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

← Prieš tai darytas keitimas Kitas pakeitimas →

Ištrintas turinys Pridėtas turinys

Inline

18:41, 8 lapkričio 2009 versija

Keliaujančio pirklio (komivojažieriaus) uždavinys arba komivojažieriaus uždavinys – grafų teorijos uždavinys, kai svoriniame grafe ieškoma mažiausio svorio Hamiltono ciklo. Neformaliai jis nusakomas 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.

Algoritmai

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 algoritmai, dažniausiai tinkami suskaičiuoti sprendimą daugiausiai 40-60 miestų.
Geriau veikia algoritmai, kurie remiasi tiesiniu programavimu. Tokie algoritmai gali būti efektyviai naudojami tikslaus maršruto tarp 120-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, vienam 500MHz procesoriui būtų prireikę apie 22,6 metų tiems patiems skaičiavimams atlikti.

Euristiniai algoritmai

Įvairūs aproksimaciniai algoritmai gana greitai ir su pakankamai dideliu tikslumu sprendžia keliaujančio pirklio uždavinį. Moderniausi algoritmai gali rasti sprendimus su ypatingai dideliu kiekiu miestų (milijonais) per protingą laiką ir yra įrodyta, kad atsakymas nuo optimalaus sprendimo nėra nutolęs toliau nei 2-3%.

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
1. ji nepažymėta;
2. ji neuždaro mažesnio ciklo;
3. ji nėra paskutinė nepažymėta briauna, išeinanti iš vienos viršūnės;
kartojame 2 žingsnį, kol gausime Hamiltono ciklą.

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

Vikiteka: Keliaujančio pirklio uždavinys – vaizdinė ir garsinė medžiaga

Šablonas:Link FA

@@ Eilutė 1: / 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:
+'''Keliaujančio pirklio (komivojažieriaus) uždavinys''' arba '''komivojažieriaus uždavinys''' – [[grafų teorija|grafų teorijos]] uždavinys, kai [[svorinis grafas|svoriniame grafe]] ieškoma mažiausio svorio [[Hamiltono ciklas|Hamiltono ciklo]]. Neformaliai jis nusakomas 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.''
+== Algoritmai ==
-Grafų teorijoje galima uždavinį performuluoti – ''kaip rasti mažiausio svorio Hamiltono ciklą grafe su svoriais''.
-== Sprendimo sudėtingumas ==
+=== 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ūs sprendimai ==
 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ų.
@@ Eilutė 15: / Eilutė 14: @@
 [[2001]] metais buvo suskaičiuotas tikslus maršrutas 15 112 Vokietijos miestų naudojant tiesiniu programavimu paremtą metodą. Skaičiavimui buvo naudojama 110 procesorių tinklas, vienam 500MHz procesoriui būtų prireikę apie 22,6 metų tiems patiems skaičiavimams atlikti.
-== Euristiniai algoritmai ==
+=== Euristiniai algoritmai ===
 Įvairūs aproksimaciniai algoritmai gana greitai ir su pakankamai dideliu tikslumu sprendžia keliaujančio pirklio uždavinį. Moderniausi algoritmai gali rasti sprendimus su ypatingai dideliu kiekiu miestų (milijonais) per protingą laiką ir yra įrodyta, kad atsakymas nuo optimalaus sprendimo nėra nutolęs toliau nei 2-3%.
-=== Artimiausio kaimyno metodas ===
+==== 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 ===
+==== 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.
@@ Eilutė 30: / Eilutė 29: @@
 # kartojame 2 žingsnį, kol gausime Hamiltono ciklą.
-=== 2-jų pasirinktųjų sukeitimo algoritmas ===
+==== 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.