CSC242 homework 1 6 solutions PDF

Preview

Summary

Homework Solutions...

Description

CSC242: Homework 1.6 AIMA Chapter 4.1.3–4.1.4

1. What are the advantages and disadvantages of keeping track of more than one state during local search? ANSWER: Advantages: The set of successor states can come from any of the “promising” current states. Disadvantage: Uses more space (although only a constant factor more). Takes longer to generate successors. 2. Compare parallel local search with local beam search. ANSWER: With k local searches run in parallel, some of the searches are bound to end up in bad (unpromising) parts of the search from which it is is diffcult to reach a solution. Nonetheless, they will run to completion (although one could imagine cutting them off and starting a new search). By using local beam search with a beam of width k, states that generate uniformly poor successors will just get left behind. “In a local beam search, useful information is passed among the parallel search threads.” (AIMA p.126) It is worth noting that it is harder to parallelize local beam search, precisely because of this information sharing aspect. 3. Give the name of the algorithm that results from each of the following special cases: (a) Local beam search with k = 1. ANSWER: Hill-climbing (greedy local search). (b) Local beam search with one initial state and no limit on the number of states retained. ANSWER: Breadth-first search (with each level generated all at once). (c) Simulated annealing with T = 0 at all times (and omitting the termination test). ANSWER: “First-choice” hill-climbing (never takes a “bad” move). AIMA p. 124. (d) Simulated annealing with T = ∞ at all times. ANSWER: Random walk. (e) Genetic algorithm with population size N = 1. ANSWER: Parents are always two copies of the one individual. Crossover therefore has no effect. Result is a (slow) random walk due entirely to mutations. 1

4. Suppose you’re working on a problem at your job. Your officemate suggests an approach based on hill climbing. The boss asks for your opinion on the spot. You have about 10 seconds. What would you say? ANSWER: “The success of hill climbing depends very much on the shape of the state-space landscape: if there are few local maxima and plateaux, random-restart hill climbing will find a good solution very quickly.” (AIMA p. 125) So the answer is (a) it depends on whether there are many local maxima, and (b) random restarts would be A Good Idea. And watch out for balding porcupines. . . 5. As you probably already know, a Traveling Salesperson Problem (TSP) for a set of cities involves finding the shortest path (“tour”) that visits each city exactly once. In the classic version of the problem, you are given a symmetric matrix of distances between cities, and all cities are connected (i.e., they form a complete graph). Variations involve having actual road networks (limited connectivity) and asymmetric distances. Formulate the classic TSP as a local search problem. Hint: Use a complete-state formulation of state. ANSWER: We’ll use a complete-state formulation, as defined on AIMA page 122. Thus a state will be a tour that visits all the cities exactly once, and we will be searching for a tour with minimum total length. • Initial state: Can be any tour that visits each city exactly once. How would you find such a tour? Since the graph is fully connected, any permutation of the cities forms a tour. In general, a simple greedy algorithm can often provide an initial state for local search (note that this is different from greedy local search). • Successor function: You need a way to modify the current tour (state) while preserving the property of visiting every city exactly once. Here are two possibilities: – 2-opt: Select two edges from the tour and remove them. There is only one other way to reconnect the tour:

– 3-opt: Select three edges from the tour. There are seven other ways to reconnect the tour:

2

You may notice that the first three of these other than the initial state are 2-opt moves. • Cost function: Length of tour. Obviously, since this is what you’re trying to minimize. The key part for local search is generating successors. In general, if you break k edges in a tour, there are (k − 1)!2k−1 ways to reconnect it. Your local search procedure will choose the best of them (the lowest cost) and repeat. FYI: These “k-opt” methods can be generalized to the so-called “Lin-Kernighan” methods (yes, the same Kernighan from the early days of Unix). There are many other possibilities. A couple of seminal references are: • Lin, S. (1965) Computer Solutions of the Traveling Salesman Problem. Bell System Technical Journal 44(10): 2245–2269. • Lin, S. and Kernighan, B.W. (1973) An Effective Heuristic Algorithm for the Traveling Salesman Problem. Operations Research 21(2): 498–561. You could also choose to work with partial states–that is, states which are not a tour. Your successor function would have to include adding cities to the tour, and you would need to test that potential solutions are indeed tours. The state space will get very big, very fast. After all, this problem is NP-hard. For what it’s worth, this problem can also be tackled systematically using A* with a heuristic based on minimal spanning trees (See exercise 3.30). You might consider implementing both of these and comparing their performance. Check out http: //www.tsp.gatech.edu/ for example TSP problems. 6. Apply local beam search with k = 2 and k = 3 to the “polygon world” pathfinding problem from the previous homework (like AIMA 3.31). Make up different configurations to test local beam search against basic hill climbing. ANSWER: Left as an exercise. Be sure to show the current state(s), the possible successors, and their costs, at each step of the algorithms.

3...