Ochko‘z algoritmlar

Ochko‘z algoritmlar muhokamasi strategiyalardir

Ochko‘z algoritmlar — yechimlarni bosqichma-bosqich quradigan strategiyalar bo‘lib, har bir bosqichda global optimal natijaga erishish umidi bilan mahalliy optimal variantni tanlaydi. Ular kuchli, sodda va ko‘pincha dinamik dasturlash yoki to‘liq qidiruvdan ancha tez, ammo faqat masala ma’lum strukturaviy xossalarga (masalan, optimal quyi tuzilma va ``greedy-choice property'') ega bo‘lgandagina ishlaydi.

Ko‘plab klassik masalalarda (interval rejalashtirish, kutish vaqtini minimallashtirish, faoliyat tanlash, Huffman kodlash) ochko‘z algoritmlar optimal javob berishi isbotlangan. Musobaqaviy dasturlashda asosiy qiyinchilik — ochko‘zlik qachon to‘g‘ri ekanini va to‘g‘ri ochko‘z mezon nima ekanini aniqlashdir.

To‘g‘ri ochko‘z yechimlar odatda quyidagi kabi isbotlarga tayanadi:

• Almashtirish argumenti: har qanday optimal yechimni ochko‘z qadamlarni kuzatadigan qilib qayta tartiblash mumkinligini ko‘rsatish.
• Oldinda borish argumenti: ochko‘z yechim har doim boshqa istalgan qisman yechimdan kamida shunchalik yaxshi ekanini ko‘rsatish.

Misol 1: Faoliyat tanlash masalasi

Masala: Sizga boshlanish vaqtlari $s_i$ va tugash vaqtlari $f_i$ bo‘lgan ta faoliyat berilgan. Ustma-ust tushmaydigan faoliyatlarning maksimal sonini tanlang.