Main content

## AP®︎/College Computer Science Principles

### Unit 4: Lesson 3

Solving hard problems# Using heuristics

AP.CSP:

AAP‑4 (EU)

, AAP‑4.A (LO)

, AAP‑4.A.2 (EK)

, AAP‑4.A.8 (EK)

, AAP‑4.A.9 (EK)

The hardest problems in computer science are those that run in superpolynomial time, doubling the number of steps required each time the input size increases—or more than doubling! Computers may be able to solve those problems for very small input sizes, but they very soon get to the point where it can take months or years of computing time to solve them.

Computer scientists use a different approach for solving those hard problems: instead of trying to find the

*perfect*solution, they try to find an*approximate*solution. A good answer is better than none at all.One way to come up with approximate answers to a problem is to use a

**heuristic**, a technique that guides an algorithm to find good choices. When an algorithm uses a heuristic, it no longer needs to exhaustively search every possible solution, so it can find approximate solutions more quickly. A heuristic is a shortcut that sacrifices accuracy and completeness.To better understand heuristics, let's walk through one of the most famous hard problems in computer science.

### Traveling Salesperson Problem

The traveling salesperson problem (TSP) asks the following question:

"Given a list of cities and the distances between each pair of cities, what is the shortest possible route that visits each city and returns to the origin city?"

For example, this diagram shows the shortest tour between 46 German cities:

The TSP problem was originally faced by traveling salesmen, but is actually relevant to many areas: routing data around a network, manufacturing microchips, observing locations with a telescope, and even sequencing DNA. In all those cases, we want a solution that will find an efficient path between multiple locations.

#### The brute force approach

TSP is a combinatorial problem, and that's what makes it so hard. The only way a computer can find the optimal solution is the "brute force approach": try every possible path between cities, measure the distance of each path, and pick the path with the shortest distance.

The visualization below generates four random cities, computes the possible paths, and highlights an optimal path. Click on the paths to see the possibilities it comes up with, or start over to try it with a new set of cities.

Do you notice that it always generates

*two*optimal paths? The paths look the same, but they're in reverse order. Technically, those are both optimal solutions, and a salesperson might choose one shortest path instead of the other for non-distance reasons.It doesn't take the computer very long to generate the possible paths for 4 cities—less than a tenth of a millisecond on my machine. It's fairly quick even for 5 cities, 6 cities, and 7 cities; you can try those yourself if you trust your computer. But the run time grows exponentially, so a few milliseconds soon becomes a few seconds.

Here's a table of run times for 4 to 11 cities on my machine:

Cities | Paths | Milliseconds |
---|---|---|

4 | 6 | 0.1 |

5 | 24 | 0.3 |

6 | 120 | 0.8 |

7 | 720 | 3 |

8 | 5,040 | 10 |

9 | 40,320 | 50 |

10 | 362,880 | 520 |

11 | 3,628,800 | 5,770 |

Notice the jump from 520 to 5770 at the end there? That's when I decided to take pity on my poor laptop and not go any higher.

At that rate, the computer would need about 2, start superscript, 53, end superscript milliseconds to compute the paths for the 46 German cities from the earlier diagram. That's about 6, start superscript, 42, end superscript years, way longer than the universe has even been in existence. Of course, there are computers that are more powerful than my laptop, but even a supercomputer that is 200,000 times more powerful would require 3, start superscript, 37, end superscript years.

So how was that path of 46 cities computed above? With a heuristic, of course!

#### Developing a heuristic

One way to come up with a heuristic is to consider how you yourself would approach the problem. Humans don't like wasting unnecessary effort on solving problems, so we often find shortcuts that get us to a good enough solution.

The visualization below shows 5 random cities. Propose a shortest path by clicking the cities, starting with the next city to visit from A. When you're done, find out how your path compares to the optimal path.

How did your path compare to the optimal path? What heuristics did you use to decide the order to visit the cities? Could the computer use that same heuristic?

Not all heuristics are equal, but they can all give us ideas for different ways to guide the computer to find a good solution more quickly.

#### The nearest-neighbor heuristic

A common heuristic for TSP is "nearest neighbor": the computer always picks the

*nearest*unvisited city as the next city on the path.Try it out in the visualization below. Now that we're using a heuristic, you can try it out with many more cities than before. Even 46 cities takes just a few milliseconds on my machine.

Impressive, right? Without a heuristic, we might have waited until the heat death of the universe to find the perfect solution. Now, thanks to a simple heuristic, we see results nearly instantly.

But, remember, a heuristic only gives an

*approximate*solution. For this particular heuristic, the solution will be, on average, about 25% longer than the shortest possible path. There are even times where the nearest neighbor heuristic will give the*worst*route.Computer scientists have come up with dozens of other heuristics for TSP, including "ant colony optimization", a heuristic inspired by the way that ants deposit pheromones along a path. For each heuristic, they analyze how close the heuristic gets to finding the perfect solution, how much time it takes, and how often the worst case happens.

### Heuristics everywhere

There are many problems besides TSP that benefit from heuristics.

Here are a few:

**Knapsack problem**: You have a knapsack and a set of item types, each with a weight and value. How many of each item can you pack so that the total weight doesn't exceed the limit and the total value is maximized? This type of problem shows up in many forms across different industries, like financial advisors selecting investments for a portfolio or factories figuring out the optimal way to cut up raw materials. One heuristic is to sort by value/weight ratio when selecting the next item to pack.

**Game-playing**: For a computer to beat a human at a game (or at least lose respectably), it must pick the move with the greatest chance of success. To really predict success, the computer needs to calculate the

*entire*game tree from current move to final move, anticipating all the moves the human could make in response. For the simple game of Tic-Tac-Toe, thats 362, comma, 880 possible situations, but for a more sophisticated game like Chess, that's 10, start superscript, 120, end superscript situations! Fortunately, heuristics like "minimax" help prune down the tree of possibilities.

**Facility location**: Imagine a supermarket chain that has 20 locations in a state and wants to build 5 warehouses to deliver food to the supermarkets. Their goal is to minimize costs and maximize delivery speed. The facility location problem is finding the optimal location for those 5 warehouses. This same problem is faced by web apps that want to distribute their backend servers to respond to user requests quickly. Heuristics like "local search" help narrow down the array of possible locations.

All of these are combinatorial problems, where a computer would need to search an exponentially growing number of combinations to find the optimal answer. Combinatorial problems are quite common in the real world, so both companies and computer scientists alike care deeply about finding heuristics that will give the best approximate solutions.

🙋🏽🙋🏻♀️🙋🏿♂️Do you have any questions about this topic? We'd love to answer—just ask in the questions area below!

## Want to join the conversation?

- On the wonderful TSP program you wrote, I changed 'value' on line 126 from 7 to 8 and the program worked properly, but when I changed it to 9, a message popped up that my Javascript is taking too long to run. Is there a run-time limit in the code itself? Or is that inherent in Khan Academy's Javascript language? Not a crucial question, but I would love to try some higher numbers and test the runtime!(9 votes)
- Great question!

We actually do have an infinite loop checker in our programming environment at Khan Academy. That's necessary since we evaluate the code in real time, and it is**very**easy to write an infinite loop on your way to writing a finite loop. An infinite loop typically freezes the browser tab, so we need to prevent that. Our loop checker wraps every loop in a timer. If the timer goes off before the loop is done, then we pop up the error. We have to stay on the safe side, so sometimes we might prevent code from finishing that would have with a few more seconds.

(The problem of knowing whether a program will ever stop is an "undecidable problem", described in the next article!)

You can try running the code on a webpage locally (save the code as tsp.html and open in a browser) and see how long it takes. You may need to restart your browser at some point, however!(18 votes)

- Thank you for a good explanation of what is heuristic. If this method was applied to finding a vaccine, which I am assuming it had to have been, since vaccines take from 5 to 15 years to find, and they came up with this in five months, how far away from an optimal solution is it? Is there a way to approximate this?(2 votes)
- Why is the TSP problem combinatorial (mentioned in the introduction of the problem), rather than permutatorial? Order matters in permutations, meaning that A-B-C-D would be different than D-C-B-A or A-C-B-D, right? Isn't this true in this problem?(1 vote)
- You're right. TSP depends on ordered combinations (permutations). The term "combinatorial" (I believe) comes from the branch of mathematics called "combinatorics", which deals with combinations and permutations. This is why you'll generally see "combinatorial" in the context of Computer Science problems(1 vote)

- how to calculate the mean distance between neighbours on a given dotted map?(1 vote)