Exercise 1        Name __________________        Score __/14

  1. A farmer has a goat, a cabbage and a wolf to move across a river with a boat that can only hold himself and one other passenger. If the goat and wolf are alone, the wolf will eat the goat. If the goat and cabbage are alone, the goat will eat the cabbage.
  1. (5) Draw by hand the state space for the problem starting on the West side of the river and crossing to the East side.

The problem constraints are:

  1. The farmer must be same side when wolf = goat or goat = cabbage.
  2. No repetitions.

Include successor states that violate the problem constraints, that is the goat is alone with the cabbage or repetitions but designate as illegal (see notation below). Don't include states that violate requirement the boat can hold only two passengers (e.g. all four passengers cannot move from one side to another at once.

Notation:

Use a tuple to represent the side of the river each is located; for example (W, E, W, W) can represent the (farmer, wolf, goat, cabbage) locations. States that violate the problem constraints are (W, E, E, W) which is the goat is alone with the wolf. States that violate requirement the boat can hold only two passengers (e.g all four passengers cannot move from one side to another at once, that is (W,W,W,W) cannot become (E,E,E,E)).

     *R constraint violation due to duplicate node (e.g. (W,W,W,W) *R).

     *GC constraint violation due to goat-cabbage (e.g. (E,E,W,W)*GC)

     *WG constraint violation due to wolf-goat (e.g. (W,E,E,E)*WG).

                           (WWWW) _______________________________|_________________________________________
(EWWW)*GC*WG       (EEWW)*GC            (EWEW)                (EWWE)*WG
                                ___________|____________________________
                                (WWEW)                         (WWWW)*R
          _________________________|_____________________________________
          (EEEW)                       (EWEE)                       (EWEW)*R
______________|___________________   ___|__________________________________
(WEEW)*WG   (WWEW)*R      (WEWW)    (WWEE)*GC     (WWWE)        (WWEW)*R
____________________________|__   __________________|___________________
(EEWW)*GC (EEEW)*R      (EEWE)    (EWWE)*WG     (EEWE)*R      (EWEE)*R
____________________________|__  
(WEWE)    (WEWW)*R      (WWWE)   
___|_______________ ________|________    
(EEWE)*R  (EEEE)    (EWWE)*R  (EWEE)*R     
            GOAL                                                

  1. (2) What are the path results of depth-first search and breadth-first search?

DFS and BFS succeeds in locating same goal by examining path WWWW-EWEW-WWEW-EEEW-WEWW-EEWE-WEWE-EEEE.
 

  1. A 3-puzzle has 3 numbered tiles that can be moved right, left, up or down to place the tiles in some goal state. The initial S and goal G states are as shown.

                                      S =  1        G = 12
                                           32                 3

  1. (5) Assuming that we prefer to move the blank first right, the left, then up, and then down, draw the search space for this problem giving only legal moves from one state to another.

Notation:

*R designates repetition of a higher level node.
*G designates goal.

                                                 S
                                                 1
                                               32               
                 ________________________________________
                r                                                                         d
               1                                                                        31
               32                                                                        2
        _________________                   ____________________
        l    *R                      d                   r                                   u    *R   
         1                          12                 31                                  1
       32                          3                   2                                  32
                                 _______         _______  
                                 l *G      u *R   l  *R      u             
                               12          1       31          3             
                                 3        32         2          21         
                                                       __________    
                                                      l                  d  *R
                                                     3                  31
                                                   21                  2
                                      _______________
                                     r *R                      d 
                                    3                           23
                                    21                           1
                                                        _____________
                                                       r                       u *R   
                                                     23                       3
                                                     1                       21                     
                                        ________________ 
                                       l *R                        u              
                                     23                            2
                                       1                            13
                                                   ______________________
                                                  l                                         d *R
                                                 2                                         23
                                               13                                         1                        
                         ________________________ 
                        r *R                                      d *G
                         2                                           12                        
                       13                                             3

  1. What are the path results of depth-first search and breadth-first search?

DFS fails in examining the infinite search path of r‑l‑r‑l‑...

BFS succeeds in locating goal by examining path r‑d‑l.