Artificial Intelligence: Solution Set 1

Problem 1

A.
[] -----> [N] -----> [N,P] fail
     |          |
     |          ---> [N,S] fail
     |
     ---> [P] -----> [P,Q] (to cover R) fail
                |
                ---> [P,R] succeed.

B. A state is a set S of vertices together with an index vertex W. (We have left the index vertex implicit in the diagram above.) An operation on the pair < S,W > is the pair < S union {U}, X > if U covers W, S union {V} is an independent set, and X is the successor to W in the list of vertices. The starting state is < [], first vertex >. The goal state is a set that covers all the vertices in G.

C. Let N = |V|, the number of vertices. Then D = N and B < = N. If the condition that vertices are added to K in alphabetical order is enforced, then the size of the state space is certainly no more than 2N, the number of different subsets of V. As written the algorithm may rediscover the same state in many different ways, but the state space is certainly not larger than N!.

Problem 2

A.
[N,P,Q,R,S] -----> [N,Q,R,S] -----> [N,R,S] fail
                               |
                               ---> [N,Q,S] ---> [Q,S] succeed.

B. A state is a set S of vertices together with an index edge E. An operation on the pair < S,E > is the pair < S - {U}, F > if both ends of E are in S, U is an end of E, S - {U} covers G, and F is the successor to E in the list of edges. The starting state is < V, first edge >. The goal state is a kernel set.

C. The depth D is the number of edges, but the number of branch points on any path from the root is no more than N (since you can only remove N vertices). The branching factor is 2. The size of the state space is less than 2N