Search Algorithms in AI

A GPS application determines the quickest path among many other potential routes. A chess program selects a move from many others in a game. A big language model chooses from one potential sequence of tokens among the countless possibilities. These choices are made through a search algorithm. In this guide, all the different types of search algorithms that are employed by AI systems are explained, which include uninformed search, informed or heuristic search, local search, adversarial search, and search methods in reasoning models.

What Is a Search Algorithm in AI?

Search algorithms within the field of AI are clearly defined as procedures that examine a space of potential states in order to determine a path of actions which take a start state to a goal state. This is based on the structure proposed within Artificial Intelligence: A Modern Approach by Russell & Norvig, the standard textbook for search within AI courses at university level.

Search algorithms are distinct in three ways: the method of determining the next state to explore, the incorporation of problem specific information into that decision making process, and optimality of solutions provided.

How Search Algorithms Actually Work

Every search algorithm operates on four elements: the state, the action, the goal test, and the path cost.

Element	Definition	Example (route planning)
State	A specific configuration of the problem at one point in time	The current city on a driving route
Action	A valid transition from one state to another	Taking a specific road to the next city
Goal test	A condition that checks whether a state satisfies the objective	Arriving at the destination city
Path cost	A numeric value assigned to a sequence of actions	Total distance in kilometers or total travel time

The algorithm begins from the initial state, finds the available actions and then evaluates all possible states by testing for the goal test. This process continues till a state is reached which satisfies the goal test.

Types of Search Algorithms in AI

Search algorithms for AI can be classified into five broad classes:

• Blind/uninformed search: conducts the search without any knowledge of distance from the state to the target.
• Heuristic/informed search: utilizes estimates of distance to the target while conducting the search.
• Local search: operates by working with the current state and moving to adjacent states, without building a search tree.
• Adversarial search: search through a game tree where the other player makes decisions that counter the goal.
• Vector/LLM search: searches the embedding space or token sequences, not the graph.

Uninformed (Blind) Search Algorithms

The uninformed search algorithm chooses the next state based on how the problem is defined, such as node depth or path cost. It does not use any estimation of how far the goal is located.

Breadth-First Search (BFS)

In breadth-first search, all the nodes at the current depth level are explored before proceeding to the next level. This algorithm utilizes the FIFO (first-in, first-out) queue in order to determine which node should be expanded.

BFS guarantees the optimal solution if all actions are equal in terms of their costs. Both time and space complexity of this algorithm are O(b^d), where b is the branching factor and d is the depth of the shallowest goal. If the branching factor equals 2 and the goal depth equals 5, BFS creates no more than 63 nodes until the solution is found. The drawback of this method is that it requires a lot of memory since it keeps all the nodes at each level.

Depth-First Search (DFS)

In depth-first search, one branch of the search tree is explored to its full extent before backtracking. Depth-first search utilizes a stack data structure that operates on the principle of last-in, first-out, usually with the help of recursion.

The space complexity of DFS is O(bm), where m stands for the maximum depth of the tree, which is much less compared to BFS. Thus, DFS suits well cases when the depth of the tree is known and there is high branching. DFS does not provide optimal solution and can get stuck in the infinite path in case of cyclic trees.

Uniform Cost Search (UCS) — and Why It’s Really Dijkstra’s Algorithm

Uniform Cost Search always expands the node having the minimum cumulative cost incurred to reach that node from the root node, by making use of the priority queue. Uniform Cost Search is a generalized version of Dijkstra’s algorithm, which was published by Edsger Dijkstra in the year 1959 in the paper titled “A Note on Two Problems in Connection with Graphs.”

When all actions have equal costs, Uniform Cost Search behaves similar to Breadth First Search. Time and space complexity of Uniform Cost Search are O(b^(1 + ⌊C*/ε⌋)) where C* is the cost of the optimal solution and ε is the minimum cost of any action.

Bidirectional Search and Iterative Deepening DFS

Bidirectional search is a combination of two searches running in parallel. The first begins at the start state, while the second starts from the goal state and goes backwards until both paths meet at a common point. Since the bidirectional search does not need to go through the whole search tree in each search but only half, fewer nodes are examined than in a single forward search.

The iterative deepening depth-first search (IDDFS) is an application of DFS where the algorithm is applied repeatedly up to a certain level of depth and then incrementally by one level more each time. In this way, we combine the space efficiency of DFS and the completeness of BFS.

Informed (Heuristic) Search Algorithms

Informed searches make use of the h(n) function in order to calculate the cost to the goal from the current node. The calculation of this cost allows the algorithm to favor nodes that look like they are close to the goal node.

Greedy Best-First Search

Greedy best-first search selects the node with the minimum heuristic cost h(n). Greedy best-first search is very fast, though it is not guaranteed to provide an optimal solution as it neglects the cost of the path completely.

A* Search — Tree vs. Graph Search

The search will expand the node that has the minimum value of f(n)=g(n)+h(n), where g(n) represents the actual cost from the starting node and h(n) represents the estimated cost to reach the goal.* The A* algorithm was proposed in 1968 in the paper published in IEEE Transactions on Systems Science and Cybernetics by Peter Hart, Nils Nilsson, and Bertram Raphael.

The A* algorithm is guaranteed to find the optimal solution if the heuristic function used is admissible in nature, which means the heuristic never overestimates the actual cost to the goal. A heuristic function is called consistent if it doesn’t overestimate its actual step costs between two adjacent nodes; all consistent heuristic functions are admissible as well.

The A* tree search algorithm considers the search space as a tree but does not keep any record of the states it has already traversed, hence it may re-traverse the same state multiple times. However, in the A-star graph search, there is a closed list of traversed nodes to avoid this redundancy.

Path	g(n)	h(n)	f(n)
S	0	7	7
S → A	3	9	12
S → D	2	5	7
S → D → B	3	4	7
S → D → B → E	4	3	7
S → D → B → E → G	7	0	7

Local Search Algorithms

Local search algorithms deal with one current state and make moves to its neighboring states. Local search algorithms store nothing in memory; hence, they can be used for massive optimization problems since it is not required to keep a track of the solution.

Hill Climbing Search

The hill climbing search process begins from any initial state and then transitions to the neighboring state that has the highest value until there is no neighboring state that has a better value than the current state. The end state of this process is known as the local maximum. Hill climbing often ends up at the local maximum which is inferior to the global maximum.

Simulated Annealing

The simulated annealing approach will accept a movement to a state with lower value at some decreasing probability, based on a temperature schedule. The method was developed by Scott Kirkpatrick, C. Daniel Gelatt, and Mario Vecchi in 1983, in an article published in the journal Science, drawing upon the concept of annealing metal. Accepting movements to states with lower values will help the algorithm to avoid local maxima.

Local Beam Search

Local Beam Search retains k states at once, produces successors of all k states, and selects only the k best successors for further processing. Local Beam Search differs from performing k hill climbing searches independently in that Local Beam Search allows sharing of information across all k states. This helps to focus the search in the right areas.

Genetic Algorithms

In a genetic algorithm, the algorithm maintains a population of candidate solutions and uses operations such as selection, crossover, and mutation to create new candidates, in accordance with a particular fitness function. The concept of genetic algorithms was first introduced by John Holland in his book titled Adaptation in Natural and Artificial Systems published in 1975.

Adversarial Search: How Game-Playing AI Searches

Adversarial search involves situations where there is a conflict between two or more agents where the win by one agent means the loss for the other. Each node in the search tree corresponds to a situation, and each level belongs to the two players alternatively.

Minimax Algorithm

The minimax algorithm chooses the move with the highest minimum value that can be forced by the opponent, assuming that the opponent will play optimally in all circumstances. The minimax algorithm analyzes all the leaf nodes in the game tree and assigns them numeric values according to their utility.

Alpha-Beta Pruning

Alpha-beta pruning prunes away those branches that will not influence the outcome at all, but it doesn’t influence the outcome that the minimax algorithm gives. In case of good move ordering, alpha-beta pruning changes the branching factor b to approximately sqrt(b), hence making time complexity change from O(b^d) to O(b^(d/2)).

Monte Carlo Tree Search (MCTS) — How AlphaGo Searches

Monte Carlo tree search is an iterative process of creating a game tree through repeated simulations of random playouts from promising nodes. DeepMind’s AlphaGo used Monte Carlo tree search and deep neural networks, and it beat a professional Go player, Lee Sedol, by winning four games to one in March 2016. This was published in Nature by David Silver et al. Monte Carlo tree search does not need a full evaluation function for each position and therefore it can be applied in games like Go where the number of possible positions is very high.

Search in the Age of LLMs (2026 Update)

Search algorithms have been extended from graphs to two domains important in modern AI systems, namely, search over vector embeddings, and search over spaces of possible outputs of models.

Vector and Embedding Search (kNN, ANN)

k-nearest neighbors (kNN) search involves finding k data points in the data set that are the closest to a query data point in terms of a distance metric such as cosine similarity or Euclidean distance. The kNN search is used in recommendation systems and text search on vectors and embeddings, for example, Word2Vec (Mikolov et al., 2013) and BERT (Devlin et al., 2019) embeddings.

The approximate nearest neighbor (ANN) search provides the points that are close enough to be considered the nearest neighbors, thus sacrificing a little bit of accuracy for an order of magnitude gain in performance. An exact kNN search would require comparing the query with all data points, which is not practical for larger scales. ANN algorithms use indexes that can help to save time compared to exact kNN search. Vector databases use ANN search to retrieve passages for RAG.

How Reasoning Models Search Through Answers

The Tree of Thoughts is a reasoning framework that models the problem-solving task as a search in a tree of possible reasoning steps by applying search algorithms like BFS, DFS, or beam search. The method was proposed by Shunyu Yao and other co-authors in their 2023 research paper. Another recent work explores the idea of applying the Monte Carlo tree search algorithm for reasoning with an LLM through complex multi-step tasks by exploring promising branches at each reasoning step.

Search Algorithm Comparison Table

Algorithm	Time complexity	Space complexity	Complete	Optimal	Best use case
Breadth-First Search	O(b^d)	O(b^d)	Yes	Yes, if step cost is uniform	Shortest path with equal step costs
Depth-First Search	O(b^m)	O(m)	No	No	Deep, narrow trees with limited memory
Uniform Cost Search	O(b^(1+⌊C*/ε⌋))	O(b^(1+⌊C*/ε⌋))	Yes	Yes	Weighted graphs, variable step costs
Greedy Best-First Search	O(b^m)	O(b^m)	No	No	Fast, approximate solutions
A* Search	O(b^d)	O(b^d)	Yes	Yes, if heuristic is admissible	Optimal pathfinding with a good heuristic
Hill Climbing	Problem-dependent	O(1)	No	No	Large optimization problems, memory-constrained
Minimax	O(b^d)	O(bd)	Yes	Yes, against optimal opponent	Two-player games with small state spaces
Alpha-Beta Pruning	O(b^(d/2)) with optimal ordering	O(bd)	Yes	Yes, against optimal opponent	Two-player games needing deeper search
Monte Carlo Tree Search	Depends on simulation budget	O(bd)	Approximate	Approaches optimal with more simulations	Games with very large state spaces, such as Go

How to Choose the Right Search Algorithm

Algorithm selection should consider four aspects: goal state availability, memory restrictions, optimality need, and opponent presence.

• If the problem contains an opponent, then use minimax with alpha-beta pruning on small state spaces or Monte Carlo tree search on large ones such as Go or complicated strategy games.
• If the optimal route is needed and there is a reliable heuristic function, then go for the A* search.
• In case of no available heuristic and equal step costs, go for the breadth-first search.
• In case of unequal step costs and no available heuristic, go for the uniform cost search.
• In case of memory limitations and a deep search tree, go for the depth-first search or iterative deepening depth-first search.
• In case the goal is configuration rather than a route and the state space is huge, then apply local search such as hill climbing, simulated annealing, or genetic algorithms.
• If the problem is about extracting similar objects based on embeddings in a huge database, then go for the kNN to get exact results or ANN for quick and approximate ones.

Real-World Applications of AI Search Algorithms

Search algorithms work within systems that span different sectors.

• Pathfinding and Navigation – GPS systems employ variations of Dijkstra’s algorithm and A* search for calculating routes using driving, walking, and public transport.
• Robotics – mobile robots utilize search algorithms in planning routes that will be free from collisions with other objects.
• Game playing – chess and Go players employ minimax, alpha-beta pruning, and Monte Carlo tree search to choose actions.
• Recommendation systems – online streaming sites and eCommerce websites use kNN and ANN search for recommending products based on the history of the user’s actions.
• Medical image analysis – medical diagnostics employ nearest-neighbor search for comparing a new medical image with previously analyzed and labeled images.
• AI agents and tool use – language models utilize tree-based search for analyzing multiple options of actions before executing an action.

Advantages and Limitations of AI Search Algorithms

Advantages:

• Search algorithms enable a systematic approach towards finding the answer from among many possibilities.
• Many algorithms like BFS, UCS, and A* will find an optimal solution under certain conditions.
• The heuristic approach ensures that the algorithm has to check fewer states, which helps when dealing with complex problems.
• The local search approach can handle large optimization problems where exhaustive search fails.

Limitations:

• Uninformed search techniques take exponentially increasing time and space with increasing problem size.
• The performance of informed search is dependent upon the quality of the heuristic function; a bad heuristic will result in A* being no more efficient than an uninformed search.
• Adversarial search increases in computational cost due to high branching factor and increasing search depths; hence Go game uses Monte Carlo search in place of minimax.
• Local search techniques do not guarantee that they will converge to global optimum.

Frequently Asked Questions

Closing

Search algorithms continue to be the foundational approach used by AI systems to choose between multiple results, regardless of whether those options include roads, chess moves, or steps of reasoning in a language model. Although the algorithm varies depending on the problem (BFS and A* for problems involving graphs with definite boundaries, minimax and MCTS for adversarial games, ANN for problems in high-dimensional space), the four components that define them remain constant: state, action, goal test, and path cost.