Homework 2
Search  

Assignment

1. Copy and modify the Python program of Figure 3.9 from class notes.

   Write a function to display the nodes in the fringe queue after calling INSERT-ALL. Hint: use the Node display() to display each node.

   Make minor changes to INSERT-ALL to perform breadth-first search.

   Add a cycle to the STATE_SPACE, for example, state C has as a successor state A. Verify that the cycle causes TREE_SEARCH to execute without terminating. Pressing Ctrl and C simultaneously will terminate Python execution.

    

2. Modify your program to implement Figure 3.13 on page 77.

   Verify correct operation for each of the cases with 1) a solution, 2) cutoff , and 3) failure.

    

3. Modify your program to implement Figure 3.19 of page 83. Verify that it correctly handles STATE_SPACE cycles. Hint: Use append to add the node STATE to the closed list and in to test if a state is in the closed list.
    
4. Use your program from c. to solve the vacuum world problem. Hint: one way to represent the state space of Figure 3.3 in Python is by a dictionary where the current state is a tuple:

   (location, A status, B status)

   and a list holds successor states for each action.

   [ (Suck,   (location, A status, B status)),
     (Left,    (location, A status, B status)),
     (Right,  (location, A status, B status))]

   For example:

   ('A', 'Dirty', 'Dirty') :
       [('Suck',  ('A', 'Clean', 'Dirty')) ,
        ('Left',   ('A', 'Dirty', 'Dirty')) ,
        ('Right', ('B', 'Dirty', 'Dirty'))]

5. Use your program from c to solve the following problem.

A farmer has a goat, a cabbage and a wolf to move across a river with a boat that can only hold himself and one other passenger. If the goat and wolf are alone, the wolf will eat the goat. If the goat and cabbage are alone, the goat will eat the cabbage.

Define the state space for the problem. Hint: Use a tuple to represent the side of the river each is located; for example ('W', 'E', 'W', 'W') can represent the (farmer, wolf, goat, cabbage) locations. Use a list of tuples for the successor states. Include successor states that violate the problem constraints, that is ('W', 'W', 'E', 'E') which is the goat is alone with the cabbage; don't violate requirement that the boat can hold only two passengers (e.g all four passengers cannot move from one side to another at once, that is ('W', 'W', 'W', 'W') cannot become ('E', 'E', 'E', 'E')).

Define successor_fn to return a list of states that do not violate the problem constraints.

Turn in

1. Cover page - Your name, date, and Homework 2 should be on the first page. Staple all pages together.
2. Printouts - Print the final Python programs for Assignment a-e and Shell executions showing solution path.