Artificial Intelligence Problem Set 4
Assigned: Oct. 27
Due: Nov. 3
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.
I am not going to try to draw this graph in ASCII. The edges are:
AD, AE, AG, AH, BC, BD, BF, BG, CF, CG, DE, DG, DH, 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?
B. What is the maximum branching factor?
C. What is the distance from the start state to the goal states,
if any exist?
D. Give an upper bound on the number of states in the state space.
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?
F. Propose a heuristic for ordering the vertices so as to find
a clique as soon as possible. How does your heuristic work on this example?
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?
Br.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).''