Keliaujančio pirklio uždavinys: Skirtumas tarp puslapio versijų
S
→Euristiniai 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.
==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ų.
[[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.
==
Į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%.
=== Artimiausio kaimyno metodas ===
Pradedami nuo kažkurios Grafo viršūnės, pastoviai renkames 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 kažkuriuos 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ą pigiausią tinkamą briauną ir ją pažymime. Briauna yra tinkama, jei
* ji nepažymėta;
* ji neuždaro mažesnio ciklo;
* 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ų brianų 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.
[[Category: Grafų teorija]]
| |||