Kompyuter injiniringi ” fakulteti “dasturiy injiniring” kafedrasi

Детерминалланмаган алгоритмлар
NP нима?
Аввалги бўлимларимизда кўздан кечирилган барча алгоритмлар полиномиал мураккабликка эга эди. Ундан ташқари, уларнинг ҳаммасининг мураккаблиги O(N³)¹ эди, комплекс кўпайтириш алгоритми эса энг кўп вақт талаб қилувчи эди. Бироқ, асосийси, биз бу масалаларнинг аниқ ечимини идрокли вақт ичида топа олдик. Бу масалаларнинг ҳаммаси Р синфига – полиномиал мураккабликка эга масалалар синфига тегишли. Бундай масалалар деярли ечиладиган ҳисобланади.
Яна бошқа масалалар синфи ҳам бор: улар деярли ҳал қилинмайди ва биз уларни идрокли вақтда еча оладиган алгоритмларни билмаймиз. Бу масалалар NP синфини ҳосил қилади, яъни детерминаллашмаган полиномиал мураккабликка эга. Бу сўзларнинг маъноси параграф охирида ойдинлашади. Фақат шуни айтиш мумкинки, бу масалаларни ечувчи барча маълум детерминаллашган алгоритмларнинг мураккаблиги ёки экспоненциал, ёки факториал. Улардан баъзиларининг мураккаблиги 2^N га тенг, бу ерда N – кирувчи рақамларнинг сони. Бу ҳолда кирувчи рақамлар рўйхатига бир элементни қўшсак, алгоритмнинг ишлаш вақти икки баробар ортади. Агар бундай вазифани ечиш учун кирувчи ўнта элементдан алгоритмга 1024 та амал талаб қилинган бўлса, кирувчи 11 та элементдан амаллар сони 2048 ни ташкил қилади. Бу вақтнинг киришни қисқа узунлаштиришдаги сезиларли ортишидир.
NP синфидаги вазифаларни характерловчи «Детерминиллашган полиномиал» сўз бирикмаси уни ечишда қуйидаги икки қадамли ёндашув ҳисобланади.
Биринчи қадамда бундай вазифанинг мавжуд ечимини асосий деб ҳисоблаб, яъни ечимни топишга ҳаракат қилувчи детерминаллашмаган алгоритм мавжуд; баъзан бундай уриниш муваффақиятли бўлиб, биз оптимал ёки оптималга яқин жавобни оламиз, баъзида эса муваффақиятсиз (оптималдан узоқ жавоб) олинади. Иккинчи қадамда биринчи қадамда олинган жавоб дастлабки вазифанинг ечими эканлиги текширилди. Бу қадамларнинг ҳар бири алиҳида полиномиал вақтни талаб қилади. Муаммо шундаки, изланган ечимни олиш учун бу қадамларни неча марта такрорлашимиз кераклигини биз билмаймиз. Иккала қадам полиномиал бўлса ҳам, уларга мурожаат экспенциал ёки факториал бўлиши мумкин.
Коммивояжер масаласи NP синфига тегишли. Бизга шаҳарлар тўплами ва улар орасидаги саёҳат «нархи» берилган. Шундай тартибни аниқлаш керакки, ҳамма шаҳарларга ташриф буюриб, дастлабки шаҳарга қайтиб келганда, саёҳатнинг умумий нархи минимал бўлсин. Бу вазифани, масалан, шахар кўчаларидаги ахлатни самарали йиғиштириш тартибини аниқлаш ёки компьютер тармоғининг ҳамма бўғимларида ахборотни тез тарқатиш йўлини танлашда қўллаш мумкин. Саккизта шаҳарни 40.320 мавжуд усул билан соддалаштириш мумикн, ўнта шаҳар учун бу сон 3628800 га ортади. Қисқа йўлни танлаш ушбу ҳамма имкониятларни кўриб чиқишни талаб қилади. Фараз қилайлик, бизда кўрсатилган тартибда 15 та шаҳар орқали саёҳат баҳосини ҳисобловчи алгоритм бор. Агар бир сонияда бундай алгоритм ўзидан 100 та вариант ўтказса, ҳамма имкониятлар ва қисқа йўлни топиш учун унга тўрт аср керак бўлади. Агар бизнинг хизматимизда 400 та компьютер бўлса ҳам, барибир бунга бир йил кетади, биз атига 15 та шаҳарни назарда тутяпмиз. 20 та шаҳар учун қисқа йўлни топиш учун миллиард компьютерлар 9 ой ичида параллел равишда ишлаши лозим. Компьютерлар оптимал ечимни топишини кутгандан кўра қандай бўлса ҳам саёҳат қилиш тезроқ ва арзонроқ эканлиги аниқ кўриниб турибди.
Уларнинг барчасини кўздан кечирмай қисқа йўлни топса бўладими? Барча йўлларни кўриб чиқувчи алгоритмни ўйлаб топиш ҳали ҳеч кимнинг қўлидан келмаган. Шаҳарлар сони кам бўлса, вазифа осон ҳал бўлади, бироқ бу ҳар доим шундай бўлади дегани эмас, бизни умумий вазифанинг ечими қизиқтиради.