Imagine that you are planning a trip through several cities and want to find the shortest route to visit each city exactly once. What at first sounds like a simple task is actually one of the most famous puzzles in computer science: the Travelling Salesman Problem.
But don't worry, you don't have to be a math genius to face this legendary challenge. On the contrary! We grab our colorful blocks in Scratch and show how to solve this complex problem in a playful and creative way.
In this article, we take on the Challenge and tinker together on a solution. Are you ready to show the traveler the most efficient way and dive deep into the world of algorithms? Then let's get started
Understanding the problem – without an algorithm
Before we venture into an automatic solution, we want to take the problem into our own hands. For this I have prepared a small scratch project in which you can solve the challenge manually.
The task is simple: An owl must eat all the mice on the screen. It starts with the first mouse (with the number 1) and must also return there.
This is how it works:
- Start the project with the green flag.
- Click one by one on the mice in the order you think is the shortest.
- The owl follows your chosen route, and the total distance traveled is calculated and displayed.
Try it out right away!
You will quickly notice: Even with a few mice it is not so easy to find the shortest way. But how could the owl solve the problem automatically? This is exactly where you come into play as a tinkerer! Try to implement your own algorithm. As a starting point for your experiments, you can use the block If this figure is clicked at the owl. A click on the owl will then start your code.
The Hammer Approach: The Brute Force Method
After we have tried ourselves manually, we now want to teach the owl its first own strategy. We start with the most direct, but also the most stubborn method there is: Brute Force (in German: brute force).
The idea: Just try everything!
The logic behind Brute Force is impressingly simple: We let the computer systematically go through every single possible route and in the end simply remember the shortest one.
Imagine it as a combination lock: Instead of thinking cleverly, you just stubbornly try 0-0 and go through every single combination until the lock jumps open. That's exactly what we do here:
- The algorithm gradually creates and tests every possible sequence of mice. So it is not a huge list created in advance, but one combination after another is processed.
- For each individual order, the total distance of the trip is calculated.
- We keep a "best list" and always store only the shortest route found so far and the corresponding route.
But we allow ourselves a little optimization: The route 1 -> 2 -> 3 -> 4 -> 1 is exactly as long as the reverse route 1 -> 4 -> 3 -> 2 -> 1. So we can ignore half of all cases and save computing time.
Brute Force in action with Scratch
Enough of the theory! In this Scratch project, the brute force algorithm is implemented. After the start, click on the owl to start the automatic search.
You will notice that the owl does not fly off immediately. Instead, the calculation runs in the background. To save time, the countless paths are not visualized. Instead, pay attention to the second counter: It shows you live how long it takes the computer to calculate all the options.
As soon as the algorithm is ready, the counter stops, and the owl flies only the one, absolute shortest route. With the few mice in the example, the calculation is done in the blink of an eye. But what happens when we add more goals?
The limits of brute force
Brute Force has a huge advantage: the method guarantees that we always find the absolute shortest route. However, the disadvantage is enormous and often makes the approach useless for practice: the so-called combinatory explosion.
Let's look at a calculation example:
- With 10 mice it is already
(10-1)! / 2 = 181,440routes. Still feasible, but the second counter in Scratch will twitch significantly. - Bei 10 Mäusen sind es schon
(10-1)! / 2 = 181.440Routen. Immer noch machbar, aber der Sekundenzähler in Scratch wird schon deutlich zucken. - With 15 mice the number explodes to
(15-1)! / 2 = 43,589,145,600– over 43.5 billion routes!
Even if a modern computer could check one million routes per second, it would already need over 12 hours for only 15 mice. With 20 mice, we would already have a computing time of over 1,900 years.
Conclusion: Brute Force is a faithful but extremely slow working oce. For real applications (such as the route planning of a parcel service with hundreds of destinations), this method is absolutely unsuitable. So we need smarter approaches! And that's exactly what we'll look at in the next section.
Cleverer instead of stronger: The path of heuristics
We've seen: Although the brute force method is thorough, it's hopelessly slow for anything that goes beyond a handful of goals. In the real world, we can't wait years for a route planning. So we need a shortcut. And this is exactly where heuristics come into play.
A heuristic is basically a clever rule of thumb or an abbreviation that helps us find a good solution in short time. The crucial point is: a heuristic does not guarantee the absolute best, perfect, optimal solution. Instead, it provides us with a solution that is "good enough" for practice - and at lightning speed.
So we sacrifice the guarantee of perfection for a huge speed advantage.
Der Gierige Algorithmus (Greedy Algorithm)
Probably the simplest and most well-known heuristic is the Greedy algorithm. The name says it all, because his strategy is extremely short-sighted and, well, greedy.
The idea: From your current point of view always choose the mouse that is closest and that you have not yet visited.
Imagine it as at the buffet: You don't take what strategically best suits your entire menu, but simply what is right in front of your nose and looks the most delicious. You repeat this until your plate is full.
The Greedy Approach in Scratch
I also implemented this approach in Scratch. Click on the owl again to start the algorithm.
You will immediately notice a huge difference to the brute force method: the calculation is immediately completed. The owl flies away without any delay. But is this way also the best? Compare the distance found with the perfect solution from the brute force example.
The Pitfall of Greed
The greedy algorithm is lightning-fast, but his short-sightedness can be his downfall. A locally good decision (the next step is short) can lead to a bad overall solution globally. For example, if the owl follows a nearby mouse into a "dead end", it has to travel a very long way from there to the next mouse - a detour that a smarter algorithm would have avoided.
Conclusion: The Greedy algorithm is a fantastic way to quickly find a usable route, but it is rarely optimal.
Ein Ausblick: Was gibt es noch für schlaue Füchse?
Die Welt der Heuristiken ist riesig und faszinierend. Der Greedy-Ansatz ist nur der Anfang. Hier sind ein paar weitere, oft genutzte Verfahren, die noch bessere Ergebnisse liefern:
- 2-opt-heuristics: You start with any route (e.g. that of the Greedy algorithm) and then systematically try to improve the route by always putting two edges "over the cross" and see if the path becomes shorter.
- Simulated Annealing: An exciting approach that comes from metallurgy. The algorithm also allows "worse" trains at the beginning, so as not to get stuck in a local dead end. With time, he becomes "colder" and only accepts improvements.
- Ant Colony Optimization: This simulates the behavior of ants that leave traces of smell (pheromone) in search of food. Routes used by many "ants" get a stronger scent trail and thus become more likely for the next ant.
Maybe we'll take a closer look at one of these "chic" algorithms in a future post. For the time being, however, we have seen that it is often smarter to take a good shortcut than to stubbornly try every imaginable way.
NP-complete: The premier class of serious problems
Why is this problem, which sounds so simple, one of the hardest nuts that computer science has to crack? The answer lies in its complexity class: The Traveling Salesman problem is NP-complete.
But what does that mean? Let's just break it down:
- NP (non-deterministic-polynomial): This sounds complicated, but means something simple: If someone suggests a solution to you (e.g. "Here, take this route!"), you can check very quickly whether the solution is valid and does not exceed a certain length. Recalculating a given route is therefore easy.
- Complete: This is the crucial part. NP-complete problems are the “end enemies” in the world of NP problems. They are the most difficult among them. The special thing is: they are all related to each other. If someone would find a quick algorithm to efficiently solve just one of these problems (like the TSP), you could also quickly solve all the other thousands of NP-complete problems with this trick. That would be a scientific sensation and would change the world (and bring the discoverer a prize money of 1 million dollars).
What does this mean for our owl?
It means that to this day there is no known algorithm that is guaranteed to find the best solution in a realistic time once the number of mice grows. The computing time explodes – that's exactly what we saw with the brute force method.
Therefore, we are forced to avoid clever tricks and approximation solutions (heuristics) instead of waiting for the perfect but unattainable solution.
The grand finale: Your own algorithm lab
Theory is good, but trying it yourself is better! Now that we have looked at different solutions, it is time for you to become a researcher yourself. For this I have summarized all the ideas in a final Scratch project, a kind of algorithm playground.
In this lab you have full control and can put the algorithms against each other.
This is new:
- Choose your algorithm: Using a button at the bottom you can decide which method you want the owl to use: the manual control, the fast greedy algorithm or the slow but perfect brute force method.
- Become a level designer: The best thing at the end: You are no longer bound by my guidelines! Click on the "draw mice" button and place the mice with one click exactly where you want them.
- Compare the routes: The paths of the different algorithms remain visible, so you can compare the efficiency directly. With "clean" you create order again.
Your mission if you accept it
This lab is perfect for getting a feel for the strengths and weaknesses of the algorithms. Here are some ideas for your first experiments:
- The Greedy Trap: Can you draw an array of mice in which the Greedy algorithm chooses a visibly worse route than the brute force method? (Tip: Try to lure the owl into a "dead end" with a nearby mouse).
- The ideal case: Find an arrangement in which the Greedy algorithm randomly finds the perfect solution. What does such an order look like?
- The brute force limit: How many mice can you place before the calculation time of the brute force method increases noticeably? Find the point where you think: "Okay, this is taking too long for me now."
I'm curious to see what you find out!
In the end, the Travelling Salesman problem shows beautifully that computer science is often not about stubbornly finding the one, perfect answer. It is much more important to understand the problem and then choose the right, clever tool for the respective task. Sometimes "good enough" is infinitely much better than "perfect, but in a thousand years".
Leave a Reply