PARALLEL IMPRECISE ITERATIVE DEEPENING FOR COMBINATORIAL OPTIMIZATION
Tao Li · International Journal of High Speed Computing · 1991
In this paper we present a new parallel Iterative Deepening A* (IDA*) algorithm, the imprecise IDA* algorithm, for combinatorial optimization. This algorithm employs inadmissible heuristics. But approximate solutions which are arbitrarily close to the optimal ones can be obtained. In addition a linear speedup can be achieved by our algorithm. Experimental study has been carried out and the results are also reported here. Two computationally difficult problems, the quadratic assignment and the generalized assignment, are used in our experimental study. Our algorithm is effective for these problems of reasonable size.