Keliaujančio pirklio uždavinys: Skirtumas tarp puslapio versijų
S
wiki sintakse 3
S (robotas Pridedama: eu:Saltzaile ibiltariaren ebazkizun) |
S (wiki sintakse 3) |
||
|
==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ų.
* Geriau veikia algoritmai, kurie remiasi [[tiesinis programavimas|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.
=== 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 ===
| |||