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. There are two constraints over the space of operators that your solution has to observe.