14-amaliy ish np-to’liq masalalar np-to’liq masalalarga keltirish usullari

14-amaliy ish


NP-to’liq masalalar. NP-to’liq masalalarga keltirish usullari

Reja:

1. NP – to’liq masalalarni yechish usullarining tasnifi
2. To'liq qayta tanlash(Полный перебор) usuli
3. NP to'liq masalalarni hal qilish uchun evrestik algoritmlar
4. Kommivoyajer masalasi uchun algoritmlar


1. NP – to’liq masalalarni yechish usullarining tasnifi

Ko'p qiziqarli va amaliy masalalarni polynomial vaqtda hal qilish mumkin emas yoki ular uchun hozirgi vaqtda polinomial algoritmlar topilmagan. NP(Nondeterminictic Polinomial) murakkablik sinfidagi masala - bu shunday masalalar sinfidirki, ularni yechish uchun polinomial algoritm mavjud bo'lmasligi mumkin, lekin agar biz uning yechimini bilsak (masalan, biz buni taxminan topgan bo’lsak), unda polinominal vaqt ichida uning to'g'riligini tekshirish mumkin. Ushbu sinf ichida NP-to'liq masalalarga alohida e’tibor beriladi. Ushbu masalalarni hal qilish uchun polynomial algoritmlar hali topilmagan. Ammo bu sinfdagi barcha masalalarni bir-biriga keltirish mumkin. Ya'ni, agar NP to’liq masalalarning qandaydir birontasini polynomial vaqt ichida hal qilish mumkin bo'lsa, bu ushbu sinfdagi barcha boshqa masalalarpolinomial vaqtda samarali hal qilinishini anglatadi.

Bugungi kunga qadar, ko'pchilik mutaxassislar NP to’liq masalalarni polinomial vaqt ichida hal qilib bo’lmaydi, ya'ni NP≠P deb hisoblashadi (bu yerda P - polinomial vaqt ichida yechilishi mumkin bo'lgan masalalar sinfi), ammo buni isbotlay olmadilar. Ammo so'nggi paytlarda ushbu nuqtai nazarni inkor etishga urinishlar mavjud. Ya'ni, ushbu ilmiy munozaradagi nuqta hali aniqlanmagan. NP sinfidagi ko'pgina masalalar uchun (bunday masalalar bir necha minglab aniqlangan) yechimlarning samarali algoritmlari allaqachon ishlab chiqilgan yoki ularning to'liqligi isbotlangan. Shunga qaramay, ushbu masalada istisnolar mavjud.
NP to’liq masalarni hal qilishning keskin amaliy ehtiyojlari bizni ularni hal qilish bilan bog'liq qiyinchiliklarni yengish yo'llarini izlashga majbur qiladi. Bunday yo'llar sifatida quyidagilarni qayd etish mumkin: evristik (yaqinlashgan) yechimlarni topish, qidiruv algoritmlarini takomillashtirish, masalalarning o'lchamlariga eksponential darajada bog'liq bo'lgan jadvallardan foydalanuvchi dinamik dasturlash. Yangi masalaga duch kelinganda, birinchi navbatda savol tug'ilishi tabiiy: "Ko'rib chiqilayotgan masalani polinomial algoritm yordamida hal qilsa bo'ladimi?". Agar ushbu savolga javob ijobiy bo'lib chiqsa, unda NP-to'liqlik nazariyasi nuqtai nazaridan muammo haqida hech narsa deyish mumkin emas. Keyingi harakatlarimizni iloji boricha eng samarali polinomial algoritmlarni topishga jamlashimiz mumkin. Ammo, agar masalani hal qilish uchun polinomial algoritmi ma'lum bo'lmasa, ikkinchi savol tug'iladi: "Bu masala NP-to’liqligi rostmi?" Shuni yodda tutingki, ba'zi holatlarda bizni qiziqtiradigan masalaning polinomial yechimga egaligi osongina o'rnatiladi, boshqalarida esa uning NP-to'liqligi yaqqol ko'rinib turadi.
Ammo aksariyat ko’p hollarda, berilgan savollarning har biriga javob topish ancha mushkul. Masalaning polynomial vaqt ichida yechilishi yoki uning NP-to'liqligi aniq bo’lmasa, bu ikki imkoniyatdan qaysi biri haqiqatan ham amalga oshirilganligini aniqlash uchun ba'zi ishlar talab etiladi. Shunday qilib, masalalarni tahlil qilishda ikki tomonlama yondashuvni qo'llash yaxshiroqdir. Masalaning NP-to'liqligini bir tomondan isbotlashga harakat qilib, shu bilan birga uni hal qilish uchun polinomial algoritmni izlash tavsiya etiladi. Agar masala NP-to’liq bo'lsa, unda bu polinomial vaqt ichida yechib bo'lmasligi uchun kuchli dalildir.
NP-to'liq masalani hal qilishning maqbul algoritmini topish muammosini hal qilishda ikkita toifadagi yondoshuv mavjuddir. Birinchi guruh qidiruv hajmini minimallashtirishga qaratilgan yondoshuvni o'z ichiga oladi, ammo ayni paytda eksponentsial vaqt sarf qilinishining muqarrarligi tan olinadi. Ketma-ket tanlab olish usuli uchun eng ko’p ishlatiladigan usullar qatoriga “tarmoqlar va chegaralar” usuli yoki "noaniq tanlab olish" usuliga asoslangan usullar kiradi.
Ushbu metodlar qidiruv daraxti shaklida taqdim etilgan "qisman yechimlar" ni qurishdan iborat bo'lib, unda qisman yechimlarni aniqlashga imkon beradigan baholashning kuchli usullarini qo'llash, natijada bir qadamda qidiruv daraxtidan butun bir shox (tarmoq) kesiladi. Qidiruv jarayoni boshqacha tashkil etilganda boshqa yondashuvlar ham ma'lum (ular ba'zan “shoxlar va chegaralar” usuli bilan birgalikda ishlatiladi). Bularga dinamik dasturlash usuli, kesish usullari kiradi
Ikkinchi toifaga tegishli yondashuvlar faqat optimallashtirish masalalariga nisbatan qo'llaniladi (ammo bu juda kuchli cheklov emas, chunki amalda yuzaga keladigan juda ko'p masalalar optimallashtirish kabi shakllantirilgan) va "shartlarni kamaytirish" kabi usullarni o'z ichiga oladi. Bu optimal yechimni izlashdan voz kechish va maqbul vaqt ichida yaxshi yechimni topishdan iborat. Ushbu uslubga asoslangan algoritmlar odatda evristik yoki taxminiy deb nomlanadi, chunki ular qat'iy asoslashsiz turli xil mulohazalarni ishlatadilar.
Ushbu turdagi algoritmlarni tuzishda ishlatiladigan usullar masavazifaning xususiyatlariga juda bog'liq va algoritmning qoniqarli xususiyatlarini olish uchun odatda uni "takomillashtirish" bo'yicha ko'p mehnat talab etiladi. Natijada, faqat kamdan-kam hollarda, bunday algoritmlarning xatti-harakatlarini oldindan taxmin qilish va baholash mumkin. Buning o'rniga, bunday algoritmlar empirik ma'lumotlar va mantiqiy dalillar kombinatsiyasi asosida baholanadi va taqqoslanadi.
Ba'zi hollarda evristik algoritm yordamida olingan yechimlar har doim maqbul yechimdan foiz miqdorida ma'lum miqdordan oshmasligi isbotlanishi mumkin. Shunga o'xshash natijalarni algoritmlarning "xatolarini baholash" sifatida ko'rib chiqish mumkin. Shunday qilib, taxminiy algoritmlarning asosiy sifat ko'rsatkichlaridan biri uning yordami bilan olingan masalaning aniq yechimidan og'ishidir. Bundan tashqari, odatda bu og'ish eng yomon holatda baholanadi, ya'ni maksimal og'ish barcha mumkin bo'lgan ma'lumotlar manbai uchun olinadi. Agar shunday o'lchovdagi NP-to'liq masalalarni hal qilish zarur bo'lsa va siz taxminiy algoritmlarga murojaat qilishga majbur bo'lsangiz, unda bunday algoritmlarning sifatini baholashda kompyuter hisob-kitoblarining natijasi asosiy omil bo’ladi.
NP sinfiga tegishli ekanligi isbotlanmagan, ammo ularga NP - to'liq masalalar keltiriladigan masalalar NP-murakkab deb nomlanadi. Bu sinf NP-to’liq masalalarning ko'plab optimallashtirish variantlarini o'z ichiga oladi.
NP-to'liq masalalarning namunalari:

• 
  Bool formulalarining bajarilish masalasi
  
• 
  “O’n beshlik” o'yinining eng qisqa yechimi
  
• 
  Kommivoyajer masalasi
  
• 
  Shteyner muammosi
  
• 
  Grafni bo'yash muammosi
  
• 
  Graf cho’qqisini qoplash masalasi
  
• 
  To’plamni qoplash masalasi
  
• 
  Graf cho’qqilarining mustaqil to’plamlari masalasi
  
• 
  Saper o’yini
  
• 
  Tetris o’yini
  

NP-murakkab masalalarni hal qilish usullari quyidagilarga bo'linadi:

• 
  aniq,
  
• 
  evristik
  
• 
  metaevristik usullari
  

Aniq usullar barcha mumkin bo'lgan yechimlarni to'liq ko’rib chiqishga (полный перебор) asoslanadi va bu o'z navbatida ularning samadorligini kamaytiradi. Evristik usullar yechimlarni nisbatan cheklangan qidirishga olib keladi va odatda maqbul vaqt ichida juda yaxshi yechimni topadi. Ammo bu usullar ham kamchilikka ega, ya'ni ular taxminiydir. Metaevristik usullar eng samarali hisoblanadi, ammo bu usullarda natijaga bevosita ta'sir qiladigan parametr mavjud, kirish ma'lumotlariga asoslanib, amalda har safar ushbu parametrni qayta hisoblash kerak.
Evristik metodlar eng katta hisoblash murakkabligiga ega. Metaevristik usullar ko'proq maqbul hisoblanadi. Lokal qidiruv usuliga asoslangan klassik evristik usullardan metaevristik metodlarning ustunligi shundaki, ular sizga eng katta yechim maydonini tadqiq qilib optimal yechimga yaqin yechimni topish imkonini beradi, lokal qidirish usullari esa lokal yechimni topgandan keyin to'xtaydi.

2. To'liq qayta tanlash(Полный перебор) usuli

Umumiy holatda bu usul, aksariyat shafqatsiz kuch usullari kabi samarasiz bo'lsa ham, ba'zi holatlarda bu juda maqbuldir. To'liq qayta tanlash (yoki shafqatsiz kuch) usuli bu matematik masalalarni hal qilish usulidir. Bu barcha variantlarni ko’rib chiqib, yechim topish usullari sinfiga tegishli. To'liq qayta tanlashning murakkabligi muammoni hal qilishning barcha mumkin bo'lgan yechimlari soniga bog'liq. Agar qaror qabul qilish maydoni juda katta bo'lsa, unda to'liq qayta tanlash bir necha yil yoki hatto asrlar davomida natijalarga olib kelmasligi mumkin.

NP sinfidagi har qanday muammoni to'liq qayta tanlash usuli orqali hal qilish mumkin. Bu holda, har qanday aniq yechimdan maqsad funktsiyani hisoblash polinomial vaqt ichida amalga oshirilishi mumkin bo'lsa ham, barcha mumkin bo'lgan echimlarning soniga qarab to'liq qayta tanlash eksponensial vaqtni talab qilishi mumkin.
Kriptografiyada shifrlarning kriptografik mustahkamlik to'liq qayta tanlashning hisoblash murakkabligiga asoslanadi. Xususan, shifrlash kriptografik mustahkam hisoblanadi, agar barcha kalitlarning to'liq qayta tanlanishidan ancha tezroq ishlaydigan «buzish» usuli bo'lmasa. To'liq qayta tanlash usuliga asoslangan kriptografik hujumlar eng universal, ammo eng uzoq vaqtda ishlaydigan usullardir.
To'liq qayta tanlash usulining mohiyati shundan iboratki:
a) barcha mumkin bo'lgan holatlarni ko'rib chiqish;
b) berilgan masalaning shartini qanoatlantiradigan yechimlarni topish;
c) boshqa yechimlar yo'qligini ko'rsatish.
Masalan, massivda maksimal sonni qidirish, ma'lumotlar faylidagi kerakli yozuvni qidirish va h.k. Bunday qidirish ma'lumotlar strukturasining barcha elementlarini sanab chiqish va ularni qidirish holatini qondirish uchun tekshirish orqali amalga oshiriladi. Tarkibning barcha elementlari ko'rib chiqilgan qidiruv to’liq qayta tanlash deyiladi. Ko'pgina amaliy masalalarda juda katta (lekin cheklangan!) variantlar orasida maqbul yechimni topish talab etiladi. Ba'zan ushbu yechimga darhol ega bo’lish mumkin, lekin ko'p holatlarda uni topishning yagona yo'li bu barcha variantlarni to’liq ko’rib chiqish va ularni bir-biri bilan solishtirishdir.
To'liq qayta tanlash sxemasi doimo bir xil bo'ladi:

• 
  birinchidan, sanab o’tiladigan elementlarni tartiblash kerak (xususan, qaysi biri birinchi va oxirgisi bo'lishini aniqlash);
  
• 
  ikkinchidan, ixtiyoriy elementdan bevosita keyingisiga qanday o'tish kerakligini o’rganish (ya'ni, berilgan X₁ element uchun shunday X₂ elementni toppish kerakki, bunda X₁ < X₂ bo’lsin hamda X₁ va X₂ elementlar o'rtasida boshqa elementlar mavjud bo'lmasin).
  

3. NP to'liq masalalarni hal qilish uchun evrestik algoritmlar

Evristika yoki evristik algoritm – algoritm deb ta’riflanishi uchun quyidagi hususiyatlarga ega bo’lishi kerak:

1. U odatda shartli ravishda optimal bo’lmasa ham, yahshi yechimlarni topish kerak.
2. Uni ixtiyoriy ma’lum aniq algoritmdan ko’ra, amalga oshirish tezroq va soddaroq bo’lishi kerak.
Odatda yahshi algoritmlar evristik bo’lib chiqadi. Faraz qilaylik, biz tez ishlaydigan va barcha test topshiriqlariga javob beradigan algoritmni tuzdik, lekin uning to’g’riligini isbotlab bilmaymiz. Shunday isbot berilmaguncha, algoritm evristik deb tushuniladi.
Evristika (boshqa yunon tilidan: εὑρίσκω - "qidiraman", "kashf qilaman") - bu bilim sohasi, ijodiy faoliyatning o'ziga xos xususiyatlarini o'rganadigan ilmiy soha. Evristika deganda kognitiv, konstruktiv, amaliy masalalarni hal qilishni osonlashtiradigan sodda usullar va uslublarning umumlashgan majmuasi tushuniladi.
Evristik algoritm (evristik) - bu masalani hal qilish algoritmi, shu jumladan aniq yoki optimal bo'lishi kafolatlanmagan, ammo qo’yilgan masalani hal qilish uchun yetarli bo'lgan amaliy usul. Aniq yechimni topa olmagan holatlarda muammoni hal qilishni tezlashtirishga imkon beradi.
Evristik algoritm - bu barcha mumkin bo'lgan holatlarda uning to'g'riligi isbotlanmagan, ammo ko'p hollarda juda yaxshi yechim topishi ma'lum bo'lgan masalani hal qilish algoritmi. Aslida, hatto evristik algoritm rasman noto'g'ri ekanligi ham ma'lum bo'lishi mumkin (ya'ni isbotlangan). Agar u bir vaqtning o'zida noto'g'ri natijani faqat alohida, juda kam uchraydigan va alohida ajratilgan hollarda bersa yoki noaniq, ammo baribir maqbul natijani beradigan bo'lsa, undan foydalanish mumkin.
Oddiy qilib aytganda, evristika mutlaqo matematik asoslangan emas (yoki "umuman to'g'ri emas"), ammo bu amaliy foydali algoritmdir. Masalani hal qilishning aniq algoritmidan farqli o'laroq, evristik algoritmlar quyidagi xususiyatlarga ega ekanligini tushunish muhimdir:

• 
  yaxshiroq yechimni kafolatlamaydi.
  
• 
  garchi u aniq mavjud bo'lsa ham, yechimni topishga kafolat bermaydi.
  
• 
  Ba'zi hollarda u noto'g'ri qaror qabul qilishi mumkin.
  

Hisoblash murakkabligi yuqori bo’lgan masalalarni hal qilish uchun evristik algoritmlardan keng foydalaniladi. Ya’ni ko’p vaqt talab qiladigan va ba’zan texnik jihatdan imkonsiz barcha variantlarni to’liq qayta ko’rib chiqadigan algoritm o’rniga ancha tezroq, ammo yetarlicha nazariy asoslanmagan algoritm qo’llaniladi.

• 
  Taqribiy va evristik usullar - yechim elementlarini tanlash uchun evristikadan foydalanish.
  
• 
  Psevdopolinomial algoritmlar - dinamik dasturlash sinfiga oid algoritmlar.
  
• 
  Local yahshilash usuli - ba'zi bir mavjud yechim atrofida eng maqbul yechim izlash.
  
• 
  Tarmoqlar va chegaralar usuli - ba'zi baholashga ko'ra maqbul bo'lmagan yechimlarning barcha sinflarini bekor qilish.
  
• 
  Tasodifiy qidiruv usuli - tanlovni tasodifiy tanlovlar ketma-ketligi bilan ifodalash.
  

Yaqinlashtiruvchi(approksimatsion) algoritmlar polinomial vaqt ichida bajariladi va optimal darajaga yaqin bo'lish kafolati bo'lgan yechimlarni topadi.
Algoritmlarni ishlab chiqish uchun to'rtta umumiy metodologiya:

1. 
   Birinchi umumiy metodologiya tez va oson bajariladigan ochko'z algoritmlardir. Asosiy muammo bu optimalga yaqin maqbul yechimlarga olib keluvchi ochko'z algoritm qoidalarini topishdir.
   
2. 
   Ikkinchi umumiy metodologiya – narxlarni belgilash usuli - iqtisodiy asoslangan; masaladagi har bir cheklovga rioya qilish uchun to'lanishi kerak bo'lgan narxni ko'rib chiqiladi.
   
3. 
   Uchinchi umumiy metodologiya – Butun sonli chiziqli dasturlash usulidir. Butun sonli dasturlash masalasi ham chiziqli dasturlash masalasidek qo’yilib, optimal yechim o’zgaruvchilarning qiymati butun musbat son bo’lsin, degan qo’shimcha talab qo’yiladi.
   
4. 
   To’rtinchi umumiy metodologiya – dinamik dasturlash usuli bo’lib, optimallashtirish muammolarini hal qilishda, ma'lum cheklovlarni hisobga olgan holda, maksimal yoki minimal echimni qidiradigan muammolar uchun foydali usuldir, chunki u barcha mumkin bo'lgan kichik muammolarni ko'rib chiqadi va hech qachon biron bir sub-muammoning yechimini qaytarmaydi.
   

Yaqinlashtiruvchi(approksimatsion) algoritmlarning tasnifi:

• 
  kafolatlangan faoliyat ko’rsatuvchi algoritmlari;
  
• 
  lokal optimallashtirish algoritmlari va evristik protseduralar;
  
• 
  lokal optimallashtirish algoritmlari va evristik protseduralardan foydalanuvchi birlashtirilgan algoritmlar;
  
• 
  taqribiy yechimlarga erishish uchun aniq usullarning elementlaridan foydalanuvchi algoritmlar;
  
• 
  "tarmoqlar va chegaralar" kabi birlashtirilgan algoritmlar, katta o'lchamdagi masalalarni hal qilish algoritmlari.