m4 heuristics1

Q: What is the idea behind best-first search?

Use an evaluation function f(n) to estimate a node’s desirability and always expand the most desirable node (fringe ordered by decreasing desirability).

Q: In greedy best-first search, what is f(n)?

f(n)=h(n), an estimate of the cost from n to a goal (e.g., straight-line distance to Bucharest in the Romania map on p.5).

Q: Intuition of greedy best-first?

Expand the node that appears closest to the goal.

Q: Properties of greedy best-first (completeness, time, space, optimality)?

Complete: No (can loop). Time: O(b^m) (often much better with good h). Space: O(b^m). Optimal: No.

Q: What is the A* evaluation function?

f(n)=g(n)+h(n), where g(n) is the path cost so far and h(n) estimates cost to goal.

Q: What does f(n) represent in A*?

Estimated total cost of a cheapest solution path through n.

Q: Define an admissible heuristic.

h(n)\le h^*(n) for all n; it never overestimates the true cost to a goal (i.e., optimistic).

Q: With an admissible h, which A* variant is optimal?

A* with tree-search is optimal.

Q: Define a consistent (monotone) heuristic.

For every edge n \xrightarrow{a} n': h(n) \le c(n,a,n') + h(n'). Equivalently, f(n) is non-decreasing along any path.

Q: With a consistent h, which A* variant is optimal?

A* with graph-search is optimal.

Q: How does A* expand nodes (geometric intuition)?

In increasing f “contours” (see the f-contour visualization on p.23).

Q: A* properties (completeness, time, space, optimality)?

Complete: Yes (unless infinitely many nodes have f ≤ f(G)). Time: exponential. Space: stores all nodes (large). Optimal: Yes.

Q: Define h_1 for 8-puzzle.

Number of misplaced tiles.

Q: Define h_2 for 8-puzzle.

Sum of Manhattan distances of tiles from their goal positions.

Q: Example values from the slides?

For state S: h_1(S)=8, h_2(S)=18.

Q: What does it mean when one heuristic dominates another?

If h_2(n) ≥ h_1(n) for all n and both are admissible, h_2 dominates h_1 and typically expands fewer nodes (e.g., 73 vs 227 at depth 12; 1,641 vs 39,135 at depth 24).

Q: When do we prefer local search?

When the path is irrelevant—only the goal state matters (e.g., n-queens). Keep a single current state and try to improve it.

Q: What is the n-queens problem (setup)?

Place n queens on an n x n board with no two attacking (rows, columns, diagonals).

Q: Hill-climbing in one line?

“Like climbing Everest in thick fog with amnesia” (choose the best neighbor; see pseudocode on p.30).

Q: Main failure mode of hill-climbing?

Can get stuck in local maxima/plateaus/shoulders (diagram p.31).

Q: Typical objective function for 8-queens in slides?

h = number of attacking queen pairs (example shows h=17; local minimum example with h=1).

Q: Core idea of simulated annealing?

Occasionally accept “bad” moves to escape local maxima, but decrease their probability over time via a temperature schedule T (pseudocode p.34).

Q: Theoretical guarantee of simulated annealing (given slow cooling)?

Finds a global optimum with probability approaching 1.

Q: Example real-world uses mentioned of simulated annealing?

VLSI layout, airline scheduling, etc.

Q: What does local beam search keep track of?

k states at once. From all successors of those k, select the best k for the next iteration; stop if any is a goal.

Q: How do genetic algorithms generate successors?

By combining two parent states (selection, crossover, mutation) over a population of size k.

Q: Typical representation and scoring in Genetic Algorithms?

Bit-string (or finite alphabet) representation with a fitness function to evaluate states.

Q: n-queens fitness used in slides?

Number of non-attacking queen pairs (min 0, max 8 x 7/2=28); slide shows selection percentages (e.g., 24/(24+23+20+11)=31%) and a crossover diagram (p.38).

Q: Greedy best-first vs A*—what’s the key difference?

Greedy uses only h(n) (goal distance) and can be fast but non-optimal; A* balances cost-so-far and goal distance via g+h and is optimal with admissible/consistent h.

Q: Why can A* be memory-hungry?

It keeps all generated nodes (frontier + explored) to ensure optimality.

Q: What’s the benefit of a more informed heuristic?

Fewer nodes expanded (dominance), often orders-of-magnitude savings.