## 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 state is a clique.
• A operator on clique Z is to add a vertex V that is connected to all the vertices in Z, and that is later than all of Z in the ordering of vertices. For instance, if Z is the set { A,D } then the possible operators are adding E, adding G, and adding H.
• The start state is the empty set. (The operators on the empty set allow you to add any single vertex.)
• The goal state is a clique of size K.

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?

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.
• A state is a stack of queries.
• An operator on a state S does the following: It pops the query Q off the top of S; finds a rule R whose head matches Q under variable bindings B; pushes all of queries in the tail of Q onto S from end to beginning; and applies bindings B to all the queries in S.
• The goal state is the stack containing only the top-level query (the user's query).
• The end state is the empty stack.
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
• Pop p(a,W) off the stack
• As usual, rename the variables in the rule to be X1 and Y1.
• Match the query p(a,W) with the head of the rule p(X1,b) under the bindings W=b, X1=a.
• Push the tail of the rule onto the stack and apply the bindings.
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:

```r(X,X).
r(a,b).
r(b,c).
s(b).
s(c).
t(a,a).
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).''