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

Grafų teorijoje galima uždavinį performuluoti – ''kaip rasti mažiausio svorio Hamiltono ciklą grafe su svoriais''.

 

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]] <!-- o tai ne „šakų ir ribų“ algoritmų klasė? --monas --> algoritmai, dažniausiai tinkami suskaičiuoti sprendimą daugiausiai 40-60 miestų.