A* Search

A* combines the benefits of both Uniform Cost Search and Best-First Search.

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

• g(n): Cost from start to current node
• h(n): Estimated cost from current node to goal

Guarantees shortest path and is usually the most efficient.

Uniform Cost Search

UCS expands nodes based on their path cost from the start node.

Only considers g(n) where:

• g(n): Actual cost from start to current node

Guarantees shortest path but may explore more nodes than A*.

Depth-First Search

DFS explores as far as possible along each branch before backtracking.

Uses a Stack (LIFO)

• Memory efficient
• May not find shortest path
• Can get stuck in infinite paths

Best-First Search

Greedy approach that expands the most promising node based on heuristic.

Only considers h(n) where:

• h(n): Estimated cost from current node to goal

Fast but does not guarantee shortest path.