Toshkent axborot texnologiyalari universiteti nukus filiali

O’ZBEKISTON RESPUBLIKASI AXBOROT

TEXNOLOGIYALARI HA'M KOMMUNIKATSIYALARINI

RAWAJLANDIRIW WAZIRLIGI

MUHAMMAD AL – XORAZMIY ATINDAG'I

TOSHKENT AXBOROT TEXNOLOGIYALARI UNIVERSITETI

NUKUS FILIALI

“Telekommunikatsiya texnologiyalari ha'm Kasbiy ta’lim” fakulteti

“Kompyuter injiniring” sırtqı bo'lim bag'dardı 3-kurs student

Tangirbergenov Azimjan

“Algaritimlerdi proektlestiriw” paninen

O'ZBETINSHE JUMIS.

Orınlag'an : Tangirbergenov.A

Qabıllag'an: Janabergenova.A

Nukus – 2023

Tema: NP – tolıq máseleler. Esaplawda sheshilmewlik jag'dayları.

Joba:

1. NP – tolıq máselelerdi sheshiw usıllarınıń klassifikaciyası
2. Tolıq qayta tańlaw (Polniy perebor) usılı
3. NP tolıq máselelerdi sheshiw ushın evrestik algoritmlar

NP-to'liklik máselesi

Ámeliy kózqarastan qızıq bolǵan wazıypalardıń kópshiligi, polinomial (polinomial waqıt dawamında isleytuǵın ) algoritmlar. Yaǵnıy, n uzınlıqtaǵı kirisiwde algoritmdıń islew waqtı turaqlı k (kirisiw uzınlıǵınan ǵárezsiz) ushın O(n^k) den aspaydı. Hár bir máselede bul ózgeshelikti qandiradigan sheshim algoritmı joq. Birpara máselelerdi ulıwma qandayda bir algoritm járdeminde hal etip bolmaydı. Bunday máseleniń klassik mısalı bul “toqtap qalıw mashqalasi” (berilgen programma berilgen kirisiwde toqtap qalıwın biliw). Bunnan tısqarı, olardı sheshetuǵın algoritm ámeldegi bolǵan máseleler ámeldegi, hár qanday bunday algoritm uzaq waqıt isleydi - onıń islew waqtı hár qanday fiksirlangan k sanı ushın O (nk) bóle almadı. Eger biz ámeliy algoritmlar hám tek teoriyalıq qızıǵıwshılıq algoritmları ortasında qopal, biraq rásmiy shegara sızıwdı qálesek, ol jaǵdayda kópshiligilikli waqıt ishinde isleytuǵın algoritmlar klası birinshi orında turadı. NP -tolıq dep atalǵan máseleler klasın kórip shıǵamız. Bul máseleler ushın hesh qanday polinomial algoritmlar tabilǵan zatǵan, biraq bunday algoritmlar joqlıǵı tastıyıqlanmadi. NP menen baylanıslı mashqalalardi úyreniw “P = NP” dep atalǵan soraw menen baylanıslı. Bul soraw 1971 jılda berilgen hám házirde esaplaw teoriyasında eń qıyın máselelerden biri esaplanadı. Ne ushın programmist NP - pıtken máseleler haqqında biliwi kerek? Eger qandayda bir NP - tolıqlıq ushın onıń tolıqlıǵın tastıyıqlaw múmkin bolsa, onı derlik hal etip bolmaydı dep esaplaw ushın tiykar bar. Bunday halda, onı anıq sheshetuǵın operativ algoritmdı qıdırıwdı dawam ettiriwden kóre, shamalıq algoritmdı dúziwge waqıt jumsaw jaqsılaw bolıp tabıladı. Polinom waqtı Abstrakt mmáselele Joqarıda aytıp ótilgeni sıyaqlı, kóp tárepten sheshiletuǵın (polinomial) máseleler konsepsiyası ámelde sheshiliwi múmkin bolǵan máseleler ideyasın jetilistiriw esaplanadı. Bul shártlesiwdi ne túsintiredi? Birinshiden, ámelde isletiletuǵın kópaytirilgan algoritmlar, ádetde júdá tez isleydi. Ekinshiden, polinomial algoritmlar klasın kórip shıǵıw, bul klasstıń kólemi málim bir esaplaw modelin tańlawdan derlik ǵárezsiz bolıwı bolıp tabıladı. Mısalı, tosınarlı tosınarlı kirisiw mashinasında (RAM) kópaytirilgan waqıt ishinde sheshiliwi múmkin bolǵan máseleler klası Tyuring mashinalarında polinomal sheshiletuǵın máseleler klasına tuwrı keledi. Klass parallel esaplaw modeli ushın birdey boladı, protsessorlar sanı, kirisiw uzınlıǵı polinomi menen sheklengen. Úshinshiden, polinomal sheshiletuǵın máseleler klası tábiyiy jabıqlıq qásiyetlerine iye. Mısalı, eki algoritmdıń quramıkompozitsiyasi da polinomial waqıtlı isleydi. Óytkeni, kópxadlarning jıyındısı, kóbeymesi hám kompozitsiyasi kópxadr bolıp tabıladı. Tómende esaplaw máselesiniń abstrakt modelin keltirilgen. Bunı abstrakt másele dep ataymiz, Q - eki jıynaq elementleri arasındaǵı qálegen binar munasábet: I - shártler kompleksi hám S - sheshimler kompleksi. Mısalı, G= (v, E) jóneltirilmagan grafning berilgen eki úshleri arasındaǵı eń qısqa joldı tabıw máselesinde, shárt (element I) úsh element, graf hám eki qırdan ibarat hám sheshim (S element) - bul grafda kerekli joldı quraytuǵın vertikallardıń izbe-izligi. NP tolıqlıǵı teoriyasında tek sheshiw máseleleri kórip shıǵıladı - arnawlı bir sorawǵa “ha” yamasa “joq” dep juwap beriw kerek bolǵan máseleler. Rásmiy, I jıynaq shártlerin {0, 1} jıynaqǵa tuwrı keletuǵın funksiya retinde kórip shıǵilıwı múmkin. Mısalı, G= (v, E) grafdagi eń qısqa joldı tabıw máselesi menen berilgen G= (v, E) graf járdeminde eki túyin ol, v∈v hám natural k pútkil sanlar ol hám v túyinleri arasında odan úlken bolmaǵan hám de G grafda jol bar yamasa joq ekenligi máselesin sheshiń. Optimallastırıw menen baylanıslı máseleler bul - arnawlı bir muǵdardaǵı bahanı maksimal dárejede asırıw yamasa minimallastırıw kerek bolǵan máselelerdi. NP - tolıqlıq haqqında soraw beriwden aldın bunday máseleler, olardı sheshiw máselelerine aylantırılıwı kerek. Sonday etip, mısalı, grafdagi eń qısqa joldı tabıw máselesinde optimallastırıw máselesin sheshiw máselesinen ruxsat beriw máselesine óttik hám jol uzınlıǵına sheklew qosdıq. Eger transformaciyadan keyin NP - tolıq máselesi júzege kelse, ol jaǵdayda túp mashqalanıń qıyınlıǵı da belgilenedi. Maǵlıwmatlar prezentaciyası. Kirisiw maǵlıwmatların (yaǵnıy I jıynaqtıń elementi) algoritmǵa kirgiziwden aldın olardıń qanday etip “kompyuterge qolay” tárzde usınıs etiliwi tuwrısında kelisip alıw kerek. Dáslepki maǵlıwmatlar bıytlar izbe-izligi menen kodlanǵan dep qabıl etemiz. Formal aytqanda, S kompleksiniń elementlerin ańlatıw bul S den e ni bitli qatarlar jıynaqlarına túsiwi bolıp tabıladı. Mısalı, (0, 1, 2, 3,... ) - pútkil sanlardı, ádetde (0, 1, 10, 11, 100,... ) - bitli qatarlar menen ańlatıladı. Usınıs etilgen maǵlıwmatlardı jaylastırb, abstrakt máseleni satrli maǵlıwmatqa aylantıramız, bul satirli maǵlıwmat ushın kirisiw maǵlıwmatları, máseleniń dáslepki maǵlıwmatların sáwlelendiriwshi bitli satir boladı. Kirisiw maǵlıwmatları (bitli qatar) n - uzınlıqta bolǵanında, algoritmdıń islew waqtı O (T (n)) - bolsa, algoritm satirli máseleni O (T (n)) waqıtta sheshedi desek boladı. Eger k konstanta hám O (T (n)) waqıt ishinde bul máseleni sheshetuǵın algoritm ámeldegi bolsa, satirli másele polinomial dep ataladı. Quramalılıq P klası - bul barlıq satirli máseleler bolıp, polonomia waqıt ishinde sheshiliwi múmkin, yaǵnıy, O (nk) waqıt ishinde sheshiliwi múmkin, bul jerde k kiriwge baylanıslı bolmaydı. Polinomial abstrakt máselesiniń konsepsiyasın anıqlawdı qálegen halda, biz hár qıylı maǵlıwmatlardı usınıw múmkinligine dus kelamiz.
Polinomial abstrakt máselesiniń konsepsiyasın anıqlawdı qálegen halda, biz hár qıylı maǵlıwmatlardı usınıw múmkinligine dus kelamiz.

Xar bir usınıs etilgen e jıynaq ushın, I kiriwleri bolǵan Q abstrakt máseleniń satirli máselesin alamız.

Biraq, ámelde (hasası 1 bolǵan cifrlı sistema sıyaqlı “qımbat” wákillik usılların esaptan tısqarı qilsak), tábiyiy wákillik usılları ádetde ekvivalent bolıp tabıladı, sebebi olardı bir-birine kóp tárepten aylandırıw múmkin. A polinomial algoritmı ámeldegi bolsa, f:{0, 1}*→{0, 1}* funksiyası polinimial waqıt ishinde esaplab shıǵıladı, ol hár qanday x∈ {0, 1}* ushın f (x) nátiyjeni beredi.
Qálegen abstrakt másele ushın I kompleksi sharıtlarini kórip shıǵamız. I jıynaqtıń y e₁ hám y e₂ elementleri polinomial baylanısqan dep ataladı, eger polinomial waqıtta esaplaw múmkin bolǵan eki f₁₂ (e₁ (i)) = e₂ (i) hám f ₂₁ (e₂ (i)) = e₁ (i), i ∈ I funsiyalar ámeldegi bolsa. Bunday jaǵdaylarda, polinomial baylanısqan eki elementten qay-qaysısın tańlaw zárúrli emes.
P, NP, NP-complete (NP-to'liklik máseleleri) klasslar arasındaǵı munasábetler, NP-hard (NP-quramalı máseleler), P≠NP hám P=NP bolǵan qallarda.

NP- tuliklik máselesi — algoritmlar teoriyasında NP – klasstaǵı «ha» yamasa «yo'k» juwaplı máseleni sol klasstaǵı boshka máselege polinomial vakt oralgida maslastırıw múmkin (yaǵniy, baslanǵısh maǵlıwmatlar kolemine boglanganlik dárejesi málim polinimdan úlken bulmagan ámeller járdeminde atqarıladı ).

Sonday etip, NP -tolıq máseleler, málim mániste, NP klası daǵı “tipik” máseleler kompleksin qáliplestiredi: eger olardıń geyparaları ushın « operativ» sheshim algoritmı tapılsa, NP klası daǵı hár qanday basqa máseleni tap sol tárzde sheshiw múmkin.
Álippe degende hár qanday sheklengen belgiler kompleksi túsiniledi (mısalı, {0, 1} yamasa {a, b, c}). Qálegen álippesidan dúzilgen barlıq sózler kompleksi (jazılǵan satirlar, bul álippediń belgilerinen dúziledi) ∑* menen belgilenedi.
∑ alfavit járdeminde jaratılǵan qálegen L tili bul jıynaqtıń L jıynaq astısı, yaǵnıy L⸦.
Ushın teńib alıw wazıypası berilgen sóz tiline tiyisli yamasa joq ekenligin anıqlaw bolıp tabıladı.
∑ álippe ústinde hám L₂ – eki til bolsın. L1 tiline (Karp boyınsha ) L₂ tiline kemeytiw dep ataladı, eger funksiyası ámeldegi bolsa, bul funksiyanı polinomial waqıt menen esaplaw múmkin bolsa, tómendegi ózgeshelikke yega: x ∈ L₁,, eger hám tek eger f (x) ∈ L₂,. Karp boyınsha kemeytiw L₁ ≤ _p L ₂ menen belgilenedi.
Eger NP-den qandayda bir til oǵan qısqartirilsa, L₂ tili NP-tolıq dep ataladı. Til NP-jetilisken dep ataladı, eger ol NP-qıyın bolsa hám usınıń menen birge ózi NP klasında bolsa.
A másele B máselesine qısqartirilganligi, A másele B máselesinen kóre “quramalıroq” ekenligin ańlatadı (sebebi eger biz B máseleni sheshiliwi, A máselenin da sheshilishini ańlatadı ). Sonday etip, NP menen baylanıslı qıyınshılıqlar klasqa NP menen baylanıslı máseleler hám olar ushın « talay qıyın» bolǵan máseleler kiredi (yaǵnıy NP menen baylanıslı máselelerdi kemeytiw múmkin bolǵan máseleler). NP klass NP tolıq máselelerdi hám olardan « ańsatlaw» bolǵan máselelerdi óz ishine aladı (yaǵnıy, NP-tolıq máselelerge kemeytiwgen máseleler).
Tariypdan sonday juwmaq kelip shıǵadıki, eger NP-tolıq máselesi polinomial waqıtta sheshetuǵın algoritm tapılsa, ol jaǵdayda barlıq NP-tolıq máseleler P klasqa jaylastırıladı, yaǵnıy olar polinomial waqıtta sheshiledi.
Eger máseleniń qisim máseleleri ámeldegi bolsa ol kúshli NP-tolıq másele dep ataladı, bunda : Máseleniń cifrlı parametrleri ámeldegi bolmasa (yaǵnıy, bul máselede ushraytuǵın shamalardıń maksimal ma`nisi polinom uzınlıǵı menen joqarıdan shegaralanǵan ).
Máseleniń cifrlı parametrleri ámeldegi bolmasa (yaǵnıy, bul máselede ushraytuǵın shamalardıń maksimal ma`nisi polinom uzınlıǵı menen joqarıdan shegaralanǵan ).

NP-to'liklik másele.

Bunday wazıypalar klası NPCS dep ataladı. Eger P ≠ NP gipotezasi tuwrı bolsa, ol jaǵdayda NPCS máselesi ushın jalǵanopolinomial algoritm joq.
NP-to'liklik máselege mısallar

Bul formulaları orınlanıwı máselesi

« Daqlar» n × n ólsheminiń eń qısqa sheshimi

Kommivoyajyora máselesi

Shteyner mashqalası

Qananı boyaw máselesi

Taraw (maydan ) qatlamı máselesi

Jıynaqtı oraw máselesi

Tańlaw máselesi

Jıynaqtıń ǵárezsizligi máselesi

Saper (oyın )

Tetris.
NP – tolıq máselelerdi sheshiw usıllarınıń klassifikaciyası

Kóp qızıqlı hám ámeliy máselelerdi polynomial waqıtta sheshiw múmkin emes yamasa olar ushın házirgi waqıtta polinomial algoritmlar tabilǵan zatǵan. NP (Nondeterminictic Polinomial) quramalılıq klası daǵı másele – bul sonday máseleler klasıdirki, olardı sheshiw ushın polinomial algoritm ámeldegi bolmawi múmkin, lekin eger biz onıń sheshimin bilsek (mısalı, biz bunı shama menen tapqan bolsaq ), ol jaǵdayda polinominal waqıt ishinde onıń tuwrılıǵın tekseriw múmkin. Bul klass ishinde NP-tolıq máselelerge bólek itibar beriledi. Bul máselelerdi sheshiw ushın polynomial algoritmlar ele tabilǵan zatǵan. Biraq bul klasstaǵı barlıq máselelerdi bir-birine keltiriw múmkin. Yaǵnıy, eger NP tolıq máselelerdiń qanday da qandayda birsin polynomial waqıt ishinde sheshiw múmkin bolsa, bul bul klasstaǵı barlıq basqa máselelerpolinomial waqıtta nátiyjeli hal etiliwin ańlatadı.
Búgingi kunga shekem, kópshilik qánigeler NP tolıq máselelerdi polinomial waqıt ishinde hal etip bolmaydı, yaǵnıy NP≠P dep esaplasadı (bul jerde P – polinomial waqıt ishinde sheshiliwi múmkin bolǵan máseleler klası ), biraq bunı tastıyıqlay almadılar. Biraq sońǵı payıtlarda bul kózqarastı biykar etiwge urınıslar bar. Yaǵnıy, bul ilimiy tartıs daǵı noqat ele anıqlanbaǵan. NP klası daǵı kóplegen máseleler ushın (bunday máseleler bir neshe mińlaǵan anıqlanǵan) sheshimlerdiń nátiyjeli algoritmları qashannan berli islep shıǵılǵan yamasa olardıń tolıqlıǵı tastıyıqlanǵan. Soǵan qaramay, bul máselede esaptan tısqarılar bar.

NP tolıq máselerni sheshiwdiń keskin ámeliy mútajlikleri bizni olardı sheshiw menen baylanıslı qıyınshılıqlardı jeńiw jolların izlewge májbúr etedi. Bunday jollar retinde tómendegilerdi atap kórsetiw múmkin: evristik (jaqınlasqan ) sheshimlerdi tabıw, qıdırıw algoritmların jetilistiriw, máselelerdiń ólshemlerine eksponential dárejede baylanıslı bolǵan kestelerden paydalanıwshı dinamikalıq programmalastırıw. Jańa máselege dus kelingende, birinshi náwbette soraw tuwılıwı tábiyiy: « Kórip shıǵılıp atırǵan máseleni polinomial algoritm járdeminde hal qilsa bola ma? «. Eger bul sorawǵa juwap unamlı bolıp shıqsa, ol jaǵdayda NP-tolıqlıq teoriyası kózqarasınan mashqala haqqında hesh nárse deyiw múmkin emes. Keyingi háreketlerimizni ılajı bolǵanınsha eń nátiyjeli polinomial algoritmlardı tabıwǵa jıynashimiz múmkin. Biraq, eger máseleni sheshiw ushın polinomial algoritmı málim bolmasa, ekinshi soraw tuwıladı : « Bul másele NP-tolıqlıǵı rostmi? « Sonı eslep qalıńki, birpara jaǵdaylarda bizni qızıqtırarlıq máseleniń polinomial sheshimge egaligi ańsatǵana ornatıladı, basqalarında bolsa onıń NP-tolıqlıǵı ayqın kórinip turadı.

Biraq kópshilik kóbinese, berilgen sorawlardıń hár birine juwap tabıw talay qıyınshılıqlı. Máseleniń polynomial waqıt ishinde sheshiliwi yamasa onıń NP-tolıqlıǵı anıq bolmasa, bul eki múmkinshilikten qay-qaysısı haqıyqattan da ámelge asırılǵanlıǵın anıqlaw ushın birpara jumıslar talap etiledi. Sonday etip, máselelerdi analiz qılıwda óz-ara jantasıwdı qóllaw jaqsılaw bolıp tabıladı. Máseleniń NP-tolıqlıǵın bir tárepden tastıyıqlawǵa háreket etip, usınıń menen birge onı sheshiw ushın polinomial algoritmdı izlew usınıs etiledi. Eger másele NP-tolıq bolsa, ol jaǵdayda bul polinomial waqıt ishinde sheship bolmawi ushın kúshli dálil bolıp tabıladı.

NP-tolıq máseleni sheshiwdiń maqul túsetuǵın algoritmın tabıw mashqalasın sheshiwde eki taypa daǵı jantasıw bar bolıp tabıladı. Birinshi gruppa qıdırıw kólemin minimallastırıwǵa qaratılǵan jantasıwdı óz ishine aladı, biraq usı waqıtta eksponentsial waqıt sarp etiw etiliwiniń anıqlıǵı tán alınadı. Izbe-iz tańlap alıw usılı ushın eń kóp isletiletuǵın usıllar qatarına “tarmaqlar hám shegaralar” usılı yamasa « uǵımsız tańlap alıw» usılına tiykarlanǵan usıllar kiredi.

Bul metodlar qıdırıw tereki formasında usınıs etilgen « bólekan sheshimler» ni qurıwdan ibarat bolıp, ol jaǵdayda bólekan sheshimlerdi anıqlawǵa múmkinshilik beretuǵın bahalawdıń kúshli usılların qóllaw, nátiyjede bir qádemde qıdırıw tereginen pútkil bir shaq (tarmaq ) kesiledi. Qıdırıw procesi basqasha islengende basqa jantasıwlar da málim (olar geyde “shaqlar hám shegaralar” usılı menen birgelikte isletiledi). Bularǵa dinamikalıq programmalastırıw usılı, kesiw usılları kiredi

Ekinshi taypaǵa tiyisli jantasıwlar tek optimallastırıw máselelerine salıstırǵanda qollanıladı (biraq bul júdá kúshli sheklew emes, sebebi ámelde júzege keletuǵın júdá kóp máseleler optimallastırıw sıyaqlı qáliplestirilgen) hám « shártlerdi kemeytiw» sıyaqlı usıllardı óz ishine aladı. Bul optimal sheshimdi izlewden waz keshiw hám maqul túsetuǵın waqıt ishinde jaqsı sheshimdi tabıwdan ibarat. Bul usılǵa tiykarlanǵan algoritmlar ádetde evristik yamasa shamalıq dep ataladı, sebebi olar qatań tiykarlashsiz hár qıylı oy-pikirlerdi isletediler.

Bul túrdegi algoritmlardı dúziwde isletiletuǵın usıllar masavazifaning qásiyetlerine júdá baylanıslı hám algoritmdıń qanaatlanǵan qásiyetlerin alıw ushın ádetde onı « jetilistiriw» boyınsha kóp miynet talap etiledi. Nátiyjede, tek kemnen-kem jaǵdaylarda, bunday algoritmlardıń minez-qulqların aldınan shama qılıw hám bahalaw múmkin. Bunıń ornına, bunday algoritmlar empirik maǵlıwmatlar hám logikalıq dáliller kombinatsiyası tiykarında bahalanadı hám salıstırıwlanadı.

Birpara jaǵdaylarda evristik algoritm járdeminde alınǵan sheshimler mudamı maqul túsetuǵın sheshimnen procent muǵdarında málim muǵdardan aspawı tastıyıqlanıwı múmkin. Soǵan uqsas nátiyjelerdi algoritmlardıń « qátelerin bahalaw» retinde kórip shıǵıw múmkin. Sonday etip, shamalıq algoritmlardıń tiykarǵı sapa kórsetkishlerinen biri onıń járdemi menen alınǵan máseleniń anıq sheshiminen iyiwi bolıp tabıladı. Bunnan tısqarı, ádetde bul iyiw eń jaman jaǵdayda bahalanadı, yaǵnıy maksimal iyiw barlıq múmkin bolǵan maǵlıwmatlar dáregi ushın alınadı. Eger sonday ólshew degi NP-tolıq máselelerdi sheshiw zárúr bolsa hám siz shamalıq algoritmlarǵa shaqırıq etiwge májbúr bolsańız, ol jaǵdayda bunday algoritmlardıń sapasın bahalawda kompyuter esap -kitaplarınıń nátiyjesi tiykarǵı faktor boladı.

NP klasına tiyisli ekenligi tastıyıqlanbaǵan, biraq olarǵa NP – tolıq máseleler keltiriletuǵın máseleler NP-quramalı dep ataladı. Bul klass NP-tolıq máselelerdiń kóplegen optimallastırıw variantların óz ishine aladı.
Grafik daǵı shıńlar kompleksi, eger bul jıynaqtıń eki uchi bir shet menen baylanıspaǵan bolsa, ǵárezsiz dep ataladı. Basqasha etip aytatuǵın bolsaq, bul jıynaq tárepinen induktsiya etilgen tómengi grafik izolyatsiya etilgen tóbelerden ibarat. Sonıń menen birge, geyde grafikdıń hár bir shetsi ǵárezsiz jıynaqtıń kópi menen bir shıńina tuwrı keledi, dep da aytıladı. Teńib alıw máselesi (sheshiw máselesi) tómendegishe kórinedi: berilgen G grafigi k ólshem degi ǵárezsiz jıynaqǵa egami?
Oǵan sáykes keletuǵın optimallastırıw máselesi ǵárezsiz jıynaq máselesi dep da ataladı, tómendegishe dúzilgen: berilgen G grafigida maksimal ólshem degi ǵárezsiz jıynaqtı tabıw talap etiledi. Bul ólshem ǵárezsizlik sanı, ishki tıǵızlıq sanı yamasa boslıq dep ataladı hám a (G) menen belgilenedi.
9 kók múyeshning ǵárezsiz kompleksi
Bul másele geyde eń úlken ǵárezsiz jıynaqtı tabıw dep ataladı. Bul kontseptsiyanı maksimal ǵárezsiz jıynaq yamasa qosıw arqalı maksimal ǵárezsiz jıynaq menen aralastırıp jibermaslik kerek, bul sonday ǵárezsiz shıńlar kompleksi retinde belgilenediki, oǵan túp grafikdıń taǵı bir (hár qanday ) shıńı qosılsa, ol toqtaydı. ǵárezsiz bolıń (ulıwma aytqanda, bunday jıynaqlar bir neshe hám túrli ólshem degi bolıwı múmkin). Inklyuziya-maksimal ǵárezsiz jıynaq mudamı da eń úlken emes. Usınıń menen birge, hár bir eń úlken ǵárezsiz jıynaq, tariypiga kóre, qosıw boyınsha da maksimal bolıp tabıladı. Qosıw boyınsha (birpara ) maksimal ǵárezsiz jıynaqtı tabıw ushın polinom waqtında isleytuǵın ashkóz algoritmnan paydalanıw múmkin, eń úlken ǵárezsiz jıynaq máselesi bolsa NP-tolıq máseleler klasına tiyisli.
Optimal quyistruktura máselesi
Terektiń dúzilisi bul máseleni sheshiwdi usınıs etedi. Yaǵnıy, hár qanday shıńnı terektiń túbiri retinde belgileymiz jáne onı r dep ataymız. Ol ® de túbir otgan tómengi terektiń eń úlken ǵárezsiz shıńlar kompleksiniń ólshemin bildirsin. Ol halda máseleniń juwabı I ®.
Kórinip turıptı, olda, eger ol shıńnı eń úlken ǵárezsiz jıynaqǵa kiritsak, ol halda onıń tiykarǵılıǵı 1 ge artadı, lekin biz onıń balaların ololmaymiz (sebebi olar ol shıń menen shet menen baylanısqan ); eger biz bul shıńnı kiritpesak, ol halda eń úlken ǵárezsiz jıynaqtıń kardinalligi bul shıńdıń ǵárezsiz jıynaqları ólshemleri jıyındısına teń boladı. Máseleni sheshiw ushın bul eki varianttan maksimalın tańlaw qaladı :
Bul jerde grandchild shıńdıń qálegen “aqlıǵı”ni, child bolsa shıńdıń hár qanday áwladın ańlatadı.

Function get_independent_set (Node ol)

{

Eger I (ol) qashannan berli esaplanǵan, keyin I ® ni qaytarıń

// jıynaqtıń anıqlıǵı, eger ol uchini almasak, alınıwı múmkin children_sum = 0

Grandchildren_sum = 0

// barlıq child ushın cikl

For i := 1 tap child_num do

Children_sum = children_sum + get_independent_set (children[i])

// barlıq aqlıqlar ushın cikl

For i:= 1 tap grandchildren_num

Grandchildren_sum = grandchildren_sum + get_independent_set (grandchildren[i])

// qayta esaplamaslik ushın eslab qoling

I (ol) = max (1 + grandchildren_sum, children_sum)

Vozvratit' I (ol)

}

Paydalanıg'an a'debiytlar.

Geri M., Djonson D. Vыchislitelnыe mashinы i trudnoreshayemыe zadachi. M.: Mir, 1982.

Tomas X. Kormen i dr. Bob. 34 NP-polnota // Algoritmы: postroyeniye i analiz = Introduction to Algorithms. — 2-e izd. — M.: «Vilyams», 2006. — 1296 s. — ISBN 0-07-013151-1.

Djon Xopkroft, Radjiv Motvani, Djeffri Ulman. Vvedeniye v teoriyu avtomatov, yazыkov i vыchisleniy = Introduction to Automata Theory, Languages, and Computation. — M.: «Vilyams», 2002. — 528 s. — ISBN 0-201-44124-1.