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

3. NP to'liq masalalarni hal qilish uchun evrestik algoritmlar
Evristika yoki evristik algoritm – algoritm deb ta’riflanishi uchun quyidagi hususiyatlarga ega bo’lishi kerak:
1. U odatda shartli ravishda optimal bo’lmasa ham, yahshi yechimlarni topish kerak.
2. Uni ixtiyoriy ma’lum aniq algoritmdan ko’ra, amalga oshirish tezroq va soddaroq bo’lishi kerak.
Evristika (boshqa yunon tilidan: εὑρίσκω - "qidiraman", "kashf qilaman") - bu bilim sohasi, ijodiy faoliyatning o'ziga xos xususiyatlarini o'rganadigan ilmiy soha. Evristika deganda kognitiv, konstruktiv, amaliy masalalarni hal qilishni osonlashtiradigan sodda usullar va uslublarning umumlashgan majmuasi tushuniladi.
Evristik algoritmlar quyidagi xususiyatlarga ega ekanligini tushunish muhimdir:

• yaxshiroq yechimni kafolatlamaydi.
• garchi u aniq mavjud bo'lsa ham, yechimni topishga kafolat bermaydi.
• Ba'zi hollarda u noto'g'ri qaror qabul qilishi mumkin.

Hisoblash murakkabligi yuqori bo’lgan masalalarni hal qilish uchun evristik algoritmlardan keng foydalaniladi. Ya’ni ko’p vaqt talab qiladigan va ba’zan texnik jihatdan imkonsiz barcha variantlarni to’liq qayta ko’rib chiqadigan algoritm o’rniga ancha tezroq, ammo yetarlicha nazariy asoslanmagan algoritm qo’llaniladi.

*Taqribiy va evristik usullar - yechim elementlarini tanlash uchun evristikadan foydalanish.
*Psevdopolinomial algoritmlar - dinamik dasturlash sinfiga oid algoritmlar.
*Local yahshilash usuli - ba'zi bir mavjud yechim atrofida eng maqbul yechim izlash.
*Tarmoqlar va chegaralar usuli - ba'zi baholashga ko'ra maqbul bo'lmagan yechimlarning barcha sinflarini bekor qilish.
*Tasodifiy qidiruv usuli - tanlovni tasodifiy tanlovlar ketma-ketligi bilan ifodalash.
4. Kommivoyajer masalasi uchun algoritmlar
Tarmoqlar va chegaralar usuli
Аgar, biz shaharlarni bir marta aylanib chiqishni marshrut deb atasak, aniqki, bunday marshrutlar soni koʼpi bilan (h-1)!ta boʼladi.
Biz tarmoqlar va chegaralar usulini kommivoyajer masalasini yechish uchun qoʼllanishini koʼramiz. Faraz etaylik cij sonlari ishahardan j-shaharga oʼtish uchun ketadigan xarajatni bildirsin. Аgar i shahardan j shaharga oʼtishning iloji boʼlmasa, cij ni yetarlicha katta son deb olamiz (buni cij =∞ deb belgilaymiz), i-shahardan yana i-shaharga oʼtildi, deyish maʼnosiz boʼlganligi sababli cij =∞ deb olinadi.
Shundan soʼng nxn oʼlchamli (cij) jadval (matritsa) hosil boʼladi, u xarajat jadvali deb ataladi. Yana bir bor taʼkidlab oʼtamizki, jadvalning i satri j ustuni kesishgan joydagi cijelement i-shahardan j-shaharga oʼtish uchun ketgan sarf-xarajatni bildiradi. Endi jadvalni keltirish tushunchasini kiritamiz. Buning uchun, avval jadval satrlari keltiriladi, yaʼni jadvalning har bir satr elementlaridan shu satrning kichigi mos ravishda ayirib tashlanadi. Barcha satrlari va ustunlari keltirilgan jadval keltirilgan deb ataladi. Demak, keltirilgan jadvalning har bir satri va ustunida kamida bitta nol element ishtirok etgan boʼladi. Jadval satr va ustunlari eng kichik elementlarining yigʼindisi h bilan belgilanib, u jadvalning keltirish koeffitsienti deyiladi. Misol sifatida quyidagi harajat jadvalini ko’ramiz:
Jadval satrlarini keltirish uchun, uning oʼng tarafiga mos satrning eng kichik elementini yozib chiqamiz va satr elementlaridan uni ayirib quyidagi jadvalga ega boʼlamiz.
Hosil boʼlgan C* jadvalning ustunlarini keltirish maqsadida jadval ostiga mos ustunning eng kichik elementi yoziladi va u ustun elementlaridan ayirib chiqiladi, natijada quyidagi jadval hosil boʼladi. C ** jadval keltirilgan boʼlib, uning har bir satr va ustunida kamida bittadan nol element bor. Koʼrilayotgan jadvalning keltirish koeffitsienti h quyidagi songa teng
h=3+1+2+1+4+4+0+3+0+0+0+0=18.
Keltirish koeffitsienti h eng kam xarajatli oʼtishlarning umumiy harajatini bildirib, bu xarajatni beruvchi marshrutni xar vaqt ham aniqlab boʼlmaydi. Yuqorida koʼrilgan misolda eng kam harajatli (h=18) marshrutni aniqlasak, u ikkita bir biriga bogʼlanmagan oʼtishlardan (tsikllardan) iborat boʼlib qoladi, yaʼni 1→5→3→2→1 va 4→6→4. Bu esa qoʼyilgan masalaning yechimini bermaydi. Demak, jadvalni keltirish bilan har vaqt ham qoʼyilgan masalaning yechimini olib boʼlmas ekan. Umuman, tarmoqlar va chegaralar usuli ikkita muhim bosqichdan iboratdir. 1) tarmoqlash; 2) chegaralarni aniqlash. Bu graf oʼzaro birlashtirilgan doirachalardan iborat boʼlib, ularning har biri maʼlum bir xossali marshrutlar toʼplamini aniqlaydi.
Foydalanilgan adabiyotlar:
*https://en.wikipedia.org/wiki/NP-completeness
*https://arm.tdpushf.uz/kitoblar
E’tiboringiz uchun rahmat!