Vikipedija

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

Naršyti istoriją interaktyviai
← Prieš tai darytas keitimasKitas pakeitimas →
Ištrintas turinys Pridėtas turinys
VizualusVikitekstas
Thijs!bot (aptarimas | indėlis)
Botai
60 408 keitimai
Lang-Bot-as (aptarimas | indėlis)
106 625 keitimai
S robotas: brūkšneliai keičiami brūkšniais (pagal lietuvių kalbos rašybos normas)
Eilutė 1:
'''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 mieste.''
 
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.
 
==Tikslūs sprendimai==
Rodomas puslapis "https://lt.wikipedia.org/wiki/Keliaujančio_pirklio_uždavinys"