Taqsimlangan tizimlarning m atematik algoritmini ishlab chiqish

1. 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.

Ochko'zlik yondashuvining afzalliklari

• 
  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

1. 
   Boshlash uchun, yechimlar to'plami (javoblarni o'z ichiga olgan) bo'sh.
   
2. 
   Har bir bosqichda, yechimga erishilgunga qadar, eritma to'plamiga element qo'shiladi.
   
3. 
   Agar yechim to'plami amalga oshirilishi mumkin bo'lsa, joriy element saqlanadi.
   
4. 
   Aks holda, element rad etiladi va boshqa hech qachon ko'rib chiqilmaydi.
   

Keling, muammoni hal qilish uchun ushbu algoritmdan foydalanamiz.