2
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.
3
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.
