IDA* MCSP: a fast exact MCSP algorithm
Yuxi Li, Janelle J. Harms, Robert C. Holte · 2005
QoS routing has been shown to be NP-hard. A recent study of its hardness suggests that the "worst-case" may not occur in practice, and thus there may exist a fast exact algorithm. We deploy the idea of iterative deepening search and look ahead to design an exact algorithm for finding the shortest path subject to multiple constraints (the MCSP problem). The accuracy of look-ahead information determines the efficiency of a search algorithm. The higher the accuracy of the look-ahead information, the more efficient the search process. An empirical study on a wide range of topologies shows the high accuracy of look-ahead information in the studied cases. Experimental results also show that our algorithm, IDA*/spl I.bar/MCSP, is fast and, in general, significantly outperforms A*Prune, an algorithm designed for the MCSP problem. The characteristics of iterative deepening search and the high accuracy of look-ahead information make IDA*/spl I.bar/MCSP a fast exact algorithm for the MCSP problem.