'Milk Pitcher problem designing a A* heuristic

I'm trying to come up with a good heuristic value (h) for the following milk pitcher variant: we define n pitchers with volumes e.g. [1,2,3,4,6] and then a final "infinite" pitcher giving us n+1 pitchers, and then a goal state to reach x (e.g. 61 for this problem).

Liquid can be transferred from any pitcher to any other pitcher (following the volume constraints), including to and from the infinite pitcher, to return the shortest path from the empty state to the goal state where the infinite pitcher contains the goal amount.

For example in this problem the minimum number of steps is 22 ((10 * 6)+(1 * 1))*2.

I am struggling coming up with a good heuristic for this problem, I think the infinite jug is throwing me off. Any suggestions?

algorithma-starheuristics


Sources

This article follows the attribution requirements of Stack Overflow and is licensed under CC BY-SA 3.0.

Source: Stack Overflow

Solution Source

Related Questions