Home > Blockchain >  Heuristic function for water jug problem in A* search
Heuristic function for water jug problem in A* search

Time:10-17

I have questions about heuristic value. So, this is my puzzle:

volume of the 3 jugs = (10,6,5) initial state = (10,0,0) goal state = (8,3,0)

I'm choosing to use A* search for this puzzle. Is it something like h(x,y,z)=(x*a) (y*b) (z*c) as x y z is the volume of water in each jug and a b c is whether the jug is empty or not. If it is empty then equal to 0, if not then equal to 1. Because I'm getting confused when search through the internet. Can u guys help guide me? I'm new to AI too. Thanks.

CodePudding user response:

The most basic heuristic for A* is, don't follow branches that lead to duplicate states. You keep a Set of all previous states and don't follow a branch if the next state already exists in the set.

For your specific question, a possible heuristic function might be one that takes your next "state" (volumes of jugs) and subtracts the "goal" state and returns a delta score based on how close your next state is to your goal. The specific problem will have at most 6 branches from each unique state so you'd choose to follow the branch with the lowest delta score.

h(state)  = dot(abs(state - goal), 1 / volume)
  • Related