Ochko‘z algoritmlar: qanday ishlaydi va qachon xato beradi

Ochko‘z algoritm nima

Ochko‘z algoritm (greedy algorithm) masalani qadamma-qadam yechadi. Har qadamda hozir eng yaxshi ko‘ringan variantni tanlaydi va bu qarorni hech qachon qayta ko‘rib chiqmaydi.

Optimal javob faqat ikki shart bajarilganda chiqadi:

• Ochko‘z tanlov xossasi — lokal eng yaxshi qadamdan boshlanadigan optimal yechim mavjud, shuning uchun bu qadam eng yaxshi natijaga yo‘lni yopmaydi.
• Optimal quyi tuzilma — tanlovdan keyin xuddi shu turdagi kichikroq masala qoladi va uning optimal yechimi umumiy optimal javobni to‘ldiradi.

Ikkala shart bo‘lsa, ochko‘z algoritm sodda va tez — odatda hammasi saralashga bog‘liq, O(n log n). Bo‘lmasa, algoritm baribir qandaydir javob qaytaradi, faqat eng yaxshisini emas, va bu haqda hech narsa ogohlantirmaydi.

Tangalar bilan qaytim: har qanday to‘plamga mos emas

Masala: summani eng kam tanga bilan yig‘ish. Ochko‘z qoida: har doim sig‘adigan eng katta tangani olish.

def greedy_coins(amount, coins):
    result = []
    for c in sorted(coins, reverse=True):
        while amount >= c:
            amount -= c
            result.append(c)
    return result

1, 5, 10, 25 tangalari va 30 summasi bilan 25 + 5 chiqadi — optimal. Ochko‘z algoritm doim optimal beradigan to‘plamlar kanonik deyiladi va ko‘plab real valyutalar aynan shunday tuzilgan.

Endi 1, 3, 4 tangalari va 6 summasi:

• Ochko‘z: 4 + 1 + 1 — uchta tanga.
• Optimal: 3 + 3 — ikkita tanga.

Birinchi «eng yaxshi» tanlov (4) qolganini buzdi. Ixtiyoriy tangalar to‘plami uchun dinamik dasturlash kerak: 0 dan maqsadli summagacha har bir summa uchun minimal tangalar sonini hisoblash.

def min_coins(amount, coins):
    INF = float("inf")
    dp = [0] + [INF] * amount
    for a in range(1, amount + 1):
        for c in coins:
            if c <= a and dp[a - c] + 1 < dp[a]:
                dp[a] = dp[a - c] + 1
    return dp[amount] if dp[amount] != INF else -1

Uchrashuvlar jadvali: tugash vaqti bo‘yicha saralash

Masala: bitta majlislar xonasi uchun bir-biri bilan kesishmaydigan eng ko‘p uchrashuvni tanlash.

To‘g‘ri ochko‘z qoida — eng erta tugaydigan uchrashuvni olish, so‘ng u tugagandan keyin boshlanadigan uchrashuvlar uchun takrorlash.

def max_meetings(intervals):
    count, last_end = 0, float("-inf")
    for start, end in sorted(intervals, key=lambda x: x[1]):
        if start >= last_end:
            count += 1
            last_end = end
    return count

Nega ishlaydi: erta tugash qolganlar uchun eng ko‘p joy qoldiradi. Aynan qoida muhim — «avval eng qisqalari» yoki «avval eng erta boshlanganlari» mantiqiy ko‘rinadi, lekin oddiy misollarda buziladi. Agar uchrashuvlarning vazni bo‘lsa (ba’zilari qimmatliroq), ochko‘zlik endi ishlamaydi, saralangan intervallar bo‘yicha DP kerak.

Huffman kodlash: ikkita eng kam uchraydiganini birlashtirish

Huffman kodi siqish uchun optimal prefiks kod quradi: tez-tez uchraydigan belgilar qisqa kod, kam uchraydiganlari uzun kod oladi.

1. Har bir belgini chastotasi bilan ustuvorlik navbatiga qo‘ying.
2. Ikkita eng kam uchraydigan tugunni olib, chastotalari yig‘indisiga teng yangi tugunga birlashtiring.
3. Uni navbatga qaytaring va bitta daraxt qolguncha takrorlang.
4. Kodlarni ildizdan o‘qing: chap qirra — 0, o‘ng qirra — 1.

Ochko‘z tanlov — ikkita eng kam uchraydigan belgini birlashtirish — isbotlangan holda xavfsiz: qandaydir optimal daraxtda ular eng chuqur darajada qo‘shni bo‘ladi. Huffman kodi ZIP va PNG da ishlatiladigan DEFLATE formatining bir qismi.

Ochko‘zlik qachon xato qiladi va DP kerak bo‘ladi

0/1 ryukzak — klassik tuzoq. Sig‘im 50, buyumlar (vazn, qiymat): (10, 60), (20, 100), (30, 120). Kilogramm boshiga qiymat bo‘yicha ochko‘z tanlov birinchi ikkitasini olib, 160 ga ega bo‘ladi. Eng yaxshi javob — ikkinchi va uchinchisi, 220. Buyumning bir qismini olish mumkin bo‘lgan kasrli ryukzakda xuddi shu ochko‘z qoida optimal.

Ochko‘z g‘oyani qanday tekshirish kerak

• Kichik qarshi misol qidiring. Juda kichik kirishlarni qo‘lda tekshiring yoki tezkor testda to‘liq saralash bilan solishtiring.
• Almashtirish argumentini sinab ko‘ring. Istalgan optimal yechimni oling va uning birinchi qadamini yomonlashtirmasdan ochko‘z qadam bilan almashtirish mumkinligini ko‘rsating.
• Vaznlar va «hammasi yoki hech narsa» buyumlariga e’tibor bering. Ular ochko‘z qoidalarni ko‘pincha buzadi.
• Ikkilansangiz, avval DP yozing, keyin u ochko‘z qoidaga soddalashadimi, ko‘ring.