Search — Informatique universitaire

Vocabulaire

English	Sens
search tree	search tree
heuristic/hjuːˈrɪstɪk/	heuristic

English

The tree and the estimate

A search tree: nodes are states, edges are moves. Uninformed search expands blindly — breadth-first (BFS, shortest when steps equal), depth-first (DFS, frugal memory). Informed search uses a heuristic $h(n)$: A* search picks the node minimising $f = g + h$.

{exercise:uni-cs1301-astar}

Pratique

A* chooses the node minimising —

Difficulté 1/5 · 100 pièces + un petit bonus lors de la première réussite aujourd'hui

English

Course graph: D→A (4), D→B (2), A→C (3), B→C (1), C→G (5), B→G (9); $h = \{A{:}8, B{:}6, C{:}5, G{:}0\}$. A* pops D (0), B (8), C (8), G (8): optimal cost 8 via D→B→C→G, four expansions — BFS visits every node.
Admissibility is the contract: $h(n) \le h^*(n)$ guarantees the first goal pop is optimal, because $f$ at that pop is a lower bound no open node can beat.

{exercise:uni-cs1301-trace}

Pratique

On the course graph, A* expands — nodes before the goal

Difficulté 1/5 · 100 pièces + un petit bonus lors de la première réussite aujourd'hui

English

Overestimate $h(C) = 12$: C carries $f = 3 + 12 = 15$ while Goal-through-B carries $11$ — A* pops the Goal at cost 11 and stops: suboptimal ($11 > 8$).
Complete (finds a solution) is not optimal (finds the best); BFS's frontier costs $O(b^d)$ memory.

{exercise:uni-cs1301-lies}

Pratique

Overestimating h(C) to 12 makes A* return cost —

Difficulté 1/5 · 100 pièces + un petit bonus lors de la première réussite aujourd'hui