AI: Solution Set 1
Problem 1.A
empty > S=W > S=W,T=X > S=W,T=X,U=Y > fail
 
 > S=W,T=Y > S=W,T=Y,U=X > fail

> S=X > S=X,T=W > S=X,T=W,U=Y > fail
 
 > S=X,T=Y > S=X,T=Y,U=W > S=X,T=Y,U=W,V=Z.

> S=Y > S=Y,T=W > S=Y,T=W,U=X > fail

> S=Y,T=X > S=Y,T=X,U=W > S=Y,T=X,U=W,V=Z.
Problem 1.B
The depth is at most N (exactly N, if there is a solution.) The branching
factor at the root is N. The size of the state space is O(N!) since
in a complete tree, each leaf would correspond to one permutation of
the vertices of G2.
Problem 2.A
empty > S=X > S=X,T=Y > S=X,T=Y,U=W > S=X,T=Y,U=W,V=Z.

> S=Y > S=Y,T=X > S=Y,T=X,U=W > S=Y,T=X,U=W,V=Z.
Problem 2.B
empty>A=J>fail

>A=M>A=M>A=M>A=M>fail
B=L B=L  B=L
C=N  C=N
 D=P

>A=M>A=M>A=M>A=M>A=M
B=L B=L B=L B=L B=L
C=N C=N C=N C=N C=N
D=Q D=Q D=Q D=Q D=Q
E=J E=J E=J E=J
F=K F=K F=K
G=R G=R
H=P
Problem 3.A
Edges BF, CH, DE, DG, FH, GH in GA are not matched in GB.
Edges JQ, KL, LM, NQ, NR, PR in GB are not matched in GA.
Total cost: 12.
Problem 3.B
There are many possible solutions, e.g.

1. Switch any two assignments. E.g. switch the assignment of B with the
assignment of F, to get
A > R, B > L, C > P, D > N, E > M, F > Q, G > K, H > J.

2. Switch any two consecutive assignments. E.g. switch the assignment of
C with the assignment of D.

3. Permute any three assignments. E.g. switch A,C,F to get
A > P, B > L, C > L, D > N, E > M, F > R, G > K, H > J.
There are two constraints over the space of operators that your solution has
to observe.

1. That the operator stays within the state space. E.g. "Change the
assignment of any vertex" would not be an acceptable operator,
because it generates assignments that are not in the specified state space.

2. That the class of operators spans the state space; that is, that any
state can be turned into any other state by a sufficient number of
operator applications. For example, "Switch the assignment of
any two vertices connected by an edge," will not work for disconnected
graphs. "Rotate the assignments around the list" will not work.
Solution (3) above will not work for graphs with only three vertices.