|
Texnologiyalari va kommunikatsiyalarini rivojlantirish vazirligi muhammad al-xorazmiy nomidagi toshkent axborot texnologiyalari universiteti samarqand filiali
|
| bet | 5/6 | | Sana | 17.05.2023 | | Hajmi | 394.27 Kb. | | #61083 |
Bog'liq 4-amaliy Abduqahorov R. Taqsimlangan 4aouLxYxNuuVApyO5uymXDuR5l4wDvxrGkrCXPHB, 1, 6-modul. Buralish deformatsiyasi, article for Sukhrob, 1-amaliy ish Risklarni baholash usullari Ishdan maqsad, MSM, rivojlanishi, 1-topshiriq 511-512-531-532-533, 28-03 03-16, 5 20 guruh talabasi Toshpolotov shahzod optoelektronika fanidan (1), 41uHnjgpJSayA50P8nEHxTVvPwPTV8x8QTy4OkzW, genomika REFARAT, ingliz tili 2, 91. Greedy Choice Mulki. Agar tanlangan oldingi bosqichlarni qayta ko'rib chiqmasdan, har bir bosqichda eng yaxshi tanlovni tanlash orqali muammoning optimal echimini topish mumkin bo'lsa, muammoni ochko'zlik bilan hal qilish mumkin. Bu xususiyat ochko'z tanlov mulki deb ataladi.
2. Optimal quyi tuzilma. Agar muammoning optimal umumiy yechimi uning kichik muammolarining optimal yechimiga mos kelsa, u holda muammoni ochko'z yondashuv yordamida hal qilish mumkin. Bu xususiyat optimal pastki tuzilma deb ataladi.
Algoritmni tasvirlash osonroq .
Bu algoritm boshqa algoritmlarga qaraganda yaxshiroq ishlashi mumkin (lekin hamma hollarda emas).
Ochko'zlik yondashuvining kamchiliklari
Yuqorida aytib o'tilganidek, ochko'zlik algoritmi har doim ham eng maqbul echimni keltirib chiqarmaydi. Bu algoritmning asosiy kamchiligi
Misol uchun, biz quyidagi grafikda ildizdan barggacha bo'lgan eng uzun yo'lni topmoqchimiz deylik. Keling, bu erda ochko'z algoritmdan foydalanamiz.
4.2-rasm.
Eng uzun yo'lni topish uchun bu daraxtga ochko'z yondashuvni qo'llang
Ochko'z yondashuv
1. Keling, ildiz tugunidan boshlaylik 20 . O'ng qismning vazni 3 , chap qismning vazni 2 .
2. Bizning muammomiz eng katta yo'lni topishdir. Va, hozirgi vaqtda optimal yechim 3 dir . Shunday qilib, ochko'z algoritm 3 ni tanlaydi .
3. Nihoyat, 3 yoshli yagona qismning vazni 1 ga teng . Bu bizga yakuniy natijani beradi 20 + 3 + 1 = 24.
Biroq, bu optimal yechim emas. 20 + 2 + 10 = 32 Quyidagi rasmda ko'rsatilganidek, ko'proq og'irlik ( ) ko'taradigan yana bir yo'l bor .
4.3-rasm. Eng uzun yo'l
Shuning uchun, ochko'z algoritmlar har doim ham optimal/mumkin yechimni bermaydi.
Ochko'z algoritm
Boshlash uchun, yechimlar to'plami (javoblarni o'z ichiga olgan) bo'sh.
Har bir bosqichda, yechimga erishilgunga qadar, eritma to'plamiga element qo'shiladi.
Agar yechim to'plami amalga oshirilishi mumkin bo'lsa, joriy element saqlanadi.
Aks holda, element rad etiladi va boshqa hech qachon ko'rib chiqilmaydi.
Keling, muammoni hal qilish uchun ushbu algoritmdan foydalanamiz.
|
|
Bosh sahifa
Aloqalar
Bosh sahifa
Texnologiyalari va kommunikatsiyalarini rivojlantirish vazirligi muhammad al-xorazmiy nomidagi toshkent axborot texnologiyalari universiteti samarqand filiali
|
