HOMEWORK (chapter 3: uninformed search)
Q-1: Give a complete problem formulation for each of the following.
Q-2: Answer the followng questions:
- The map coloring problem: Using
only four colors, you have to color a planar map in such a way that no
two adjacent regions have the same color.
- The monkey-and-banana problem: A
3-foot-tall monkey is in a room where a banana is suspended from the
8-foot ceiling. He would like to get the banana. The room contains two
stackable, movable, climbable 3-foot-high crates.
- There are an empty 3-gallon jug and an empty 5-gallon jug. The jugs can be filled from a fountain of water, water can be poured between the two jugs, and the jugs can be emptied. The problem is to fill one of the jugs with exactly 4 gallons of water.
- The missionaries and cannibals
problem is usually stated as follows. Three missionaries and three
cannibals are on one side of a river, along with a boat that can hold
one or two people. Find a way to get everyone to the other side without
ever leaving a group of missionaries in one place outnumbered by the
cannibals in that place.
- What is the difference between tress search and graph search?
- What is the preferred uninformed search algorithm if we know the length of the path?
- What is the difference between breadth-first search and uniform-cost search?
- Under which conditions is depth-first search complete?
- What are the major difficulties of bidirectional search?
Q-3: Apply breadth-first and depth-first graph search algorithms
separately to the above water-jugs problem. Is the solution found by
depth-first search optimal?
Q-4: Apply bi-directional search to the 8-puzzle. Is the first solution found by bi-directional search guaranteed to be optimal?