Kompyuter injiniringi ” fakulteti “dasturiy injiniring” kafedrasi

Типик NP масалалар
Биз муҳокама қиладиган масалаларнинг ҳар бири ёки оптималлаштирилган, ёки ечимни қабул қилиш масаласи ҳисобланади. Оптималлаштириш масаласининг мақсади, одатда, минимал ёки максимал қийматга эга аниқ натижа ҳисобланади. Ечимни қабул қилиш масаласида,одатда, чегарали қиймат берилади. Бизни кўрсатилган чегарадан ката (максималлаштириш масалаларида) ёки кичик (минималлаштириш масалаларида) ечим мавжудлиги қизиқтиради. Оптималлаштириш масалаларида олинган аниқ натижа жавоб бўлиб хизмат қилади, ечимни қабул қилиш масалаларида – «ҳа» ёки «йўқ» жавоби бўлади.
11.1 § да биз коммивояжер масаласининг оптималлашган варианти билан шуғулланган эдик. Бу минималлаштириш масаласи эди ва бизни минимал нарх йўли қизиқтирган эди. Ечимни қабул қилиш вариантида биз берилган С константадан кичик баҳоли коммивояжер йўли мавжудлигини сўрашимиз мумкин эди. Ечимни қабул қилиш масаласидаги жавоб танланган чегарага боғлиқлиги аниқ. Агар бу чегара жуда ката бўлса (масалан, у ҳамма йўлларнинг жамланма баҳосидан ортса), «ҳа» жавобини олиш қийин эмас. Агар бу чегара жуда кичик бўлса (масалан, у ихтиёрий икки шаҳар орасидаги йўллар баҳосидан кичик бўлса), «йўқ» жавоби ҳам тез олинади. Бошқа оралиқ ҳолларда жавобни излаш вақти жуда узоқ ва у оптималлашган масалани ечиш вақтига тенг. Шунинг учун биз оптималлашган ва ечимни қабул қилиш масалалари ҳақида навбатма-навбат гапириб, жорий мақсадларимизга жавоб берадиган масаладан фойдаланамиз.
Кейинги бир нечта бўлимларда биз ҳам оптималлашган вариантда, ҳам ечимни қабул қилиш вариантида яна олтита NP масалани кўриб чиқамиз.
Графни бўяш
6-бобда айтиб ўтганимиздек, G = (V, Е) графи чўққиларни жуфтлаб боғловчи Е қирралар тўплами, V тугунлар ёки чўққилар тўпламидан иборат. Бу ерда биз фақат йўналтирилган графлар Билан шуғулланамиз. Графнинг чўққиларини бутун сонлар билан белгиланадиган турли рангларга бўяш мумкин. Бизни ҳар бир қирранинг учи турли рангларга бўялиши қизиқтиради. N чўққили графда турли N рангларга бўяш мумкин, лекин бунда бўёқни кам миқдорда ишлатиш мумкинми? Оптималлаштириш масаласида бизни граф чўққисини бўяш учун зарур бўладиган бўёқларнинг минимал миқдори қизиқтиради. Ечимни қабул қилиш масаласида бизни чўққиларни с ёки камроқ бўёқларга бўяш мумкинлиги қизиқтиради.
Графни бўяш масаласида амалий иловалар бор. Агар графнинг ҳар бир чўққиси коллежда ўқиладиган курсни билдирса ва чўққилар қирралар билан боғланса, агар иккала курсни танловчи талаба бўлса, ғоят мураккаб граф ҳосил бўлади.
Агар ҳар бир талаба 5 та курс тингласа, бир талабага 10 та қирра тўғри келади. 35000 талабага 500 курс тўғри келади, деб фараз қилайлик. У ҳолда ҳосил бўлган графда 500 чўққи ва 35000 қирра бўлади. Агар имтиҳонларга 20 кун ажратилган бўлса, талабага бир кунда иккита имтиҳон тўғри келмаслиги учун граф чўққиларини 20 та ранга бўяш керак бўлади.
Имтиҳонлар жадвалини тишлаб чиқиш графларни бўяшга эквивалентдар. Аммо графларни бўяш масаласи NP синфига тегишли, шунинг учун жадвални идрокли вақтда тўғри ишлаб чиқиш мумкин эмас. Бундан ташқари имтиҳонларни режалаштирганда, одатда, талабаларда бир кунда иккитадан ортиқ имтиҳон бўлмаслиги кераклиги талаб этилади, курснинг турли бўлимлари бўйича имтиҳонлар эса бир кунга белгиланади. Кўриниб турибдики, имтиҳонларнинг «мукаммал» режасини ишлаб чиқиш мумкин эмас, шунинг учун қулай режаларни ишлаб чиқиш учун бошқа техника зарур. Яқинлаштирилган алгоритмлар 9-бобда ёритилган.