A graph search method is a deterministic algorithm that explores vertices and edges for discovery or explicit search. Methods divide into blind searches, which use no search-space information, and informed searches, which use it. section 3.6 section 2.2
Choose a method according to path costs, search direction, depth limits, and the desired balance of time and space:
- Breadth-first search examines one tree level at a time and finds shortest paths when edge costs are equal. section 3.6
- Depth-first search follows a branch as far as possible before backtracking; depth-limited search adds a maximum depth. section 3.6
- Iterative deepening search repeatedly increases the depth limit, combining DFS space efficiency with BFS-style search progress. section 3.6
- Dijkstra’s algorithm and uniform-cost search use cumulative costs for weighted graphs with non-negative edge costs; bidirectional search works forward and backward. section 3.6
- Informed methods include hill climbing, beam search, best-first search, A*, and contraction hierarchies. section 2.2
Routing between two places
Represent locations as vertices and connections as edges, then search from an origin such as home to a destination. Use blind search for simple, well-defined routing; use cost-aware methods when edge costs differ. section 3.0 section 3.6
Figure 2.16 Deterministic vs. stochastic algorithms. Deterministic algorithms follow a set procedure, and the results are repeatable, while stochastic searches have elements of randomness built into the algorithms.
Compare repeatable deterministic procedures with stochastic searches that incorporate randomness, and place graph search methods within that distinction. section 2.2
