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

NP – to’liq masalalarni yechish usullari
Aniq usullar
Taqribiy usullar
To’liq qayta tanlash
Dinamik dasturlash
Tarmoqlar va chegaralar
Ochko’z va gradiyent usullar
Tasodifiy usullar
FF turidagi usullar
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.
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.
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.
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.
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 X1 element uchun shunday X2 elementni toppish kerakki, bunda X1 < X2 bo’lsin hamda X1 va X2 elementlar o'rtasida boshqa elementlar mavjud bo'lmasin).