Assignment 1 Solution

(2 points) Solve the problem of finding a route from Timisoara to Bucharest using the various uninformed search strategies (both tree-search and graph-search variants) discussed and report statistics (number of expansions and solution cost). See the slides for the Romania map. The accompanying code has implementations for several search strategies, but not all, e.g. iterative deepening is not implemented (you should implement it).












(2.5 points) Use the straight-line heuristic function (see slides) to solve the Romania route problem (starting from Timisoara going to Bucharest) efficiently using A* TreeSearch and A* GraphSearch. Report statistics. Draw (or print out) the final search tree, and add at each node its path cost value (g), the heuristic function value (h), their sum (f=g+h), and the order of expansion, e.g. the root will be 0, then the next node expanded will be 1, etc.



You can solve this by hand on paper, or create a PrintTree method which takes the list of all created (search-tree) nodes and prints them in a nested form, e.g.




Timisoara(g=0.0, h=329.0, f=329.0) order=0

Arad(g=118.0, h=366.0, f=484.0) order=3

…




Lugoj(g=111.0, h=244.0, f=355.0) order=1

…







3. (2 points) Consider the following problem:




Three missionaries and three cannibals seek to cross a river, say from the left bank to the right bank. A boat that may be navigated by any combination of one or two people is available on their side of the river. If cannibals outnumber the missionaries on either side of the river at any time, the cannibals will indulge in their anthropophagic tendencies and do away with the missionaries. Find a sequence of boat trips that will permit all the missionaries and cannibals to cross the river safely.




Code this problem. Partial code provided. You should fill in the TODO parts.




Solve the problem using the various uninformed search control strategies provided.













(2 points) Consider the following problem (Water Jugs Problem). You have three jugs, measuring 12 gallons, 8 gallons, and 3 gallons, and a water faucet. You can fill the jugs up, or empty them out from one another or onto the ground. You need to measure out exactly one gallon.



Consider a variant of the Water Jugs Problem in which we are interested in minimizing the amount of water that must be poured. Filling the large jug when it is empty requires pouring 12 gallons into it. Likewise, transferring water from a full large jug into an empty small jug requires pouring 3 gallons. A lazy person might not mind a longer solution to the problem if it in fact reduced the amount of water they had to heft and pour. Attempt to solve the problem using the various uninformed search control strategies provided and report statistics.







(1.5 points) Devise a heuristic function for the missionaries and cannibals problem. Then, solve the problem using that heuristic and report statistics.