Kompyuter injiniringi ” fakulteti “dasturiy injiniring” kafedrasi

Коммивояжер ҳақидаги масала биз 6-бобда кўриб чиққан дастур масалаларига ўхшаш. Ҳар бир шаҳарни графнинг чўққиси, шаҳарлар орасидаги йўлни қирралар, улар орасидаги саёҳат баҳосини шу қирранинг оғирлиги деб тасаввур қилиши мумкин. Бундан шундай хулоса чиқариш мумкинки, қисқа йўлни қидириш алгоритми коммивояжер масаласини ҳал қилади, бироқ бу ундай эмас. Коммивояжер ҳақидаги масаланинг қандай икки шарти уни қисқа йўл ҳақидаги масаладан фарқлайди? Биринчидан биз ҳамма шаҳарларга ташриф буюришимиз керак, қисқа йўлни излаш алгоритми эса берилган икки шаҳарлар орасидаги йўлни беради. Агар қисқа йўлни танлаш алгоритми берган қисқа бўлакли йўлни йиғсак, бу йўл баъзи шаҳарлардан бир неча марта ўтади. Иккинчи фарқ қисқа йўлни излашда дастлабки нуқтага қайтишни талаб қилишдан иборат.
Бу масала NP синфига тегишли эканлигини кўрсатиш учун уни юқорида ёритилган икки қадамли амал ёрдамида қандай ечиш мумкинлигини тушуниш зарур. Коммивояжер ҳақидаги масаланинг биричи қадамида шаҳарларнинг баъзи тартиблаштирилиши асосий ўринга чиқади. Бу детерминаллашмаган жараён бўлганлиги учун ҳар сафар янги тартиб пайдо бўлади. Генерация жараёнини полиномиал вақтда амалга ошириш мумкин: биз шаҳарлар рўйхатини сақлашимиз мумкин, тасодифий рақамни асосийлаштиришимиз, шу номдаги шаҳарни рўйхатдан танлашимиз ва у Яна пайдо бўлмаслиги учун рўйхатдан чиқаришимиз мумкин. Бундай жараён O(N) ичида амалга оширилади, бу ерда N – шаҳарлар сони. Иккинчи қадамда берилган тартибдаги шаҳарлар бўйича саёҳатлар баҳосини ҳисоблаш амалга оширилади. Бунинг учун биз рўйхатдаги шаҳарларнинг кетма-кет жуфтлари орасидаги саёҳат баҳосини жамлашимиз керак, бунинг учун ҳам O(N) жараёни талаб қилинади. Икала қадам ҳам полиномиал, чунки коммивояжер масаласи NP синфига тегишли.
Бу ерда шуни таъкидлаш лозимки, бундай икки қадамли амални биз аввал кўриб чиққан масалаларнинг ихтиёрийсига қўллаш мумкин. Масалан, рўйхатни саралашни дастлабки рўйхат элементларининг эркин тартибини асосийлаштириб, бу тартиб ўсувчи эканлигини текширган ҳолда бажариш мумкин. Саралаш масаласининг бундай талқини NP синфига тегишли эмасми? Албатта, тегишли. P ва NP синфлари орасидаги фарқ шундаки, биринчи ҳолда бизда полиномиал вақтда масалани ечувчи детерминаллашган алгоритм бўлса, иккинчи ҳолда биз бундай алгоритмни билмаймиз. Бу масалага биз 11.3 § да қайтамиз.