Коммивояжер

Коммивояжер хакидаги масала Хар бир шахарни графнинг чуккиси. шахарлар орасидаги йулни кирралар, улар орасидаги саёхат бахосини шу кирранинг огирлиги деб тасаввур килиши мумкин. Бундан шундай хулоса чикариш мумкинки, киска йулни кидириш алгоритми коммивояжер масаласини хал килади, бирок бу ундай эмас. Коммивояжер хакидаги масаланинг кандай икки шарги уни киска йул хакидаги масаладан фарклайди? Биринчидан биз хамма шахарларга ташриф буюришимиз керак. киска йулни излаш алгоритми эса берилган икки шахарлар орасидаги йулни беради. Агар киска йулни ганлаш алгоритми берган киска булакли йулни йигсак, бу йул баъзи шахарлардан бир неча марта утади. Иккинчи фарк киска йулни излашда дастлабки нуктага кайтишни талаб килишдан иборат.
Бу масала NP синфига тегишли эканлигини курсагиш учун уни юкорида ёритилган икки кадамли амал ёрдамида кандай ечиш мумкинлигини тушуниш зарур. Коммивояжер хакидаги масаланинг биричи кадамида шахарларнинг баъзи тартиблаштирилиши асосий уринга чикади. Бу детерминаллаш маган жараён булганлиги учун хар сафар янги тартиб иайдо булади. Генерация жараёнини полиномиал вактда амалга ошириш мумкин: биз шахарлар руйхатини саклашимиз мумкин, тасодифий ракамни асосийлаштиришимиз, шу номдаги шахарни руйхатдан танлашимиз ва у Яна иайдо булмаслиги учун руйхатдан чикаришимиз мумкин. Бундай жараён O(N) ичида амалга оширилади, бу ерда N - шахарлар сони. Иккинчи кадамда берилган гаргибдаги шахарлар буйича саёхатлар бахосини хисоблаш амалга оширилади. Бунинг учун биз руйхатдаги шахарларнинг кетма-кет жуфтлари орасидаги саёхат бахосини жамлашимиз керак, бунинг учун хам O(N) жараёни талаб килинади. Икала кадам хам полиномиал, чунки коммивояжер масаласи NP синфига тегишли.