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

SNo edit summary
[[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 uždavinys''' arba '''komivojažieriaus uždavinys'''  – [[grafų teorija|grafų teorijos]] uždavinys, kai pilnajame [[svorinis grafas|svoriniame grafe]] ieškoma mažiausio svorio [[Hamiltono ciklas|Hamiltono ciklo]]. Neformaliai jis nusakomas taip:
: ''Turint tam tikrą skaičių 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.''
 
 
=== Tikslūs algoritmai ===
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ų atsakymą pateikiantys algoritmai sprendžia problemą tik su nedideliu miestų skaičiumi:
* Įvairūs [[skaldyk ir valdyk]] <!-- o tai ne „šakų ir ribų“ algoritmų klasė? --monas --> algoritmai, dažniausiai tinkami suskaičiuoti sprendimą daugiausiai 40-60 miestų.
* Geriau veikia algoritmai, kurie remiasi [[tiesinis programavimas|tiesiniu programavimu]]. Tokie algoritmai gali būti efektyviai naudojami tikslaus maršruto tarp 120-200120–200 miestų radimui.
 
[[2001]] metais buvo suskaičiuotas tikslus maršrutas 15 112 Vokietijos miestų naudojant tiesiniu programavimu paremtą metodą. Skaičiavimui buvo naudojama 110 procesorių tinklas. Galutinis apskaičiuotas maršrutas yra apie 66 000 kilometrų ilgio. [http://www.math.uwaterloo.ca/tsp/d15sol/]
 
==== Artimiausio kaimyno metodas ====
Pradedami nuo kažkurios grafo viršūnės, pastoviai renkamės iš neaplankytų viršūnių pačią „artimiausią“ (su kuo mažesniu briaunos svoriu). Kai nebelieka neaplankytų viršūnių  – grįžtame į pradinę.
 
==== Pigiausios jungties algoritmas ====
Pradedami nuo bet kurios grafo viršūnės,
# Imame mažiausio svorio briauną (jei yra kelios vienodai mažo svorio  – renkamės bet kurią). Pasirinktą briauną pažymime.
# Imame kitą mažiausio svorio briauną ir ją pažymime. Briauna yra tinkama, jei
## ji nepažymėta;
15 145

pakeitimai