FGWC Heuristics

In this exercise, we will consider some possible heuristics for the "Farmer, Goat, Wolf, Cabbage" problem from the previous exercise.

These problems cannot be checked without giving away the solution, and so you will be given only one submission. Think about them (try considering how the heuristic values compare to the actual number of required moves in a few cases), and do your best. Don't worry if you get some wrong; just try to convince yourself of the reason.

Let n(s) be the number of objects (wolf, goat, cabbage) on the left side of the river in state s. For each of the following heuristics h(s), mark whether it is admissible or inadmissible.

h_1(s) = \text{max}(0, n(s)-1)
-- Admissible Not Admissible

h_2(s) = \text{max}(0, 2n(s)-1)
-- Admissible Not Admissible

h_3(s) = \text{max}(0, 3n(s)-1)
-- Admissible Not Admissible

Which heuristic would be likely to reduce the search the most, while retaining optimality of the answer?

-- h1 h2 h3