Assignment 2A

CSE 573, Autumn 2005

Due in class Wednesday October 12th. You may discuss the problems with other students in the class, but please do the final writeup on your own.

1. The Traveling Salesman Decision Problem (TSP) is defined as follows: You are given a set of cities C= {c1 … cn}; a distance function d(ci, cj) over cities; and a number K. The distance between any two distinct cities is positive. A circuit is a closed path (loop) that visits each node exactly once. The objective is to determine if there is a circuit of length less than or equal to K. TSP is NP-complete, so it is a good candidate for a problem to be solved by heuristic search.

(a) Formulate TSP as a state space search problem, where each state is a partial circuit. What is the size of the state space, in terms of the number of cities? About how large a problem could you hope to solve by uninformed, exhaustive search? (Make a rough, back-of-the-envelope calculation, using your guess-timate of machine speed.)

(b) Consider the following heuristic function:

(length of a minimum spanning tree over the unvisited nodes) +
(length of the the shortest edge from some visited node to an unvisited node) +
(length of the 2nd shortest edge from some visited node to an unvisited node)

Is this heuristic admissible? Why or why not? Can it be computed efficiently?

(c) Formulate TSP as a state space search problem, where each state is a complete circuit. Suggest a search method and appropriate heuristic for this formulation.

2. Consider a local search procedure for finding satisfying assignments for a given formula F, which operates as follows:

1. The initial state is a random truth assignment.

2. The neighbors of a state are assignments that differ on a single variable.

3. The heuristic value of a state is the number of clauses that it makes false. If two neighbors have the same heuristic value, the search chooses randomly between them.

Suppose F is the formula:

(x1 v ~x2) & (x1 v ~x3) & (x1 v ~x4) & ... & (x1 v ~x100)

(a) What is the probability that the initial state willl satisfy F?

(b) If the initial state does not satisfy F, then how many search steps will be needed to reach a satisfying assignment?

(c) What single clause could we add to F such that it would still be satisfiable, but extremely difficult to solve using this local search algorithm? Briefly explain why it would be difficult.

(d) Optional: Create a CNF formula that cannot be solved by this algorithm (even in infinite time), if the initial guess is not a solution.