Chapter 3

Q1. Give the initial state, goal test, successor function, and cost function for each of the following. Choose a formulation that is precise enough to be implemented.

f. You have to color a planar map using only 4 colors, in such a way that no two adjacent regions have the same color.

g. A 3-foot-tall monkey is in a room where some bananas are suspended from the 8-foot ceiling. He would like to get the bananas. The room contains 2 stackable, movable, climbable 3-foot-high crates.

h. You have a program that outputs the message “illegal input record” when fed a certain file of input records. You know that processing of each record is independent of the other records. You want to discover what record is illegal.

i. You have 3 jugs, measuring 12 gallons, 8 gallons, and 3 gallons, and a water faucet. You can fill the jugs up or empty them out from one to another or onto the ground. You need to measure out exactly one gallon.

Q2. For the following tree, list the order in which the nodes are visited for the following three search strategies

a. Depth-First Search

b. Depth-First Iterative-Deepening Search

c. Breath-First Search

Q3. Consider the following road map of cities: 

Each city has a road connecting it to another city.  The numbers on the road indicate how long it takes to travel between cities.  Suppose you live in city A.  You want to plan a trip that visits each city only once that starts and ends at home.  For example, the trip ABDCEA (meaning you go from city A to B, then to D, etc) is one such path that would take you 17 hours to follow.  Your goal is to choose a path that minimizes the time spent traveling.  (Note: this is called the Traveling Salesman Problem, described on pg 68)

d. Formulate the state space for the problem

e. Draw a diagram of the complete state space, describing what the actions are

f. Describe a breath first search algorithm, and find the shortest trip from A to A that visits all cities.

g. Compare the time & space requirements for Depth-First search & Breadth-First Search on this problem.

h. Would uniform-cost search work well with this problem?