Searching in AI - Popular Search Algorithms (Full Explanation)
Searching is a basic method used for solving problems in Artificial Intelligence. It’s commonly applied in single-player games like Sudoku, tile puzzles, and crosswords, where the search algorithm helps find a specific position or solution.
Single Agent Pathfinding Problems
Games like the 3x3 Eight-Tile, 4x4 Fifteen-Tile, and 5x5 Twenty-Four Tile puzzles are examples of pathfinding problems for a single agent. These puzzles contain a blank space and several tiles, and the objective is to arrange the tiles by sliding them horizontally or vertically into that space.
Other classic examples of single-agent pathfinding include the Rubik’s Cube, Travelling Salesman Problem, and theorem proving.
Search Terminology
- Problem Space: The area or setup where the search happens, including all possible states and the operations that move between them.
- Problem Instance: It combines the starting state and the goal state.
- Problem Space Graph: A graphical layout where nodes show different states, and edges indicate the operators used to move between them.
- Depth of a Problem: It refers to the shortest number of steps needed to get from the start to the goal.
- Space Complexity: The most nodes a search algorithm needs to keep in memory.
- Time Complexity: The total number of nodes it creates while working.
- Admissibility: Whether the algorithm guarantees the best possible solution.
- Branching Factor: The average number of new child nodes created from one node.
- Depth: Distance between the initial state and the goal in terms of steps.
Brute-Force Search Strategies
These strategies don’t use any special knowledge about the problem. They can work well when the number of states isn’t too large.
They require:
- A clear way to describe a state
- A list of valid operations
- A defined starting state
- A target goal state
Breadth-First Search (BFS)
This method begins at the root and explores all nearby nodes first before moving to the next level. It uses a FIFO queue and guarantees the shortest solution path.
If the branching factor is b and the depth is d, the total nodes can be up to b^d. However, storing all levels uses a lot of memory space.
Depth-First Search (DFS)
DFS works by going deep into one path before backtracking. It uses recursion and a LIFO stack.
This method uses less memory, only keeping a single path in memory. But if the path is long or wrong, it can run forever. Using a cut-off depth can help, but if set wrong, it may miss the solution or take longer.
Bidirectional Search
This method searches from the starting point and also from the goal, and they meet in the middle. It’s efficient since each half-search covers only half the depth.
Uniform Cost Search
This approach sorts paths based on their total cost and always expands the cheapest path. If all steps have equal cost, it works like BFS. But when there are many paths with cost less than or equal to the best one, it must explore all of them.
Iterative Deepening DFS
It starts with a depth limit of 1 and increases it gradually. Each time, it performs a full DFS up to the new limit. It only saves a small number of nodes and guarantees to find the best solution eventually.
Search Algorithm Comparison
| Criteria | Breadth-First | Depth-First | Bidirectional | Uniform Cost | Iterative Deepening |
|---|---|---|---|---|---|
| Time | b^d | b^m | b^(d/2) | b^d | b^d |
| Space | b^d | b^m | b^(d/2) | b^d | b^d |
| Optimal | Yes | No | Yes | Yes | Yes |
| Complete | Yes | No | Yes | Yes | Yes |
Informed (Heuristic) Search
When facing large problem spaces, we use heuristics—problem-specific knowledge—to improve efficiency.
Heuristic Evaluation
A heuristic estimates how close a state is to the goal. For tile puzzles, it often counts how far each tile is from its goal and adds them together.
Pure Heuristic Search
This search method expands nodes based on their heuristic value. It keeps a list of visited nodes (closed) and another for unvisited ones (open). In every round, it picks the node with the best heuristic value and explores its children.
A* Search
This is a combination of the cheapest cost so far (g(n)) and the estimated remaining cost (h(n)). The formula is:
f(n) = g(n) + h(n)
It prioritizes nodes with the lowest total estimated cost and uses a priority queue.
Greedy Best-First Search
It chooses the node that looks closest to the goal using f(n) = h(n). It's fast but not always reliable or optimal, and it might get stuck in loops.
Local Search Algorithms
These methods begin with a possible solution and improve it step by step, even if the algorithm is interrupted.
Hill-Climbing Search
This algorithm starts with a random solution and improves it by changing one element at a time. If the new solution is better, it replaces the previous one. It repeats until no improvement is found.
inputs: problem, a problem
local variables: current, a node
neighbor, a node
current <-Make_Node(Initial-State[problem])
loop
do neighbor <- a highest_valued successor of current
if Value[neighbor] Value[current] then
return State[current]
current <- neighbor
endDrawback: It’s neither complete nor optimal.
Local Beam Search
It keeps k states at a time, evaluates their successors, and selects the top k among them for the next round. This continues until the best state is found.
start with k randomly generated states loop generate all successors of all k states if any of the states = solution, then return the state else select the k best successors end
Simulated Annealing
Inspired by metal cooling, this method starts with a high "temperature" and cools gradually. It allows bad moves early on, decreasing the chance over time.
Steps:
-
Set temperature high.
-
Randomly make changes.
-
Accept worse solutions based on probability and temperature.
-
Reduce temperature gradually.
-
Repeat until condition is met.
Travelling Salesman Problem (TSP)
The goal is to find the cheapest round-trip path through all cities.
Steps:
-
List all (n - 1)! paths.
-
Calculate their costs.
-
Pick the one with the lowest cost.
.jpg)
