CSE 473: Introduction to Artificial Intelligence

Autumn 2009

Hw Assignment 3 (Exercise): Due Wednesday, October 21 in class: 20 points

  1. (11 pts) Given the 8-Puzzle search problem we started in class, generate the full search tree up to solution for each of the search types below. At each node of the tree, show the state of the puzzle and give the values for f, g, and h in that order. Also use circles with numbers inside (1, 2, 3, ...) to show the order of the search. Put a box around the f value, so it stands out (or make it bold if you are typing). Here are templates for your answers.

    1. (5 pts) A* search where g=depth and h=h1 (number of misplaced tiles). For this problem, you will find you have a choice of states with the same f-value (5) that are both on OPEN. For consistency of answers, choose the one with the blank in the top middle position and continue down its path when you again have the choice of 2 states with f-value 5. You don't have to include any moves that reverse the previous move, as we know they will not lead to a shorter path.

    2. (6 pts) greedy search where g=0 and h=h2 (sum of Manhattan distances of each misplaced tile to its proper spot). You should see that the Manhattan distance works better than the number of misplaced tiles in guiding the search.

  2. (3 pts) Try the applet at U of Rochester link. For at least 3 different problems (use create to start a new problem) try each of the 5 search techniques and record the values it shows for 1. (length of) solution and 2. (number of) nodes. Then compute the averages for all 3 (or more) problems. State your conclusions.

  3. (6 pts) In the Traveling Salesman Problem, the goal is to find the shortest tour through a set of cities in which each city is visited exactly once. A tour starts at one city (we'll say any one), visits every city once, and ends back at the first one. Hill climbing algorithms produce rough solutions to problems, usually much faster than a big search. We'd like to convert the Traveling Salesman Problem to a hill-climbing problem, which could then use the function HILL-CLIMBING in Figure 4.2 (of addendum) to solve. To do this we need a complete-state formulation of the problem, an objective function, and a method for determining new states from given ones.

    You are given a set CITIES of N cities and you know for each pair Ci and Cj, whether there is a road between Ci and Cj and the distance D(Ci,Cj) between them if there is a road. (We'll assume at most one road between any pair.)

    1. (3 pts) Define the set of states S, the start state s0, and the objective function f that takes in a given state s and produces a number indicating the goodness of s based on path length (here the shorter the path, the better the goodness).

    2. (3 pts) Devise a method to take one such state and produce multiple children states by doing something to the given one. HINT: the state defines a path. You can think of it as a string of cities or list of cities. What kinds of things can you do to one path to produce other paths that might be shorter? For example, you could swap 2 cities. Note: this is a thought question.