CODEWITHSUNDEEP
artificial-intelligence
user2713650
user2713650

Reputation: 99

When is one heuristic better than another?

I answered a question in which two heuristics were given for which A* was to be conducted to find a path from a start state to a goal state.

One of the heuristics found a path by expanding one node less - now for this reason, would we say this heuristic is better than the other?

Thanks!

Upvotes: 3

Views: 2599

Answers (1)

beaker
beaker

Reputation: 16791

We cannot say that one heuristic is "better" than another simply because it expands fewer nodes on one example of a problem. On the next example, the "better" heuristic might expand many more nodes than the other.

We know that a heuristic estimate can't go over the actual distance if it is to be admissible. In other words, the heuristic function must be constructed in such a way that it will never overestimate the distance to the goal under any circumstances.

It make sense, then, that if one heuristic gets closer to the actual distance without going over, it can be considered "better". If you used a heuristic that said that the distance between any two nodes was 1 (or any value less than the shortest edge length) you would end up expanding a lot of nodes. As the estimate gets closer to the actual distance you make it more likely that you can eliminate paths earlier.

There are, of course, other ways of defining "better", such as being easier to calculate.

Upvotes: 3

Related Questions