Najdi nejkratší trasu, která projede všemi městy a vrátí se zpět. Vypadá jednoduše, ale počet možných tras roste astronomicky — přesně tady se potkávají dva principy z této série: kombinatorická exploze (příklad 1) a evoluční optimalizace (příklad 8). Níže je můj starší projekt, který TSP řeší genetickým algoritmem přímo v prohlížeči. Find the shortest route that visits every city and returns home. It looks simple, but the number of possible routes grows astronomically — this is exactly where two principles of this series meet: combinatorial explosion (example 1) and evolutionary optimization (example 8). Below is my older project that solves the TSP with a genetic algorithm right in the browser.
Co to jeWhat it is Klasická úloha: najít nejkratší trasu, která projede všemi městy a vrátí se zpět. Vypadá jednoduše, ale počet možných tras roste astronomicky rychle.A classic problem: find the shortest route that visits every city and returns home. It looks simple, but the number of possible routes grows astronomically fast.
Co zkusitWhat to try V aplikaci níže rozmísti města a spusť evoluci — populace tras se křížením a mutací generaci po generaci zkracuje. Sleduj, jak se nejlepší trasa postupně „narovnává".In the app below, place cities and start the evolution — a population of routes shortens generation by generation through crossover and mutation. Watch the best route gradually “untangle”.
Proč je to důležitéWhy it matters Bonus spojující dva principy série: kombinatorickou explozi (příklad 1 — tras je tolik, že je nelze projít všechny) a evoluční optimalizaci (příklad 8 — chytře hledáme dost dobré řešení). Přesně tak se řeší reálné logistické úlohy.A bonus joining two principles of the series: combinatorial explosion (example 1 — too many routes to try them all) and evolutionary optimization (example 8 — cleverly finding a good-enough solution). This is exactly how real logistics problems are solved.
Interaktivní vizualizér řešící problém obchodního cestujícího (TSP) pomocí genetického algoritmu. Celý výpočet běží v prohlížeči (bez serveru) a průběh optimalizace se kreslí v reálném čase na plátno. Aplikace se sama zastaví, jakmile se řešení přestane zlepšovat. An interactive visualizer that solves the travelling salesman problem (TSP) with a genetic algorithm. The whole computation runs in the browser (no server) and the optimization is drawn on a canvas in real time. The app stops by itself once the solution stops improving.
Nabízí čtyři varianty genetického algoritmu:It offers four variants of the genetic algorithm:
Cena trasy se počítá přes RMS (penalizuje dlouhé úseky víc než několik krátkých). K dispozici je 12 map: reálná česká města (20–192 měst, souřadnice S-JTSK) i geometrické testy (kruh, spirála, čtverec, trojúhelník, linka). Route cost is computed via RMS (which penalizes long legs more than several short ones). There are 12 maps available: real Czech cities (20–192 cities, S-JTSK coordinates) and geometric tests (circle, spiral, square, triangle, line).
Postaveno v TypeScriptu (Vite), kreslení přes HTML5 Canvas (HiDPI), výpočet běží na pozadí ve Web Workerech, bez runtime závislostí. Je to modernizovaný přepis původní Java desktop aplikace z roku 2006. Built in TypeScript (Vite), drawn with HTML5 Canvas (HiDPI), the computation runs in the background in Web Workers, with no runtime dependencies. It's a modernized rewrite of the original Java desktop app from 2006.
TSP je jedna z nejznámějších optimalizačních úloh a krásně shrnuje celou tuhle sérii: prostor řešení je obrovský, hrubá síla nestačí, a tak nasazujeme heuristiky a evoluci. The TSP is one of the best-known optimization problems and neatly sums up this whole series: the solution space is enormous, brute force isn't enough, so we bring in heuristics and evolution.
Počet různých tras je (n−1)!/2. Pro 20 měst je to už ~1016,
pro 192 měst nepředstavitelné číslo. Projít všechny (jako v příkladu 1) nejde. The number of distinct routes is (n−1)!/2. For 20 cities that's already ~1016;
for 192 cities, an unimaginable number. Going through them all (as in example 1) is impossible.
Chytrý trik: kdykoliv se trasa sama kříží, prohození dvou hran ji zkrátí. Opakováním vznikne velmi dobrá (i když ne nutně optimální) trasa. A clever trick: whenever a route crosses itself, swapping two edges shortens it. Repeating this yields a very good (though not necessarily optimal) route.
Populace tras se kříží a mutuje k lepšímu — přesně princip z příkladu 8, jen místo věty hledáme nejkratší okruh. 2-opt funguje jako lokální „doladění" potomků. A population of routes crosses over and mutates toward better ones — exactly the principle from example 8, only instead of a sentence we seek the shortest loop. 2-opt acts as a local "fine-tuning" of the offspring.
TSP není jen hlavolam — stejná úloha je za plánováním rozvozů, trasováním vrtů na deskách, logistikou i sekvenováním. Dobrá heuristika tu šetří reálné peníze. The TSP isn't just a puzzle — the same problem lies behind delivery planning, drilling routes on circuit boards, logistics and sequencing. A good heuristic here saves real money.