Heuristic search
A farmer needs to move a hen, a fox, and a bushel of grain from the left side of the river to the right using a raft. The farmer can take o ne item at a time (hen, fox, or bushel of grain) using the raft. The h en cannot be left alone with the grain, or it will eat the grain. The fox cannot be left alone with the hen, or it will eat the hen. For ex ample, the farmer cannot move from one side x of the river to the other side y if it would mean leaving the fox and hen together on side x.
The farmer can load an item onto the raft, move the raft from o ne side of the river to the other, or unload an item from the raft. The farmer wants to move the items with the fewest number of tri ps across the river as possible, but does not care about how much ti me is spent loading or unloading.
1. Classify this problem using the primary representational dimen sions from lecture 2.(02 ¿Î¼þ-RepresentationalDimensions)
2. Represent this problem as a graph search problem. Be sure to i nclude and formally describe each component the graph search p roblem.
3. What is the forward branching factor for your representation fro m part (2)? Justify your answer.
4. Construct a non-constant admissible heuristic for this problem.
5. Argue that the heuristic from part (4) is admissible.
6.Implement your representation from part (2) and heuristic from p art (4) in Python 3 by editing the River_problem class in the pro vided riverProblem.py. We will run your code with the command python3 riverProblem_run.py. Your code must complete within 2 m inutes for full marks.1
Submit all of your code (including provided boilerplate files) in a single zip file.