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.)