## 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 B-F, C-H, D-E, D-G, F-H, G-H in GA are not matched in GB.
Edges J-Q, K-L, L-M, N-Q, N-R, P-R 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.