Bajardi: Abdullayev Bahriddin Shakarov Samandar mavzu: Np-to’liq masalalarni yechish uchun algoritmlarini qiyinligini baholash

O’ZBEKISTON RESPUBLIKASI AXBOROT TEXNOLOGIYALARI VA KOMMUNIKATSIYALARINI RIVOJLANTIRISH VAZIRLIGI
Muhammad Al-Xorazmiy nomidagi Toshkent Axborot Texnologiyalari Universiteti
Algoritmlarni loyihalash
Mustaqil ishi
Bajardi:Abdullayev Bahriddin
Shakarov Samandar

MAVZU: Np-TO’LIQ MASALALARNI YECHISH UCHUN ALGORITMLARINI QIYINLIGINI BAHOLASH. 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. 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.
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.
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