Toshkent 2023 Mavzu: p va np sinflar, np- to‘liq masalalar tushunchasi Reja: p va np sinflarining tengligi muammosi

NP-to’liq masalalarni yechish algoritmlari

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.