Search Algorithm Comparison

Here can compare the performance and costs for each of the aforementioned search algorithms. The benchmarking function returns the algorithm’s name, the runtime of the algorithm (in seconds), the route’s cost (in metres), as well as the algorithm’s search space.

# Setup the Graph
import osmnx
import pandas
from smart_mobility_utilities.common import Node
from smart_mobility_utilities.search import *

stats = []
reference = (43.661667, -79.395)
G = osmnx.graph_from_point(reference, dist=300, clean_periphery=True, simplify=True)
origin = Node(graph=G, osmid=55808290)
destination = Node(graph=G, osmid=389677909)

# Benchmark Blind Search Algorithms
stats.append(benchmark(BFS,use_G=False, G=G,origin=origin, destination=destination)) # BFS
stats.append(benchmark(DFS,use_G=False, G=G,origin=origin, destination=destination)) # DFS
stats.append(benchmark(dijkstra, G=G,origin=origin, destination=destination)) # Dijkstra

# Benchmark Informed Search Algorithms
stats.append(benchmark(hill_climbing, G=G, origin=origin, destination=destination))
stats.append(benchmark(beam, G=G, origin=origin, destination=destination))
stats.append(benchmark(astar,G=G,origin=origin, destination=destination))

# Handle special case for bidirectional A*
name, rtime, rcost = benchmark(bidirectional_astar,include_cost=False,G=G,origin=origin, destination=destination)
rcost = 827.505 # (from previous section)
stats.append((name,rtime,rcost))

# Benchmark both the contraction generation as well as the search
G = osmnx.graph_from_point(reference, dist=300, clean_periphery=True, simplify=True, network_type='drive_service')
start = 36603405
end = 24959560
c_gen = process_time()
G, hierarchy = contraction_hierarchy_generate(G)
c_gen = process_time() - c_gen
ch_time = process_time()
route, ch_cost = bidirectional_dijkstra_with_contraction(G,start,end,hierarchy, cost=True)
ch_time = process_time() - ch_time

stats.append(('Graph Contraction',c_gen,''))
stats.append(('Bidirectional-Dijkstra (contracted graph)',ch_time,ch_cost))
df = pandas.DataFrame(stats, columns=['Algorithm','Time','Cost (m)'])
df.style.hide_index() # Hide the index for display purposes
df.round(5)

---------------------------------------------------------------------------
ModuleNotFoundError                       Traceback (most recent call last)
Input In [1], in <cell line: 4>()
      2 import osmnx
      3 import pandas
----> 4 from smart_mobility_utilities.common import Node
      5 from smart_mobility_utilities.search import *
      7 stats = []

ModuleNotFoundError: No module named 'smart_mobility_utilities'

Note that cost and time for Bidirectional-Dijkstra with contraction used a simplified version of the road network, which will generate a different shortest path, as well as reduce overall search time.

Comparison of Time and Space Complexities

Algorithm	Worst-case Time	Worst-case Space	Completeness	Optimal
BFS	\(O(b^d)\)	\(O(b^d)\)	Yes	No
DFS	\(O(b^d)\)	\(O(bd)\)	Yes	No
Dijkstra	\(O(|E|+|V|log|V|)\)	\(O(b^d)\)	Yes	Yes
Hill Climbing	\(O(\infty)\)	\(O(b)\)	No	No
Beam Search	\(O(\infty)\)	\(O(kb)\)	No	No
A* Search	\(O(b^d)\)	\(O(b^d)\)	Yes	No
Bidirectional A*	\(O(b^d)\)	\(O(b^d/2)\)	Yes	No
Bidirectional Dijkstra with contraction	\(O(|E|+|V|log|V|)\)	\(O(b^d/2)\)	Yes	Yes

Note

Notes

• An A* Heuristic search can be “optimally efficient”, depending on the heuristic used.

• As both Hill Climbing and Beam Search can get stuck at local maxima, they are considered to be incomplete.

• Contraction-based bidirectional searches perform at the same time complexity as a normal bidirectional Dijkstra, at the expense of drastically increased preprocessing time.

At first glance, it may seem that a Bidirectional Dijkstra is the “best” search algorithm, as it is both complete and optimal, as well as more space efficient than a normal Dijkstra search. However, when dealing with large datasets, space complexity is often a bigger hurdle than actual performance or guaranteeing an optimal solution.

When comparing search algorithms, it is important to be aware of the constraints for any given problem, and select an algorithm based on those constraints. For example, certain implementations of hill climbing may result in rapid exit conditions. If the goal is to maximize number of problems solved (and local maxima are an acceptable result), Hill Climbing algorithms result in quick solutions that have some degree of “optimality”.

On the other hand, preprocessing-heavy algorithms like contraction hierarchies offer incredibly low space costs (even more so when implemented with a bidirectional search), as well as rapid searches for guaranteed optimal solutions (if using Dijkstra). For high-volume usage implementations where preprocessing is not a concern (i.e. Uber), contraction hierarchies are a good choice. In fact, the osrm package that is used in this book is primarily based on an implementation of contraction hierarchies.