2

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.

Improve this question
2
  • 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. Commented Feb 15, 2015 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? Commented Feb 15, 2015 at 23:05

1 Answer 1

Reset to default
3

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.

Edit: This comment from another user(@esoteric) adds some additional clarity:

Try thinking of it as a statement of what happens in the worst case, especially given that half of the initial positions are unsolvable, and viewing the opportunity for early termination as a happy accident. Consider also that if the traversal is unlucky, it still may be required to walk the entire tree before finding a solution even if the instance is solvable. So, for > 50% of all instances, a full traversal is required. Given that, it's reasonable for the algorithm to expect to have to traverse the entire tree.

Improve this answer
10
  • Hold on though. By your definition, if a problem is decidable then we MUST know whether it is solvable or not. Thus, if it is solvable, heuristics will improve performance and if it isn't solvable then you wouldn't need to run any code (very efficient!). And if we don't know about solvability a priori doesn't that mean that decidability isn't even possible? Sorry for confusing the issue.. Commented Feb 15, 2015 at 23:43
  • 1
    Read his answer again. It says that "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." That means you have to check every sequence to determine that the puzzle is unsolvable, and a heuristic is not going to help you there. Heuristics are about finding solutions, not about not finding solutions. Commented Feb 15, 2015 at 23:45
  • @nullpointer No, if a problem is decidable then a computer can determine in finite time whether it is solvable or not. This involves running code. But if it turns out that the problem wasn't solvable, we would have been better off without using heuristics. Commented Feb 15, 2015 at 23:46
  • @amon OK. Shouldn't the book have therefore read: "For decidable problems such as the 8-puzzle [ if they turn out to be unsolvable ] this means that the whole search tree must be traversed up to a maximal depth whether a heuristic is being used or not." Commented Feb 16, 2015 at 0:37
  • 1
    @nullpointer Decidable refers to the problem statement in general; solvable to a specific instance. Your suggested addition to the sentence conflates the two. The original means the algorithm for determining the solvability of a given instance of a decidable problem is to traverse the entire decision tree. If it turns out to be solvable, sure, terminate early. But if it isn't, you won't know unless you traverse the whole tree. It's a contrast of the general cases of complete traversal versus heuristics. One can determine the solvability of an arbitrary instance; the other can't. Commented Feb 16, 2015 at 8:13

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.