Keliaujančio pirklio uždavinys: Skirtumas tarp puslapio versijų

S
robotas: brūkšneliai keičiami brūkšniais (pagal lietuvių kalbos rašybos normas)
S (robotas Pridedama: simple:Travelling Salesman Problem)
S (robotas: brūkšneliai keičiami brūkšniais (pagal lietuvių kalbos rašybos normas))
'''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 baigtusi pradiniame mieste.''
 
Grafų teorijoje galima uždavinį performuluoti - ''kaip rasti mažiausio svorio Hamiltono ciklą grafe su svoriais''.
 
==Sprendimo sudėtingumas==
Akivaizdžiausias uždavinio sprendimas - visų įmanomų maršrutų perrinkimas. Tačiau tokio sprendimo sudėtingumas N! (miestų skaičiaus [[faktorialas]]), taigi didėjant miestų skaičiui sprendimas pasidaro nepraktiškas.
 
==Tikslūs sprendimai==
106 625

pakeitimai