Page 6: Heuristic Solutions

Unit 5, Lab 1, Page 6

TG and solutions need to be checked. –MF, 12/19/18

On this page, you’ll learn that even for unreasonable time problems, there can still be reasonable time “close enough” solutions.

AAP-4.A.6, AAP-4.A.8, AAP-4.A.9

If a problem can be solved in exponential time, there might be a different algorithm that can do it in polynomial time (that is, more quickly), but some problems can’t possibly be answered in polynomial time. It’s important to recognize that an exponential time algorithm still solves a problem correctly; it just takes a unreasonably long time (perhaps even hundreds of years for some inputs, for example).

Exponential time algorithms can sometimes be replaced by heuristics, which are polynomial-time algorithms that don’t solve the problem exactly, but give a good enough approximation. But heuristics are useful only for certain kinds of problems.

AAP-4.A.2

  • A decision problem is a problem with a true/false answer (for example, “is 5,825,496,221 a prime number?”).
  • An optimization problem is one with the goal of finding the best solution among many (for example, “what’s the best school schedule to place every student into as many of their requested classes as possible?”).
  1. For which kind of problems (optimization problems or decision problems) is a heuristic solution likely to be useful?

An example of a problem for which a heuristic solution is useful is the traveling salesperson problem: For a group of cities, what is the shortest route for a salesperson to visit every city and return to their home city? This is good case for heuristics because:

  1. It’s clear that there must actually be a shortest route.
  2. There is no known polynomial time algorithm for this problem. (Most computer scientists think that it’s not possible to write one.)
  3. There is a possible heuristic: pick a path at random, then try to improve it by swapping two cities repeatedly until you can’t make the path better with such small changes.

This heuristic is called “hill climbing” because you’ll find the best nearby path (the top of a hill), but there might be a higher hill (a better path) further away.

Can All Decision Problems Be Solved?

As it turns out, not all decision problems (true/false questions) can be solved with an algorithm.

AAP-4.B.1, AAP-4.B.2, AAP-4.B.3

A decidable problem a decision problem for which it’s possible to write an algorithm that will give a correct output for all inputs.

An undecidable problem is the opposite. It’s not possible to write an algorithm that will give a correct output for all inputs—even though it might be possible for some of them.

The question “Is the integer even?” is an example of a decidable problem because it’s possible to write an algorithm that will determine whether any integer is even.

The question “Will this computer program that takes an input always eventually report a result?” is an undecidable problem. It’s possible to write such a checking algorithm that would be able to say for some programs with some inputs whether they will report a result or get stuck in an infinite loop and never report. But it turns out that it’s not possible write a checking algorithm that will work for any program with any input. (You can see a proof that no such checking algorithm—for a computer or a person—can be written in Lab 4.)

  1. Talk with Your Partner What does it mean for a problem to be undecidable?