Mustaqil ishi qabul qildi: Ergashev. O topshirdi: Shamsuddinov. H mavzu: np- to’liq masalalar. Hisoblashda yechilmaslik hollari. Reja: np-to‘liklik masalasi

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 algoritm (evristik) - bu masalani hal qilish algoritmi, shu jumladan aniq yoki optimal bo'lishi kafolatlanmagan, ammo qo’yilgan masalani hal qilish uchun yetarli bo'lgan amaliy usul. Aniq yechimni topa olmagan holatlarda muammoni hal qilishni tezlashtirishga imkon beradi.
Evristik algoritm - bu barcha mumkin bo'lgan holatlarda uning to'g'riligi isbotlanmagan, ammo ko'p hollarda juda yaxshi yechim topishi ma'lum bo'lgan masalani hal qilish algoritmi. Aslida, hatto evristik algoritm rasman noto'g'ri ekanligi ham ma'lum bo'lishi mumkin (ya'ni isbotlangan). Agar u bir vaqtning o'zida noto'g'ri natijani faqat alohida, juda kam uchraydigan va alohida ajratilgan hollarda bersa yoki noaniq, ammo baribir maqbul natijani beradigan bo'lsa, undan foydalanish mumkin.
Oddiy qilib aytganda, evristika mutlaqo matematik asoslangan emas (yoki "umuman to'g'ri emas"), ammo bu amaliy foydali algoritmdir. Masalani hal qilishning aniq algoritmidan farqli o'laroq, 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
  

Xulosa:

Adabiyotlar

1. 
   Geri M., Djonson D. Vыchislitelnыe mashinы i trudnoreshayemыe zadachi. M.: Mir, 1982.
   
2. 
   Tomas X. Kormen i dr. Bob. 34 NP-polnota // Algoritmы: postroyeniye i analiz = Introduction to Algorithms. — 2-e izd. — M.: «Vilyams», 2006. — 1296 s. — ISBN 0-07-013151-1.
   
3. 
   Djon Xopkroft, Radjiv Motvani, Djeffri Ulman. Vvedeniye v teoriyu avtomatov, yazыkov i vыchisleniy = Introduction to Automata Theory, Languages, and Computation. — M.: «Vilyams», 2002. — 528 s. — ISBN 0-201-44124-1.
   

http://fayllar.org