The 2-color problem in discrete tomography requires to construct a 2-colored matrix consistent with a given set of projections representing the number of elements of each color in each one of its rows and columns. In this paper, we describe an heuristic algorithm to find a solution of the 2-color problem, that has been recently proved to be NP-complete. The algorithm starts by computing a solution where elements of different colors may overlap, and then it proceeds in searching for switches that leave unaltered the projections but remove the overlaps. Experimental results show that this heuristic approach finds a solution in a short computational time to almost all the randomly generated 2-color instances, and it provides for the remaining ones a high quality approximation.
Solving the two color problem: an heuristic algorithm / E. Barcucci; S. Brocchi; A. Frosini. - STAMPA. - 6636:(2011), pp. 298-310. (Intervento presentato al convegno 14th International Workshop on Combinatorial Image Analysis, IWCIA 2011 tenutosi a Madrid nel maggio 2011) [10.1007/978-3-642-21073-0_27].
Solving the two color problem: an heuristic algorithm
BARCUCCI, ELENA;BROCCHI, STEFANO;FROSINI, ANDREA
2011
Abstract
The 2-color problem in discrete tomography requires to construct a 2-colored matrix consistent with a given set of projections representing the number of elements of each color in each one of its rows and columns. In this paper, we describe an heuristic algorithm to find a solution of the 2-color problem, that has been recently proved to be NP-complete. The algorithm starts by computing a solution where elements of different colors may overlap, and then it proceeds in searching for switches that leave unaltered the projections but remove the overlaps. Experimental results show that this heuristic approach finds a solution in a short computational time to almost all the randomly generated 2-color instances, and it provides for the remaining ones a high quality approximation.
I documenti in FLORE sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
