Water jugs heuristic function for A*

For the cl开发者_Go百科assic water jugs search problem, even for more than three jugs, which are some admissible functions that can be used for the A* search algorithm?

Edit:

I know about http://www.dave-reed.com/csc550.S02/HW/HW4.html , but that function clearly is not consistent.

---

There are two general methods how to design an admissible heuristic. Both work by solving a simpler problem. The heuristic value is then the distance to the goal in the simpler problem.

1. Relaxation

The problem is simplified by forgetting negative effects. For example, if you once had one quart of water, it will be always available when needed.

A Tutorial on Planning Graph Based Reachability Heuristics.

2. Abstraction

The problem is simplified by ignoring some details. For example, a simpler goal could ignore the amount of water in the last jug at the end.

You could store the precomputed heuristic values in a pattern database. The key would be the simpler abstract problem and the value would be the heuristic value.

A formal introduction.