AI · Theory

Search Algorithms

Theory

20/215

Search Algorithms

Search finds a path from start to goal on a graph of states. Uninformed: BFS, DFS, UCS — no hint about the goal. Informed: greedy, A* — use a heuristic h(n). Adversarial: minimax when an opponent plays. Always say state, action, cost.

Campus map: rooms as nodes, corridors as edges. BFS finds fewest doors if every door costs 1. A* if walking time differs. Don’t start coding before you draw the tiny graph.

Search Algorithms — output — ['A', 'B', 'D'] (or A-C-D). Queue = fewest doors if each edge costs 1.

Diagram

start
    │
    ├── BFS  (queue, fewest steps)
    ├── DFS  (stack, deep first)
    └── A*   (g+h, if heuristic OK)
    │
    ▼
   goal

Exam tip

BFS vs A* in one sentence each.

Example

# BFS shortest hops
from collections import deque
graph = {"A": ["B", "C"], "B": ["D"], "C": ["D"], "D": []}

def bfs(start, goal):
    q = deque([(start, [start])])
    seen = {start}
    while q:
        node, path = q.popleft()
        if node == goal:
            return path
        for nxt in graph[node]:
            if nxt not in seen:
                seen.add(nxt)
                q.append((nxt, path + [nxt]))
    return None

print(bfs("A", "D"))

Search Algorithms — output: ['A', 'B', 'D'] (or A-C-D). Queue = fewest doors if each edge costs 1.

Short notes

DefUninformed vs informed vs adversarial.
RuleState + action + cost.

# BFS shortest hops from collections import deque graph = {"A": ["B", "C"], "B": ["D"], "C": ["D"], "D": []} def bfs(start, goal): q = deque([(start, [start])]) seen = {start} while q: node, path = q.popleft() if node == goal: return path for nxt in graph[node]: if nxt not in seen: seen.add(nxt) q.append((nxt, path + [nxt])) return None print(bfs("A", "D"))

Search Algorithms

Example

Short notes

Questions

Search Algorithms

Example

Short notes

Questions