Search and Problem Solving (Artificial Intelligence)

The search problem

Many AI tasks can be expressed as finding a sequence of actions that transforms an initial state into a goal state. A search problem therefore specifies states, available actions, transition rules, a goal test and a cost function.

The search space can be represented as a graph. Nodes represent states or partial solutions and edges represent actions. The challenge is that the graph may be enormous, so the search algorithm must decide which nodes are worth expanding.

Uninformed search

Breadth-first search expands the shallowest nodes first and is optimal when all actions have equal cost.
Depth-first search follows one branch deeply before backtracking and uses much less memory.
Uniform-cost search expands the lowest-cost frontier node and is optimal for positive action costs.
Iterative deepening repeatedly performs depth-limited search with increasing depth limits.

A* and heuristic search

A heuristic estimates the remaining cost from a state to a goal. A* combines the cost already paid with that estimate.

f(n) = g(n) + h(n)

When the heuristic never overestimates the true remaining cost, it is admissible. Under the standard conditions of graph search, admissible or consistent heuristics provide optimality guarantees while often reducing the number of nodes examined.

Adversarial search

Game-playing systems must account for an opponent who is actively trying to make the system fail. Minimax recursively evaluates possible moves under the assumption of optimal opposition.

Alpha-beta pruning eliminates branches that cannot affect the final decision. Strong move ordering can reduce the effective search cost dramatically. Modern game systems often combine search with learned value and policy models.

Local search

Local search methods optimise a state or configuration without requiring the complete path to the solution. Hill climbing, simulated annealing and evolutionary methods are examples.

The tradeoff is deliberate: these methods sacrifice some completeness and optimality guarantees in exchange for handling very large optimisation landscapes.