Beacon has a new job: plan the supply rover's route through the greenhouse domes.
Today the rover leaves the dock and visits three domes: A for tomatoes, B for beans and C for herbs.
"Easy," Comet says. "Beacon can try every order and pick the shortest."
Wren counts on his fingers. "Three domes give six orders. But mission control wants ten domes next year."
Nova projects a number that keeps growing until it fills the wall. "Ten domes give 3,628,800 orders," she says.
Comet's mouth falls open. "Maybe we need a smarter rule."
"A good rule," Wren says, "even if it is not always the best one."
To count the orders, multiply. Three domes give 3 times 2 times 1, which is 6 orders.
Each extra dome multiplies the count again. This kind of growth is called factorial.
| Domes to visit | Possible orders |
|---|---|
| 3 | 6 |
| 4 | 24 |
| 5 | 120 |
| 6 | 720 |
| 8 | 40,320 |
| 10 | 3,628,800 |
Algorithms with polynomial efficiency, like constant, linear, square or cube, run in a reasonable amount of time.
Algorithms with exponential or factorial efficiency are examples of algorithms that run in an unreasonable amount of time.
Some problems cannot be solved in a reasonable amount of time, because no efficient algorithm exists for them. Then people look for approximate solutions.
A heuristic is an approach that gives a solution that is not guaranteed to be the best. People use one when finding the best is impractical.
Wren suggests a heuristic for the rover: always drive to the nearest dome you have not visited yet.
Here are the drive times in minutes. The rover does not need to return to the dock.
| Drive | Minutes |
|---|---|
| Dock to dome A | 1 |
| Dock to dome B | 2 |
| Dock to dome C | 5 |
| Dome A to dome B | 3 |
| Dome A to dome C | 4 |
| Dome B to dome C | 8 |
With three domes, Beacon can check all six orders. With ten, the heuristic gives a good route fast, even if it is not always the best.
A decidable problem is a decision problem for which an algorithm can give a correct output for every input. "Is the number even?" is one.
An undecidable problem is one for which no algorithm can be built that always gives a correct yes or no answer.
Some instances of an undecidable problem may still be solvable. But no algorithm can solve all of its instances.
| Statement | True or false? |
|---|---|
| "Is the number even?" is a decidable problem. | ? |
| A heuristic always finds the best solution. | ? |
| An undecidable problem has no algorithm that is always correct for every input. | ? |
| If a problem is undecidable, none of its instances can ever be solved. | ? |
Big ideas today. Tomorrow you will find these algorithms far beyond the greenhouse.