IDA*_MCSP: A Fast Exact MCSP Algorithm
- Yuxi Li, Department of Computing Science, University of Alberta
- Janelle Harms, Department of Computing Science, University of Alberta
- Robert Holte, Department of Computing Science, University of Alberta
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. In this paper, we deploy the idea of iterative deepening
search and look ahead to design an exact algorithm for nding
the shortest path subject to multiple constraints (the MCSP
problem). The accuracy of look-ahead information determines
the efciency of a search algorithm. The higher the accuracy of
the look-ahead information, the more efcient 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* MCSP
is fast and in general signicantly 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* MCSP a fast exact algorithm for the
MCSP problem.
Citation
Y. Li,
J. Harms,
R. Holte.
"IDA*_MCSP: A Fast Exact MCSP Algorithm". ICC, pp 93-99, January 2005.
| Keywords: |
IDA*, MCSP |
| Category: |
In Conference |
BibTeX
@incollection{Li+al:ICC05,
author = {Yuxi Li and Janelle Harms and Robert Holte},
title = {IDA*_MCSP: A Fast Exact MCSP Algorithm},
Pages = {93-99},
booktitle = {},
year = 2005,
}Last Updated: June 04, 2007
Submitted by Staurt H. Johnson 
