# 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)

Algorithm Time Cost (m)
0 BFS 0.00139 954.727
1 DFS 0.00043 1521.548
2 dijkstra 0.01505 801.464
3 hill_climbing 2.60314 801.464
4 beam 19.29147 838.502
5 astar 0.00169 839.904
6 bidirectional_astar 0.00166 827.505
7 Graph Contraction 0.23532
8 Bidirectional-Dijkstra (contracted graph) 0.00084 848.715

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.