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