Water jugs heuristic function for A*

views:

331

answers:

+1 Q:

Water jugs heuristic function for A*

Hi all,

For the classic 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.

+1 A:

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.

Ivo Danihelka 2010-04-20 20:44:53

Thanks. These are also shown in AIMA 2nd edition, http://aima.cs.berkeley.edu/2nd-ed/. They apply and are effective to the puzzle problem or finding a route form A to B, but these principles shownto be sterile up to now for the jugs problem (personal opinion).

lmsasu 2010-04-21 16:20:13

To apply the heuristics to the jug problem,read about planning in AIMA. By expressing the actions as a set of preconditions and effects, you could apply any planning algorithm on the problem.

Ivo Danihelka 2010-04-21 17:01:46

ansaurus

tags:

views:

answers:

Water jugs heuristic function for A*

1. Relaxation

2. Abstraction

related questions