Verander de taal

Englishعربى中文DeutschEspañolFrançaisहिन्दीHrvatskiItaliano日本語PortuguêsRomânăРусскийSvenskaTürkçeTiếng Việt

Log in bij Mathigon

of

Nieuw account     Wachtwoord opnieuw instellen     

Graphs and Networks
Introduction
The Bridges of Königsberg
Handshakes and Dating
Planar Graphs
Map Colouring
The Travelling Salesman Problem
Scheduling Problems
Graphs in Everyday Life

Delen

Voortgang resetten

Hierdoor worden je voortgang en chatgegevens voor alle hoofdstukken in deze cursus verwijderd en kan dit niet ongedaan worden gemaakt!

Woordenlijst

Selecteer een van de zoekwoorden aan de linkerkant ...

Graphs and NetworksThe Travelling Salesman Problem

Leestijd: ~15 min

Let us think, once more, about networks and maps. Imagine that a delivery service has to visit ${tsn} different cities to distribute parcels. We can think of these cities as the vertices in a graph. If all the cities are connected by roads, this is a , so there are ${tsn}×${tsn}−12=${tsn*(tsn-1)/2} edges in total.

The delivery truck has to visit all cities, in any order. In the Königsberg bridges problem we wanted to find paths which travel along every edge exactly once. Now we want to find paths which visit every vertex exactly once. These paths are called Hamiltonian cycles.

There are countless different possibilities for Hamiltonian cycles in complete graphs. In fact, we can pick any vertex as starting vertex and then pick any of the remaining cities in any order:

Diagram coming soon…

Diagram Coming Soon…

In a graph with ${tsn1} cities, every Hamiltonian cycle must also contain ${tsn1} cities. Now,

    This means that, in total, there are ${tsnPaths(tsn1)} possible paths. A shorthand for this product is ${tsn1}! or ${tsn1} Factorial.

    You could imagine that it might not be possible to travel directly between two cities - without going via another city. In that case we no longer have a complete graph, and finding the number of Hamiltonian cycles, if they exist at all, becomes much more difficult.

    So far we have ignored the fact that some cities might be further apart than others. In real life, however, this is a very important consideration: we don’t just want to find any path but we want to find the shortest one. This is called the Travelling Salesman Problem. It has to be solved not only in transportation and logistics, but also when positioning transistors on microchips, to make faster computers, or when analysing the structure of DNA.

    One simple method would be to try all possible paths, finding the length of each, and then picking the shortest one. However we have just shown that, even with just ${tsn2} cities there are ${tsn2}! = ${factorial(tsn2)} possible paths. Once you have hundreds or thousands of vertices, trying all possible paths becomes impossible, even using powerful computers.

    Unfortunately, there is no more efficient algorithm to solve the travelling salesman problem. Instead, mathematicians and computer scientists have developed various algorithms that find good solutions, even if they may not be the very best one. These algorithms, which only give approximate solutions, are called Heuristics.

    Try rearranging the cities on this map, and watch how the shortest path between them changes. You can remove cities by tapping them, and you can add cities by clicking anywhere on the map (up to 8):

    The Greedy Algorithm (or Nearest Neighbour Algorithm) is very simple: you start in a random city and consecutively move to the closest city you haven’t visited before. Once you have visited all cities, you stop.

    Animation coming soon…

    You can show that, on average, paths found using the greedy algorithm are 25% longer than the shortest possible path.

    The 2-Opt Algorithm starts with a random possible path. Then you repeatedly pick two edges and swap them around if that would reduce the length of the path. You stop when you can't reduce the length further by swapping any pairs of edges.

    Animation coming soon…

    It turns out that, long before computers even existed, Nature had found a clever way to find optimal paths between different locations: in ant colonies.

    Ants want to find the shortest possible routes between their nest and possible food sources. They can communicate with each other through chemicals which they leave along their trail, and which other ants can follow.

    • The ant colony sends out many scouts which initially travel in random directions. Once they find food, they return, leaving behind a trail of pheromone.
    • Other ants tend to follow a trail when they find one, which leads them to food. On their return journey they deposit more pheromone, thus reinforcing the trail.
    • Over time, pheromone evaporates. The longer a path is, the more time it takes ants to travel along it, and so the pheromone has more time to evaporate. Short paths, on the other hand, can get reinforced more quickly, so their strength increases faster.

    Diagram coming soon…

    Ant Colony System (ACS) algorithms try to replicate this behaviour on computers, using many “virtual” ants. They can quickly find very good solutions for the travelling salesman problem.

    One particularly useful property of ACS algorithms is that they can run continuously and adapt in real time to changes to the graph. These changes could be caused by car accidents and road closures on street networks, or by traffic spikes to web servers on computer networks.

    The Travelling Salesman problem is NP-hard, which means that it is very difficult to be solved by computers (at least for large numbers of cities).

    Finding a fast and exact algorithm would have serious implications in the field of computer science: it would mean that there are fast algorithms for all NP-hard problems. It would also render most of Internet security useless, which relies on the fact that certain problems are believed to be very difficult for computers.

    Finding a fast algorithm to solve the Travelling Salesman problem would also solve one of the most famous open problems in mathematics and computer science, the P vs NP problem. It is one of the seven Millennium Prize Problems, each carrying a $1m prize.

    Archie