Back to Discover
🔢

Travelling salesman problem

math Maturity 11-13

Imagine you must visit many towns.

Illustration of an unsolved travelling salesman problem.svg
Illustration of an unsolved travelling salesman problem.svg
You want to go fast. You need the shortest way. You must go to each town once. Then you go home. This helps us plan trips. It even helps make tiny chips.
GLPK solution of a travelling salesman problem.svg
GLPK solution of a travelling salesman problem.svg
Can you find the best way?

58 words
🖼️ Images & Media (11)
File:Illustration of an unsolved travelling salesman problem.svg
Illustration of an unsolved travelling...
File:GLPK solution of a travelling salesman problem.svg
GLPK solution of a travelling salesman problem.svg
File:William Rowan Hamilton painting.jpg
William Rowan Hamilton painting.jpg
File:Weighted K4.svg
Weighted K4.svg
File:Bruteforce.gif
Bruteforce.gif
File:Branchbound.gif
Branchbound.gif
File:Nearestneighbor.gif
Nearestneighbor.gif
File:Creating a matching.svg
Creating a matching.svg
File:UbMjAyAmQrSwtP0gdeKe matchingshortcut.svg
UbMjAyAmQrSwtP0gdeKe matchingshortcut.svg
File:Showing a step of the two-opt heuristic.svg
Showing a step of the two-opt heuristic.svg
File:AntColony.gif
AntColony.gif
Up Next
🔢
Held–Karp algorithm
Math
→
More to explore

✨ What else?

Related topics you might enjoy

Held–Karp algorithm 0% Hamiltonian path 0% Hamiltonian path problem 0% NP (complexity) 0% Clique problem 0% NP-hardness 0%

🔬 Go deeper

More advanced topics to explore

Hamiltonian path NP (complexity) NP-hardness Computational complexity theory

🪜 Step back

Simpler topics to build understanding

Held–Karp algorithm Hamiltonian path problem Clique problem Assignment problem
📚 Content adapted from Wikipedia | Readability: FK 12.8 | Vital Level 5