Search Algorithms

All these search algorithms start with an initial state $s_0$ and a goal state $G$.

Cycle checking comes in two major types: intra-path and inter-path.

Intra-path (within a path)

• Before adding a neighbor to the current path, the algorithm looks back at the ancestors of that specific path. If the neighbor is already in that chain, it rejects it.
• It prevents infinite loops like $A\to B\to A\to B\dots$
• It allows the search to reach the same node via different branches. For example, it will explore both $A\to B\to E$ and $A\to C\to E$ as separate paths, even though they both end at state $E$.

Inter-path (between paths)

• You maintain a “Closed Set” (or Explored Set). Every time you expand a node, you put that state into the set. Before expanding any new node from the frontier, you check: “Have I expanded this state before?” If yes, you discard that path immediately.
• It stops both infinite loops and redundant work. If the algorithm reaches state $E$ via path $A\to B\to E$ first, it will completely ignore $A\to C\to E$ because state $E$ is already in the Closed Set.

Uninformed search algorithms explore the graph only based on the structure, ignoring the heuristic values ($h$).

BFS

• BFS expands all nodes at the current depth before moving on to the next level.
• Frontier: queue
• BFS finds the path with the min number of edges, not necessarily lowest total cost

DFS

• Explores as far as possible along each branch before backtracking
• Frontier: stack
• Without cycle checking, DFS can get stuck in infinite loops.
• To address this we can use DFS with Inter-Path cycle checking. Now, we maintain a “closed set” of visited states.
  • If an algorithm tries to expand a state that has been already in any previous path, that path is discarded.

Cheapest-First Search (Uniform Cost Search)

• Expand the path with the lowest cumulative cost $g(p)$
• Frontier: priority queue ordered by $cost(p)$

Informed (heuristic) search algorithms use heuristic values $h$ to guide the search towards the goal.

A* Search

• Combines path cost and heuristic $f(p)=g(p)+h(s)$, where $g$ is cost-so-far and $h$ is estimated cost-to-goal.
• Frontier: priority queue ordered by $f(p)$
• You can also do A* with intra-path cycle checking, which prevents cycles within the current path (e.g. A⇒B⇒A would be blocked)
  • Unlike inter-path cycle checking, this doesn’t prevent you from visiting the same node via two different branches.

Nearest-First Search (Greedy Best-First)

• Ignores path cost entirely and only expands based on the heuristic $h(s)$