Physical Sciences and Mathematics Commons^™

Algorithmic Foundations Of Heuristic Search Using Higher-Order Polygon Inequalities, Newton Henry Campbell Jr.

CCE Theses and Dissertations

The shortest path problem in graphs is both a classic combinatorial optimization problem and a practical problem that admits many applications. Techniques for preprocessing a graph are useful for reducing shortest path query times. This dissertation studies the foundations of a class of algorithms that use preprocessed landmark information and the triangle inequality to guide A* search in graphs. A new heuristic is presented for solving shortest path queries that enables the use of higher order polygon inequalities. We demonstrate this capability by leveraging distance information from two landmarks when visiting a vertex as opposed to the common single landmark …