Comparing the Efficiency of Popular Pathfinding Algorithms on Random Networks

Overview

Objectives/Goals Pathfinding programs are on of the most applied algorithms in present day. In my project, I will be coding four pathfinding artificial intelligence programs (A*, Uniform Cost, Breadth-first and Depth-first search) to compare the efficiency of the algorithms based on the number of iterations and the length of the path on randomly generated networks. I believe that depth first search will be the most efficient, but also least accurate. I hypothesize that Uniform Cost will always find the shortest path, but A* will find a longer path but with a better path length and iteration ratio than Uniform Cost. I think Breadth-first will be the least efficient with the highest iteration to path ratio, and will only find a slightly shorter path then depth first search. Methods/Materials First, I designed and coded a program to generate random networks with 100 to 25000 points. I then coded 4 different pathfinding methods: A*, Uniform Cost, Breadth-first and Depth-first. I ran and repeated each program at least 1000 on different randomly generated networks. Additionally, I tested A* search with different heuristics. Results I found that Uniform Cost consistently found the shortest path. Breadth-First search average path found was 1297 units, Depth-first search had a average of 2462 units and Uniform Cost typical path was at 852. With a heuristic of 1, A*1 search had a typical path of 892. When the heuristic was set to 1.5, A*1.5 search averaged 923 units. And at a heuristic of 2, A*2 search averaged 944 units. Although Depth-first search resulted in the greatest average distance, it had the lowest Iterations to Distance ratio at 0.03. A* search was the second most efficient algorithm, with A*2 averaging 0.13, A*1.5 averaging at 0.174, and A*1 averaging at .47. Uniform cost averaged at 3.47, followed by Breadth-first at 278.99. Conclusions/Discussion My hypothesis is supported by my results. Uniform cost finds the shortest path, however it has a 3529% increase in iterations compared to depth-first search. However, the path depth-first finds is 189% larger than the one Uniform cost finds. A* search varied with different heuristics, but averaged at a 190% increase in iterations and 8% increase in pathlength. The difference between the algorithms grew exponentially. Breadth-first search was the least efficient method with a 52% percent increase in path length, and a 4348.69% increase in iterations.

Competition history

• CSEF 2018 Mathematical Sciences · Entry J1505

Resources

• CSEF project summary ↗

Related projects

Closest projects by meaning, across every fair and year in the corpus.

Browse more like this

• All Mathematics projects
• CSEF Mathematics projects
• Every CSEF 2018 project