Objectives

By the end of this homework, you will know:

that Lewis Carroll was a fan of CSPs
what a minimum spanning tree is
what the classic satisfiability problem is

Practice

1 Lewis Carroll

The following puzzle is due to Lewis Carroll. A small street has five houses, each one a different color, and each one housing a man of a different nationality. Each man has a different profession, likes a different drink, and has a different pet animal. The following information is given:

The Englishman lives in the red house.
The Spaniard has a dog.
The Japanese man is a painter.
The Italian drinks tea.
The Norwegian lives in the first house on the left.
The owner of the green house drinks coffee.
The green house is on the right side of the white house.
The sculptor breeds snails.
The diplomat lives in the yellow house.
They drink milk in the middle house.
The Norwegian lives next door to the blue house.
The violinist drinks fruit juice.
The fox is in the house next to the doctor's.
The horse is in the house next to the diplomat's.

Who has the zebra, and who drinks water?

(a) Formulate this puzzle as a CSP.

(b) Solve this puzzle.

Problems

2 A Variant of Simulated Annealing

Consider the following best-improvement variant of simulated annealing: at each step, starting at state x, evaluate the objective function at all neighbors y₁, ..., y_n. If any neighbor improves the value of the objective function, then move greedily to the best neighbor: set x equal to an $\arg \min_{y \in \{ y_1, \ldots, y_n \}} \mbox{Obj}(y)$ . Otherwise, if no neighbor improves the value of the objective function, then stochastically move to some neighbor y with probability p ∼ e^{-Δ(x,y) / T}, for T > 0, where Δ(x,y) = Obj(y) - Obj(x). (The probabilities are normalized to sum to 1, so that the algorithm is guaranteed to accept some move.)

Task: Describe a search space in which this algorithm outperforms classic simulated annealing. Use no more than five states.

Task: Describe a search space in which classic simulated annealing outperforms this algorithm. Use no more than five states.

Task: Describe the behavior of this algorithm as T → ∞ in terms of heuristics and/or related optimization algorithms.

Task: Describe the behavior of this algorithm as T → 0 in terms of heuristics and/or related optimization algorithms.

3 Minimum Spanning Trees