# Why are heuristics a disadvantage for decidable problems?

I'm reading Introduction to Artificial Intelligence by Ertel.

This line has me stumped from the textbook (page 102):

For decidable problems such as the 8-puzzle this means that the whole search tree must be traversed up to a maximal depth whether a heuristic is being used or not.

And decidable ca be defined thus:

an algorithm that can and will return a Boolean true or false value (instead of looping indefinitely)

Why can't the program return if it encounters the goal state before it has traversed the entire tree? What am I missing?

In case context is important, this is the preceding sentence:

In closing, it remains to note that heuristics have no performance advantage for unsolvable problems because the unsolvability of a problem can only be established when the complete tree has been searched through.

See page 102.

It says elsewhere in the book that heuristics often reduce computation dramatically for “solvable problems”! Is there a difference between “decidable” and “solvable” problems that's relevant here? It's not explained why heuristics are good for “solvable” problems and bad for “decidable” ones.

• I don't think you're providing enough context from the textbook. What context you've provided doesn't say what you say it says... it says that "heuristics aren't going to be useful for unsolvable problems" (duh, unsolvable), and that, for decidable problems, heuristics aren't going to save you from traversing the whole search tree. – Robert Harvey Feb 15 '15 at 22:58
• I've added a link to the book. Yes, the sentence about "unsolvable problems" is straight forward. But, why must you traverse the entire game tree of 8-puzzle if you use heuristics. Couldn't you just stop when you get the state your looking for? – nullpointer Feb 15 '15 at 23:05

A problem is solvable iff a solution exists.
A problem is decidable iff we can tell whether the problem is solvable or not, i.e. whether a solution exists.

The 8-puzzle is not always solvable, but it is decidable since if a solution exists, we know it will take at most 31 single-tile moves. So to decide whether a given 8-puzzle is solvable, we must find any solution. If no sequence of moves with max length of 31 solves the problem, we know that this puzzle is unsolvable.

Now we can restate this in terms of whether the problem is solvable:

• For a solvable problem, we only need to find one solution to prove that it's solvable. Here, heuristics can speed up finding a solution.

• For an unsolvable problem, we have to prove that not a single solution exists. Since a heuristic will not lead to a solution for an unsolvable problem, we have to investigate the whole game tree to be sure that it contains no solutions. Since we have to investigate every possible game state, a heuristic will not matter (all a heuristic does is prioritize promising moves). Since a heuristic adds a computational cost, using a heuristic will be a net loss for unsolvable problems.

The funny thing is that we do not generally know a priori whether a given problem is solvable.