Keliaujančio pirklio uždavinys: Skirtumas tarp puslapio versijų
Ištrintas turinys Pridėtas turinys
S robotas: smulkūs taisymai |
"Commonscat", paveikslėlis. |
||
Eilutė 1:
[[Vaizdas:TSP Deutschland 3.png|thumb|Keliaujančio pirklio uždavinio sprendinys, kai reikia apeiti penkiolika didžiausių Vokietijos miestų ir briaunų svoriai lygūs atstumams tarp miestų]]
'''Keliaujančio pirklio (komivojažieriaus) uždavinys''' – [[grafų teorija|grafų teorijoje]] sprendžiamas uždavinys, formuluojamas taip:
: ''Turint tam tikrą kiekį miestų, taip pat kelionės iš vieno miesto į kitą kainas, reikia rasti pigiausią maršrutą, kad aplankius kiekvieną miestą maršrutas baigtųsi pradiniame mieste.''
eilutė 31 ⟶ 32:
=== 2-jų pasirinktųjų sukeitimo algoritmas ===
Šio algoritmo veikimo principas yra dviejų briaunų panaikinimas, sujungiant viršūnes kitokiu būdu, tikintis gauti trumpesnį maršrutą. Jei pasiūlytas naujasis kelias yra trumpesnis (jei panaikintų briaunų svorių suma didesnė už sujungtų kitokiu būdu), tuomet juo pakeičiame pradinį. Visada yra tik vienas būdas perjungti lankus, kurie įeina į maršrutą, kad išliktų ciklas.
== Išorinės nuorodos ==
{{Commonscat|Traveling salesman problem}}
{{Link FA|de}}
| |||