Found in
games
Articles
GRA
Algorithm
Breadth-first search
Walks a graph in layers and finds paths with the fewest edges in O(V + E).
O(V + E)
2 problems
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
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
GEO
Technique
Vectors and orientation
The sign of the cross product is a left or right turn; almost all of computational geometry stands on it.
O(1) per turn
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
classic 5 interviews 4 contests 3 heuristic 3 shortest path 2 graph 2 maps and navigation 2 traversal 1 queue 1 heap 1 weighted graph 1 precomputation 1