A comparative study of tree-based search algorithms on the London Underground

TL;DRAbstract

In this paper, we examine different tree-based search algorithms that can be used for solving the shortest path problem. We investigate the use of three informed search algorithms and three uninformed search algorithms on the London Underground, an intricate railway system that connects various parts of Greater London and its neighbouring areas with more than 300 stations and 11 lines. We also present a custom search algorithm for this task. We show that, while Best-First and A* are effective at finding short and useful paths, Hill-Climbing and most of the uninformed search algorithms are less useful. We conclude that heuristic algorithms are the direction at which we should concentrate on in this kind of problems.

Chat with Paper

AI Agents for this Paper