Shortest Path Discovery Problems: A Framework, Algorithms and Experimental Results
- Csaba Szepesvari, Department of Computing Science; PI of AICML
In this paper we introduce and study Shortest Path Discovery (SPD) problems, a generalization of shortest path problems: In SPD one is given a directed edge-weighted graph and the task is to find a the shortest path for fixed source and target nodes such that initially the edge-weights are unknown, but they can be queried. Querying the cost of an edge is expensive and hence the goal is to minimize the total number of edge cost queries executed. In this article we characterize some common properties of sound SPD algorithms, propose a particular algorithm that is shown to be sound and effective. Experimental results on real-world OCR task demonstrate the usefulness of the approach whereas the proposed algorithm is shown to yield a substantial speed-up of the recognition process.
Citation
C. Szepesvari. "Shortest Path Discovery Problems: A Framework, Algorithms and Experimental Results". National Conference on Artificial Intelligence (AAAI), San Jose, California, USA, pp 550-555, January 2004.| Keywords: | machine learning |
| Category: | In Conference |
BibTeX
@incollection{Szepesvari:AAAI04,
author = {Csaba Szepesvari},
title = {Shortest Path Discovery Problems: A Framework, Algorithms and
Experimental Results},
Pages = {550-555},
booktitle = {National Conference on Artificial Intelligence (AAAI)},
year = 2004,
}Last Updated: April 24, 2007Submitted by William Thorne
