Artificial Intelligence Problem Set 5
Assigned: Nov. 3
Due: Nov. 10
This problem set, like problem set 4, deals with finding a clique in a graph.
Recall that 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.
{\bf Problem 1:}
In problem set 4, we formulated the problem of finding a clique of specified
size K in a graph as a state space search in the following way: 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.
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:
An alternative to the problem of finding a clique of size K in graph
G uses hill-climbing, as follows: A state S is any set of K
vertices. The error function to be minimized is the number of pairs of
vertices in S that are not connected by an edge. The operator is
to swap one vertex in S with a vertex out of S.
For example, if K=4 and S is the set { A,C,E,F }, then the value of
the error function is 4, as none of the edges AC, AF, CE, or EF are
in the graph. The operators on S are
Swap A with B, giving { B,C,E,F }
Swap A with D, giving { D,C,E,F }
Swap A with G, giving { G,C,E,F }
Swap A with H, giving { H,C,E,F }
Swap C with B, giving { A,B,E,F }
and so on. (The above is not a complete list.)
A. Looking for a clique of size 4 in the above graph, if a
hill-climbing search starts with
{ A,C,E,F }, what are the possible next states in the search? (If
there are several tied for the best next move, list them all.)
B. Looking for a clique of size 4 in the above graph, find
a local minimum of the error function that is not a global minimum.
(Interpret "local minimum" here in the non-strict sense; that is,
a state where the error function is less than or equal to its value
at all its neighbors.)
C. If you are using this technique to look for a clique of size K
in a graph of size N, what is the size of the state space? (The exact
answer is best here, but I'll accept a reasonable approximation.)
What is the branching factor? What is the diameter of the search space?
(The diameter of a state space is the maximum distance between two states,
where the distance is the number of operators needed to turn one state into
another.)