Method
heuristic
Articles
GRA
Algorithm
A*
Dijkstra with a hint of how far is left: the wave stretches towards the goal, and the path stays shortest.
O((V + E) log V)
2 problems
GRA
Algorithm
Bidirectional search
Two Dijkstra waves towards each other: where to stop, how much is saved, and how to make it work with A*.
O((V + E) log V)
2 problems
GRA
Algorithm
Contraction hierarchies
A navigator's precomputation: contract unimportant crossroads into shortcuts and find the path with two waves going up.
O((V + E′) log V)
1 problem
GRA
Algorithm
Graph colouring
Different colours for neighbours: the greedy way, the smallest-last order, DSatur and exact search on maps and timetables.
O(V + E) for greedy in a given order and smallest last; O((V + E) log V) for DSatur with a heap
2 problems
PAR
Technique
Backtracking
Build a solution step by step, check at once and retreat from dead ends: sudoku, queens, colourings.
O(bᵈ) in the worst case
2 problems
RND
Algorithm
Genetic algorithm
A population of solutions, selection, crossover and mutation: the evolution of a racing line on a real circuit.
O(G · N · c)
2 problems
Problems
Often together
graph 4 maps and navigation 4 classic 4 shortest path 3 heap 3 weighted graph 3 games 3 interviews 3 precomputation 2 backtracking 2 meet in the middle 1 social graphs 1