Artificial Intelligence: Problem Set 4: Solutions

Problem 1:

A clique Z in an undirected graph is a set of vertices such that every two vertices I,J in Z is connected by an edge. For instance, in the graph shown below, the set { B,C,F,G } is a clique because the graph contains all of the edges BC, BF, BG, CF, CG, and FG.

The problem of finding a clique of specified size K in a graph can be formulated as a state space search as follows: Impose a specified ordering on the vertices in the graph (e.g. alphabetical). Then

A. Is this state space a tree?
Answer: Yes it is. Because of the restriction that the vertices are added according to a fixed order, any given state can be created from the start state only by the operations of adding the vertices in order. For example, the state { A,D,E } can only be created by the three operations ``Add A; add D; add E'' in that order.

B. What is the maximum branching factor?
Answer: The maximum branching factor is attained at the root, and is equal to the number of vertices in the graph (8 in this example.)

C. What is the distance from the start state to the goal states, if any exist?
Answer: A goal state with K vertices is the result of K operations. Hence, the distance from the start state to the goal state is K (4 in this instance.)

D. Give an upper bound on the number of states in the state space.
Answer: A crude bound: As the branching factor is bounded by V (the number of vertices in the graph) and the depth of the tree is K, the number of states is less than VK.

A better bound: A set of size V has C(V,I) = V!/I!(V-I)! subsets of size I. Hence since every state in the state space is a subset of the graph of size at most K, the size of the state space is at most the sum over I from 0 to K of V!/I!(V-I)!.

E. Suppose that we search the space using a depth first search. What is the first solution found to the problem ``Find a clique of size 3'' in the above graph?
Answer: { A,D,E }.

What is the first solution found to the problem ``Find a clique of size 4'' in the above graph? \\ Answer: { B,C,F,G }.

Problem 2

For Prolog programs with no cut operator, the Prolog interpreter can be viewed as doing a depth-first search through the following space. For example, suppose that the current state is the stack [q(a,W), p(a,W)] and there is a rule
p(X,b) :- r(X,Y), s(Y), t(X,Y). Then one operator on the state is the following The new state is the stack [q(a,b), t(a,Y1), s(Y1), r(a,Y1)].

Note: The entire procedure above is one operator in the search space.

A. Suppose that there are P predicates, a maximum of R rules per predicate, and a maximum of T subqueries in the tail of a rule. What is the maximum branching factor in the search space?

Answer: The operators possible in any given state correspond to the rules that match the query at the top of the stack. Hence, the branching factor is R.

B. Suppose we have the following Prolog code:

t(X,Y) :- s(Y), r(Y,X).

p(X,Y) :- s(X), r(Y,X).
p(X,b) :- r(X,Y), s(Y), t(X,Y).
Draw the search space corresponding to the top-level query ``?-p(a,Z).''