CSE 630 Homework 2
Jason Kim


1. -1: Checkers: As stated in the textbook, Bidirectional Search has the hardest time with a large set of goal states.
		     However the example in the book was using chess, which has a much more complex 
		     moving system than Checkers.  Still with a large set of goals, the algorithm would not be able
		     to work efficiently, searching backwards from the goal and forwards at the same time.  Thus,
		     Bidirectional searches don't really work out for a game like checkers.
   
   -2: The Kevin Bacon Game:  Since the Bacon Numbers game uses a Breadth First Search 
	 				which is part of the Bidirectional Search, you can go ahead
					and use a Bidirectional search and it will probably still work.
					The way the Bacon Numbers game works is by using an actor as a start
					and Kevin Bacon as the goal and finds the shortest path between them by linking actors
					with movies as paths.  Bidirectional Search can easily do that.

					

2.  A) I would use a Depth First Search, as since the links only work one way to the goal.
    B) Expand(node, problem)
    C) No, because Hueristic searches deal with informed searches where paths are already known.

3.  
Variables 
S = Small Disc, L = Large Disc, M = Medium Disc
1 = Peg 1 2 = Peg 2 3 = Peg 3
Constraints
L > M > S, a disc that is greater than another cannot be on top of a disc that is lesser than it.
Operators:
Move(Disc,Peg)- moves a disc to desired peg within the constraints.

Hanoi Starting State
-------------
| S |   |   |
| M |   |   |
| L |   |   |
-------------

Reachable States in 3 Moves
-------------           -------------
|   |   |   |           |   |   |   |
|   |   | S |           |   | S |   |
| L |   | M |           | L | M |   |
-------------           -------------

Goal State
-------------
|   |   | S |
|   |   | M |
|   |   | L |
-------------


4.
-1   A
   / | \	
  D  P  R
 /  / \ /
 E   Z  F
/   /
Q  E
  /
 Q

-2. D, P, R

-3 R

-4 A

-5 R