Keliaujančio pirklio uždavinys: Skirtumas tarp puslapio versijų
S cs,de,he,ja,nl,pl |
Nėra keitimo santraukos |
||
Eilutė 1: | Eilutė 1: | ||
'''Keliaujančio pirklio uždavinys''' - [[grafų teorija|grafų teorijoje]] sprendžiamas uždavinys, formuluojamas taip: |
'''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 meiste.'' |
: ''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 meiste.'' |
||
Eilutė 18: | Eilutė 18: | ||
Įvairūs aproksimaciniai algoritmai gana greitai ir su pakankamai didelui 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 teisingiausio sprendimo nėra nutolęs toliau nei 2-3%. |
Įvairūs aproksimaciniai algoritmai gana greitai ir su pakankamai didelui 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 teisingiausio sprendimo nėra nutolęs toliau nei 2-3%. |
||
[[Category: |
[[Category: Grafų teorija]] |
||
[[en:Traveling salesman problem]] |
[[en:Traveling salesman problem]] |
19:39, 11 gegužės 2005 versija
Keliaujančio pirklio (komivojažieriaus) uždavinys - 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 meiste.
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.
Algoritmai
Tikslūs sprendimai
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 parentą 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 didelui 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 teisingiausio sprendimo nėra nutolęs toliau nei 2-3%.