Artificial Intelligence Qualifying Examination
August 23rd, 1999 -- 1-3pm
Below is a graph of eight nodes connected in a special way as indicated by the arcs. The task is to place the integers 1 through 8 in the nodes such that no two consecutive integers may be placed in immediately connected nodes. For example, if 2 is placed in the top node, neither 1 nor 3 may be placed in any of the three nodes below it. Ignoring reflections, there is only one solution.
a. How big is the space of candidate solutions? (5 points) b. Design a data structure for representing the problem as a state-space. Be sure to include node and edge representations, and specify the initial and goal states. In addition, describe the operator or operators that would be included. (15 points) c. Discuss the appropriateness of the basic search strategies in finding a solution. You should at least consider breadth-first, depth-first, uniform-cost search, greedy search and A* in your answer. You should develop admissible heuristics where necessary. (30 points) d. The problem can also be solved by constraint satisfaction. Describe a search strategy using constraint checking that will solve the problem. (20 points) e. Yet another way to solve the problem is called "heuristic repair" in which an arbitrary candidate solution (all integers assigned to nodes) is selected and iteratively altered until a solution is found. Discuss the differences between this strategy and the others discussed in b and c. (20 points) f. Which strategy out of all the ones you described is, in your opinion, the most human-like? Why? (10 points)
[Note there is no need to find the solution, but it may help your
discussions of the various strategies.]