Source Count: 21 | Weighted Score: 45 | Source Confidence: [5/5] | Primary Tier: 1 | Last Updated: March 14, 2026
Keywords: search algorithms, BFS, DFS, A*, heuristic search, adversarial search, Monte Carlo tree search, graph search, pathfinding, combinatorial optimization
Category Tags: information-computation, computer-science, algorithms, artificial-intelligence, optimization
Cross-References: ZD_5_10 — Information Retrieval · ZD_5_06 — Knowledge Representation · ZD_1_02 — Mathematics Information

QUICK SUMMARY

Search algorithms are fundamental computational procedures for exploring state spaces, finding paths, locating solutions, and making decisions — they constitute one of the core pillars of computer science and artificial intelligence. Every problem that can be formulated as "find a sequence of steps from an initial state to a goal state" is a search problem: route planning (find the shortest path from A to B on a map), puzzle solving (Rubik's cube, sliding tiles), game playing (what move leads to victory?), scheduling (assign tasks to resources optimally), theorem proving (find a sequence of logical deductions), and program synthesis (construct code that satisfies a specification). The major categories are: (1) Uninformed (blind) search — explores the state space without domain-specific knowledge: Breadth-First Search (BFS — explores all neighbors of a node before moving deeper, guarantees shortest path, but memory-intensive), Depth-First Search (DFS — explores as deep as possible before backtracking, memory-efficient but no shortest-path guarantee), Iterative Deepening (DFS with increasing depth limits — combines BFS optimality with DFS memory efficiency); (2) Informed (heuristic) search — uses domain-specific knowledge (a heuristic function estimating distance to goal) to guide exploration: A (Hart, Nilsson, Raphael, 1968) — the most important heuristic search algorithm, guarantees optimal solution if the heuristic is admissible (never overestimates); used ubiquitously in pathfinding (GPS navigation, video game AI, robotics); Greedy Best-First Search; IDA (memory-bounded variant); (3) Adversarial search — for competitive games where an opponent actively works against you: Minimax (von Neumann, 1928 — assumes optimal opponent play), Alpha-Beta Pruning (safely eliminating branches of the game tree — roughly squaring the depth searchable in the same time), and Monte Carlo Tree Search (MCTS) (Kocsis and Szepesvári, 2006 — UCT algorithm) — sampling random game playout simulations to estimate move quality without full tree traversal; MCTS was the key breakthrough enabling computer Go programs (combined with deep neural networks in AlphaGo/AlphaZero); (4) Local search and metaheuristics — for optimization problems where the path doesn't matter, only the final solution: Hill Climbing, Simulated Annealing (Kirkpatrick et al., 1983 — inspired by metallurgical annealing, allows probabilistic acceptance of worse solutions to escape local optima), Genetic/Evolutionary Algorithms (Holland, 1975), Tabu Search.

1. VERIFIED CLAIMS (Tier 1 — Peer-Reviewed / Established)

1.1 Uninformed Search

• Breadth-First Search (BFS): explores all nodes at depth d before depth d+1; guarantees shortest path in unweighted graphs; time and space complexity O(b^d) where b = branching factor, d = depth; implemented with a queue
• Depth-First Search (DFS): explores as deep as possible along each branch before backtracking; space complexity O(bm) where m = maximum depth — far more memory-efficient than BFS; but may find suboptimal solutions and can loop in infinite graphs without cycle detection
• Dijkstra's Algorithm (1959): finds shortest paths from a source to all nodes in a weighted graph with non-negative edge weights; foundational for network routing and GPS navigation; generalized by A* with heuristics

1.2 Heuristic Search

• A (Hart, Nilsson, Raphael, 1968): f(n) = g(n) + h(n) — actual cost from start to current node + heuristic estimate from current to goal; guarantees optimal solution when h(n) is admissible (never overestimates true cost) and consistent; the standard algorithm for pathfinding in navigation, robotics, and game AI; variants include IDA (iterative deepening A — reduces memory from exponential to linear), SMA (Simplified Memory-Bounded A), and D (dynamic replanning)
• Heuristic design: the quality of the heuristic determines search efficiency — the closer h(n) is to the true cost, the fewer nodes need to be expanded; common heuristics include Manhattan distance (grid movement), Euclidean distance (continuous space), and pattern databases (precomputed partial solution costs)

1.3 Adversarial Search

• Minimax (von Neumann, 1928): for two-player zero-sum games — one player maximizes, the opponent minimizes; assumes both players play optimally; explores the full game tree to the terminal states and propagates values back
• Alpha-Beta Pruning: eliminates branches of the minimax tree that cannot affect the final decision — effectively reducing time complexity from O(b^d) to O(b^(d/2)) with optimal move ordering, allowing search roughly twice as deep in the same time; enabled computer chess programs (Deep Blue vs. Kasparov, 1997)
• Monte Carlo Tree Search (UCT — Kocsis and Szepesvári, 2006): balances exploration (trying new moves) and exploitation (deepening promising branches) using Upper Confidence Bounds; each iteration: select a leaf using UCB, expand it, simulate a random playout, backpropagate the result; revolutionized computer Go; combined with neural networks in AlphaGo/AlphaZero

2. CREDIBLE CLAIMS (Tier 2 — Academic / Debated but Supported)

2.1 Metaheuristics

• Simulated Annealing (Kirkpatrick et al., 1983): analogous to metallurgical annealing — accepts worse solutions with probability decreasing over time (temperature schedule); effective for combinatorial optimization (traveling salesman, circuit design, protein folding); no guarantee of finding global optimum but practically effective
• Genetic/Evolutionary Algorithms (Holland, 1975; Goldberg, 1989): population-based search maintaining a pool of candidate solutions; operators: selection (fitness-proportional), crossover (combining parts of two solutions), mutation (random perturbation); effective for multi-objective optimization and problems with complex fitness landscapes

2.2 Planning and Constraint Satisfaction

• Classical AI planning: search in the space of world states (or the space of plans) to find a sequence of actions achieving a goal; STRIPS (Fikes and Nilsson, 1971), PDDL (Planning Domain Definition Language), and modern planners (Fast Downward, LAMA) use heuristic search over structured state representations
• Constraint Satisfaction Problems (CSPs): formulated as finding variable assignments satisfying constraints; solved by backtracking search combined with constraint propagation (arc consistency), variable/value ordering heuristics, and local search; applications include scheduling, timetabling, and Sudoku solving

3. SPECULATIVE CLAIMS (Tier 3 — Possible but Unverified)

3.1 Quantum Search Advantage

• Grover's Algorithm (1996): provides quadratic speedup for unstructured search — O(√N) vs. O(N) classical; whether practical quantum computers can leverage this for real-world combinatorial search problems at useful scale remains an open question dependent on quantum hardware development

4. DUBIOUS CLAIMS (Tier 4 — No Credible Source / Contradicted by Evidence)

4.1 Search Is Obsolete in the LLM Era

• [MISLEADING] While large language models can solve some search-like problems (e.g., generating solutions through learned patterns), fundamental search algorithms remain essential — LLMs themselves use beam search for text generation, MCTS is combined with LLMs for reasoning (Tree of Thoughts), and search/planning algorithms underpin robotics, logistics, hardware verification, and scientific computing

COUNTER-ARGUMENTS AND CRITICAL PERSPECTIVES

Worst-Case Complexity Limits Formal Guarantees

Many search problems of practical interest (planning, scheduling, constraint satisfaction) are NP-hard, meaning that no polynomial-time algorithm is known and exact solutions cannot be guaranteed for large instances. The theoretical elegance of A* optimality, for example, does not translate to practical use when state spaces are exponentially large. Practitioners often resort to incomplete or anytime algorithms that sacrifice optimality for tractability — a pragmatic compromise that formal analysis alone cannot justify.

Heuristic Design Is More Art Than Science

The effectiveness of informed search algorithms (A, IDA, MCTS) depends critically on heuristic quality, but designing good heuristics remains largely an ad hoc, domain-specific craft. Automated heuristic learning (e.g., pattern database construction, learning heuristics from solved instances) addresses this partially, but no general method exists for producing consistently effective heuristics across domains. The gap between "there exists a good heuristic" and "we can find it" remains substantial.

LLM-Based Approaches May Bypass Explicit Search for Some Problem Classes

Large language models can solve certain search-like problems (code generation, proof search, planning) through learned pattern matching without explicit tree/graph search. Whether this represents a fundamentally different computation or merely implicit search compiled into network weights is debated. For well-structured combinatorial problems, explicit search algorithms remain superior; for ill-structured, knowledge-intensive problems, LLM approaches may be more practical than traditional search.

Monte Carlo Tree Search Scalability Limitations

While MCTS achieved remarkable success in Go (Silver et al. 2016), its effectiveness depends on a reliable simulation (rollout) policy and moderate branching factors. In domains with very large action spaces, sparse rewards, or where random simulations are uninformative, MCTS performance degrades. Extensions (progressive widening, learned value networks) address some limitations but add complexity and computational cost, and MCTS is not a universal solution for sequential decision-making.

IMAGES

No images assigned yet.

BIBLIOGRAPHY

1. Russell, Stuart; Peter Norvig. . | 2021 | ∅ | Artificial Intelligence: A Modern Approach | ∅ | ∅ | Upper Saddle River: Pearson | 4th | doi:10.1017/s0269888900007724 | ∅ | ∅ | ∅
2. Hart, Peter E., Nils J | 1968 | "A Formal Basis for the Heuristic Determination of Minimum Cost Paths" | IEEE Transactions on Systems Science and Cybernetics | ∅ | 4.2::100–107 | Nilsson, and Bertram Raphael | ∅ | doi:10.1109/tssc.1968.300136 | ∅ | ∅ | ∅
3. Kocsis, Levente; Csaba Szepesvári. : 282 293 | 2006 | "Bandit Based Monte-Carlo Planning" | ECML | ∅ | ∅ | ∅ | ∅ | doi:10.1007/11871842_29 | ∅ | ∅ | ∅
4. Cormen, Thomas H., et al. . | 2022 | ∅ | Introduction to Algorithms | ∅ | ∅ | Cambridge: MIT Press | 4th | ∅ | ∅ | ∅ | ∅
5. Kirkpatrick, Scott, C | 1983 | "Optimization by Simulated Annealing" | Science | ∅ | 220.4598::671–680 | Daniel Gelatt, and Mario P | ∅ | doi:10.1126/science.220.4598.671 | ∅ | ∅ | Vecchi
6. Holland, John H. | 1975 | ∅ | Adaptation in Natural and Artificial Systems | ∅ | ∅ | Ann Arbor: University of Michigan Press | ∅ | doi:10.1145/1216504.1216510 | ∅ | ∅ | ∅
7. Knuth, Donald E. | 2011 | ∅ | The Art of Computer Programming | ∅ | ∅ | Vol | ∅ | ∅ | ∅ | ∅ | 4A: Combinatorial Algorithms; Upper Saddle River: Addison-Wesley
8. LaValle, Steven M. | 2006 | ∅ | Planning Algorithms | ∅ | ∅ | Cambridge: Cambridge University Press | ∅ | ∅ | ∅ | ∅ | ∅
9. Silver, David, et al | 2016 | "Mastering the Game of Go with Deep Neural Networks and Tree Search" | Nature | ∅ | 529::484–489 | ∅ | ∅ | ∅ | ∅ | ∅ | ∅
10. Yao, Shunyu, et al | 2023 | "Tree of Thoughts: Deliberate Problem Solving with Large Language Models" | NeurIPS | ∅ | ∅ | ∅ | ∅ | ∅ | ∅ | ∅ | ∅
11. Goldberg, David E. | 1989 | ∅ | Genetic Algorithms in Search, Optimization, and Machine Learning | ∅ | ∅ | Reading: Addison-Wesley | ∅ | isbn:9780201157673 | ∅ | ∅ | ∅
12. Dorigo, Marco; Thomas Stützle | 2004 | ∅ | Ant Colony Optimization | ∅ | ∅ | Cambridge: MIT Press | ∅ | isbn:9780262042192 | ∅ | ∅ | ∅
13. Edelkamp, Stefan; Stefan Schrödl | 2012 | ∅ | Heuristic Search: Theory and Applications | ∅ | ∅ | San Francisco: Morgan Kaufmann | ∅ | isbn:9780123725127 | ∅ | ∅ | ∅
14. Pearl, Judea | 1984 | ∅ | Heuristics: Intelligent Search Strategies for Computer Problem Solving | ∅ | ∅ | Reading: Addison-Wesley | ∅ | isbn:9780201055948 | ∅ | ∅ | ∅
15. Koenig, Sven; Maxim Likhachev. : 476 483 | 2002 | "D Lite" | AAAI Conference on Artificial Intelligence* | ∅ | ∅ | ∅ | ∅ | ∅ | ∅ | ∅ | ∅
16. Coulom, Rémi. : 72 83 | 2007 | "Efficient Selectivity and Backup Operators in Monte-Carlo Tree Search" | Computers and Games | ∅ | ∅ | ∅ | ∅ | ∅ | ∅ | ∅ | ∅
17. Browne, Cameron B., et al | 2012 | "A Survey of Monte Carlo Tree Search Methods" | IEEE Transactions on Computational Intelligence and AI in Games | ∅ | 4.1::1–43 | ∅ | ∅ | ∅ | ∅ | ∅ | ∅
18. Felner, Ariel, et al | 2004 | "Additive Pattern Database Heuristics" | Journal of Artificial Intelligence Research | ∅ | 22::279–318 | ∅ | ∅ | ∅ | ∅ | ∅ | ∅
19. Stern, Roni, et al | 2019 | "Multi-Agent Pathfinding: Definitions, Variants, and Benchmarks" | Symposium on Combinatorial Search | ∅ | ∅ | ∅ | ∅ | ∅ | ∅ | ∅ | ∅
20. Schrittwieser, Julian, et al | 2020 | "Mastering Atari, Go, Chess and Shogi by Planning with a Learned Model" | Nature | ∅ | 588::604–609 | ∅ | ∅ | ∅ | ∅ | ∅ | ∅
21. Helmert, Malte | 2006 | "The Fast Downward Planning System" | Journal of Artificial Intelligence Research | ∅ | 26::191–246 | ∅ | ∅ | ∅ | ∅ | ∅ | ∅

CROSS-REFERENCE INDEX

Generated from V4 expansion plan. Last Updated: March 11, 2026

<table border="1" cellpadding="12" cellspacing="0" style="border-collapse: collapse; border: 2px solid #888; margin-top: 2em; background: #fafafa;">

<tr><td>

⚠️ AI-Assisted Research Disclaimer

This document was generated and structured with the assistance of AI tools.

While every effort is made to ensure accuracy, AI-assisted content may

contain errors, misattributions, or unintended inaccuracies. **Always

verify claims, dates, and sources independently** before citing or relying

on any information presented here.

• Sources may contain errors. Bibliography entries and cross-references

are checked by automated systems, but mistakes can occur. If something

looks wrong, it may be.

• Speculative and unverified claims are clearly labeled. This project

uses a four-tier evidence system:

• Tier 1 — Verified: Peer-reviewed, established scientific consensus.
• Tier 2 — Credible: Academically supported, debated but grounded.
• Tier 3 — Speculative: Plausible but unverified by mainstream science.
• Tier 4 — Dubious: No credible support or contradicted by evidence.
• This project maps multiple perspectives — not a single truth. Mainstream,

alternative, and skeptical viewpoints are presented side by side for

critical comparison, not endorsement. Inclusion does not imply agreement.

• We are actively improving. Source verification, factuality scoring,

and bibliography enrichment are ongoing. Each revision adds stronger

citations, corrects identified errors, and expands coverage.

📖 For full details on our verification methodology, scoring systems, and

quality metrics, see: Fact-Checking & Verification Systems

Think Openly. Check the sources. Draw your own conclusions.

</td></tr>

</table>