Lungimea traseului
Cel mai scurt găsit
Pași
Trasee posibile
  • Traseu
  • Cel mai scurt găsit
  • Start

Metodă Lungime Peste cel mai scurt Pași
- - -
- - -
- - -
- - -
- - -

Mai multe despre problema comis-voiajorului

Problema comis-voiajorului

Un comis-voiajor trebuie să viziteze fiecare oraș o singură dată și să se întoarcă acasă. Ce ordine face călătoria cea mai scurtă? Întrebarea este ușor de pus, dar, pe măsură ce numărul orașelor crește, este fără speranță să îi răspundeți încercând fiecare ordine: 30 de orașe permit deja aproximativ 4,4 × 10³⁰ trasee închise. Împrăștiați orașe pe o hartă sau plasați-le cu clic pe ale dumneavoastră, apoi urmăriți cum reguli empirice rapide, îmbunătățiri ingenioase și o metodă exactă își construiesc traseele pas cu pas și vedeți cât de aproape ajung cele rapide. Alege cum sunt așezate orașele și câte sunt, alege o metodă și apasă Rezolvă ca să o vezi construind pas cu pas un traseu închis, sau Pas ca să avansezi câte o mutare. Dă clic pe hartă ca să adaugi un oraș sau dă clic pe un oraș ca să-l elimini. Compară toate rulează fiecare metodă pe aceleași orașe și arată cât de departe este fiecare de cel mai scurt traseu găsit. Orașul roșu este punctul de plecare al călătoriei.

Cum funcționează

  1. Alegeți o dispunere și numărul de orașe sau dați clic pe hartă pentru a vă plasa propriile orașe și dați clic pe un oraș pentru a-l elimina.
  2. Alegeți o metodă și apăsați Rezolvă pentru a o urmări pas cu pas sau Pas pentru a avansa câte o mutare.
  3. Apăsați Compară toate pentru a rula fiecare metodă pe aceleași orașe și citiți cu cât este fiecare traseu mai lung decât cel mai scurt găsit.

De ce este dificilă

Cu n orașe există (n − 1)! / 2 trasee închise diferite, deoarece nu contează de unde porniți sau în ce sens parcurgeți traseul. Asta înseamnă 12 pentru 5 orașe, 181.440 pentru 10 și aproximativ 6 × 10¹⁶ pentru 20. Nu se cunoaște nicio metodă care să găsească cel mai scurt traseu pentru orice hartă într-un timp care crește doar ca o putere a lui n; problema este NP-dificilă. Cea mai bună metodă exactă din această aplicație, programarea dinamică Held–Karp din 1962, are încă nevoie de aproximativ n² · 2ⁿ pași, așa că aici este limitată la 12 orașe.

Trasee bune, rapid

În practică, traseele aproape cele mai scurte se găsesc repede. Cel mai apropiat vecin merge mereu la cel mai apropiat oraș nevizitat și ajunge de obicei cu aproximativ 25% peste cel mai bun traseu. Inserția cea mai ieftină extinde o buclă și adaugă orașul care o lungește cel mai puțin. 2-opt pornește de la orice traseu și înlocuiește în mod repetat două muchii cu două mai scurte, ceea ce elimină toate încrucișările și ajunge de obicei la aproximativ 5% de optim. Recoacerea simulată face mutări 2-opt aleatorii și, cât timp este încă „fierbinte”, acceptă și unele mutări care lungesc traseul, astfel încât poate ieși din fundături înainte să se stabilizeze.

Întrebări frecvente

Există o formulă pentru cel mai scurt traseu?

Nu. Cel mai scurt traseu depinde de pozițiile exacte ale tuturor orașelor și nicio metodă cunoscută nu îl găsește pentru orice hartă fără o cantitate de muncă ce, în cel mai rău caz, crește exponențial. Pentru câteva sute sau mii de orașe, solvere exacte specializate precum Concorde demonstrează totuși trasee optime combinând programarea liniară cu tăieri ingenioase, iar cea mai mare instanță rezolvată exact până acum are 85.900 de puncte.

De ce elimină 2-opt toate încrucișările?

Dacă două muchii ale unui traseu se încrucișează, cele patru orașe pe care le unesc formează un patrulater ale cărui diagonale sunt cele două muchii. Înlocuirea lor cu două laturi opuse ale patrulaterului este întotdeauna mai scurtă, conform inegalității triunghiului, și inversează porțiunea de traseu dintre ele. 2-opt face astfel de schimburi până când niciunul nu mai ajută, deci traseul său final nu se intersectează niciodată cu el însuși.

Ce este temperatura în recoacerea simulată?

Ea controlează cât de dispusă este metoda să accepte o mutare care lungește traseul. O mutare care adaugă d la lungime este acceptată cu probabilitatea e^(−d/T). La o temperatură T ridicată, aproape orice este permis, ceea ce îi permite traseului să scape dintr-o aranjare slabă; pe măsură ce T scade, metoda devine lacomă și se stabilizează. Numele vine de la răcirea lentă a metalului, astfel încât atomii lui să găsească o aranjare cu energie scăzută.

De ce este metoda exactă limitată la 12 orașe?

Held–Karp stochează cel mai scurt drum pentru fiecare submulțime de orașe și fiecare oraș final posibil, adică aproximativ n · 2ⁿ numere, și îl calculează pe fiecare cu n comparații. Pentru 12 orașe înseamnă câteva sute de mii de pași; pentru 25 de orașe ar fi miliarde. Este totuși enorm mai rapid decât încercarea tuturor celor (n − 1)! / 2 trasee: pentru 12 orașe acestea ar fi aproape 20 de milioane.

Se trimite ceva la un server?

Nu. Orașele și toate cele cinci metode rulează în browserul dumneavoastră. Orașele pe care le plasați cu clic rămân în stocarea locală a acestui browser.

Ești gata să încerci?

Deschide PictorX în browser – fără instalare și fără card de credit.

Mergi la editor