How can I define a heuristic function for water jug?

Question

I am trying to put a water jug problem into a heuristic function but I am finding some problems.

There are 2 jugs, one that can hold 5(x) and others that can hold 3(y) gallons of water. The goal is (y,x)=(0,4).

I can't figure out how to put it into a heuristic function and also I have a doubt about the number of states. If I admit the actions (fill one from the faucet, empty one to the drain, and pour from one to the other until either the receiving jug is full or the pouring jug is empty), there are 15 possible states, but if I consider all the possibilities regarding the number of gallons, there are 24 possibilities. Is that correct?

(0,0)

(3,0)(0,5)

(0,3)(3,5)(3,2)

(3,3) (0,2)

(1,5) (2,0)

(1,0) (2,5)

(0,1) (3,4)

(0,4)

I think that the Heuristic function for this problem can be defined as:

h(x,y) = (x * 5) + (y * 3)

Can anyone explain it to me, please?

max(estimate_from_parent - action_cost, estimate_from_this_node)

Answer 1

The heuristic function is the function that maps from problem state descriptions to measures of desirability, usually represented by a number. In thinking of a heuristic function, it's often useful to find a constraint that makes your problem harder and then loosen it. This facilitates coming up with a heuristic that is admissible and consistent because your heuristic will be a best-case estimate.

You want four gallons in bucket x. So the closer you are to having four gallons in bucket x, the closer you are to your goal state, and the lower the value of your heuristic function should be (since it's an estimated cost). The lowest value of your heuristic function, then, should occur when there are four gallons in bucket x.

The heuristic function you proposed here:

h(x,y) = (x * 5) + (y * 3), is lowest at (0,0). As this is not your goal node, this isn't likely to be a good heuristic function.