1
$\begingroup$

As stated in the title I'm wondering why do heuristic functions only approximate the real value of the cost? I understand it can never overestimate, but can it ensure the cost is accurate?

$\endgroup$
  • $\begingroup$ For completeness, the heuristic function only has to underestimate the cost. A good heuristic function will estimate a cost that is close to the real cost. $\endgroup$ – George Dec 18 '14 at 17:46
  • $\begingroup$ @George So it can always finds a solution, correct? Is that what you mean by your comment? :) $\endgroup$ – orange Dec 18 '14 at 17:54
4
$\begingroup$

If you create a heuristic that returns the exact cost for each node in the search tree, you can find the optimal solution easily: Start at the initial state and generate all successor states. Take the state with the best heuristic value and repeat, until you find the goal state. Because the estimated cost (from the heuristic) for each node in the search tree is equal to the actual cost, you never make a wrong decision.

Unfortunately for most problems constructing such a heuristic would mean that for each node to evaluate you calculate the solution and then return the cost of the solution. Thus you already solve your problem inside the heuristic function.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.