Reja: Algoritm tushunchasi

14-mavzu. NP-to’liq masalalarni yechish algoritmlari

Plan:

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).