Tarkibga o'tish

Greedy algoritm

Bir kundalik hayotiy vaziyat: kassada turganingizda pulni qaytarish kerak. Kassiyor sizga 87 so'm qaytarishi kerak. Minimal miqdordagi tangalar bilan bu qanday amalga oshiriladi? Ko'pchilik instinktiv ravishda eng katta tangadan boshlaydi: avval 50 so'm, keyin 25 so'm, keyin 10 so'm, keyin 2 so'm. Besh tanga — optimal natija.

Bu greedy (ochko'z) yondashuv: har qadamda eng yaxshi ko'rinadigan variantni tanlash, orqaga qaytmaslik, keyingi qadam nimani keltirishini o'ylamaslik.

Ba'zan bu yondashuv global optimalga olib keladi. Ba'zan esa noto'g'ri natija beradi. Greedy yondashuvning kuchi va cheklovi aynan shu farqni tushunishda.

Asosiy g'oya

Greedy algoritm har bosqichda lokal optimallikka erishadi — hozirgi qadam uchun eng yaxshi tanlov qilinadi va bu qaror qaytarib olinmaydi. Kafolat: barcha lokal optimalliklar birga global optimallikka olib keladi.

Bu kafolat har masalada ishlaydi degan gapmas. Kafolat faqat masalada ikki xossa mavjud bo'lganda ishlaydi:

1. Greedy choice property (ochko'z tanlash xossasi): Lokal optimal tanlov global optimalga olib boradi. Ya'ni, har qadamda eng yaxshisini tanlash keyinchalik birorta tanlovni yomonlashtirmaydi.

2. Optimal substructure (optimal pastki tuzilma): Masalaning optimal yechimi kichikroq pastki masalalarning optimal yechimlari asosida quriladi.

Agar masalada bu ikki xossa bo'lsa — greedy to'g'ri natija beradi. Aks holda — boshqa yondashuv kerak.

Greedy fikrlash jarayoni

Greedy yechimni topishda ketma-ket savollarga javob beriladi:

  1. Har qadamda nima tanlanadi?
  2. Bu tanlov keyingi qarorlarni cheklaydi — qanday?
  3. Bu tanlov boshqa tanlash bilan almashtirilsa natija yaxshilanadimi?
  4. Agar almashtirilsa natija yomонlashmaydi, degan isbotni keltirib bo'ladimi?

So'nggi savolga "ha" deyish mumkin bo'lsa — greedy to'g'ri.

Klassik misollar

Faoliyatni tanlash (Activity selection)

Har biri boshlanish va tugash vaqtiga ega n ta faoliyat bor. Bir xil vaqtda faqat bitta faoliyatda qatnashish mumkin. Maksimal faoliyatlarni tanlash kerak.

Greedy tanlov: eng erta tugaydigan faoliyatni birinchi tanla.

Nima uchun ishlaydi? Eng erta tugaydigan faoliyat tanlanganda keyingi faoliyatlar uchun eng ko'p vaqt qoladi. Boshqa istalgan faoliyatni tanlasangiz — keyingi faoliyatlar uchun kamroq vaqt qoladi va natija yaxshilanmaydi (exchange argument).

Faoliyatlar (boshlanish, tugash):
  A: [1, 4]
  B: [3, 5]
  C: [0, 6]
  D: [5, 7]
  E: [3, 9]
  F: [6, 10]

Tugash vaqti bo'yicha tartiblanib:
  A[1,4], B[3,5], C[0,6], D[5,7], E[3,9], F[6,10]

Greedy:
  1. A tanlanadi (tugash: 4). Keyingi: 4 dan keyin boshlanadigan.
  2. B[3,5] — boshlanishi 3 < 4, o'tkazib yuboriladi.
  3. D[5,7] — boshlanishi 5 ≥ 4, tanlanadi. Keyingi: 7 dan keyin.
  4. F[6,10] — boshlanishi 6 < 7, o'tkazib yuboriladi.

Natija: {A, D} — 2 ta faoliyat

To'liq tekshiruv: {A, D}, {A, F}, {B, D}, {B, F} — barchasi 2 ta. Optimal.

FUNCTION ACTIVITY_SELECTION(activities)
    activities ni tugash vaqti bo'yicha tartiblash

    last_end = -INFINITY
    count    = 0

    FOR har bir activity activities ichida
        IF activity.start >= last_end
            last_end = activity.end
            count    = count + 1

    RETURN count

Murakkablik: O(n log n) — tartiblash dominant.

Kesimlarga bo'lish (Interval partitioning)

n ta kesim berilgan. Ularni "resurs" (xona, mashina) bo'yicha guruhlash kerak, shunda bir vaqtda bir resursda faqat bitta kesim bo'lsin. Minimal resurs sonini toping.

Greedy: boshlanish vaqti bo'yicha tartibling. Har yangi kesimni eng erta bo'shagan resursga joylashtiring. Mos resurs yo'q bo'lsa — yangi resurs oching.

Bu oddiy ko'rinishda "moslash" — hech qachon orqaga qaytmasdan. Kerakli resurslar soni bir vaqtda kesishgan kesimlarning maksimal soni bilan teng — bu faktni greedy o'z-o'zidan amalga oshiradi.

Fraksional knapsack

n ta predmet bor, har birining og'irligi va qiymati berilgan. Sig'im W bo'lgan xalta bor. Predmetlarni qisman ham olish mumkin. Maksimal qiymat topilsin.

Greedy: qiymat/og'irlik nisbatiga ko'ra tartibling. Avval eng "samarali" predmetni to'liq ol. Xalta to'lib qolsa — oxirgi predmetning kerakli qismini ol.

Predmetlar (og'irlik, qiymat):
  A: (10, 60)  → nisbat: 6
  B: (20, 100) → nisbat: 5
  C: (30, 120) → nisbat: 4

W = 50

Tartib: A (6), B (5), C (4)

A: og'irligi 10, to'liq olish. Jami: 60, qolgan sig'im: 40
B: og'irligi 20, to'liq olish. Jami: 160, qolgan sig'im: 20
C: og'irligi 30, lekin 20 sig'im qoldi → 20/30 qismi olish. Qo'shiladi: 120 × (20/30) = 80

Natija: 60 + 100 + 80 = 240

Nima uchun ishlaydi? Har birlik sig'im uchun eng ko'p qiymat beradigan predmet tanlanganda global qiymat maksimal bo'ladi. Fraksional olish mumkin bo'lgani uchun bu to'g'ri — butun knapsackda esa greedy ishlamaydi.

Huffman kodlash

Matnda harflarning chastotasi bor. Tez-tez uchragan harflarga qisqaroq, kam uchragan harflarga uzunroq ikkilik kod berish orqali siqish. Huffman greedy bilan optimalini qurishni kafolatlaydi: har safar eng kam chastotali ikki tugunni birlashtirish.

Greedy nima uchun ba'zan ishlamaydi

Greedy ko'r-ko'rona "eng yaxshi ko'ringan"ni tanlaydi. Lekin hozirgi qadam keyingi qadamlarni cheklashi mumkin va "eng yaxshi" ko'ringan tanlov global optimalni yo'qotishi mumkin.

Butun knapsack: predmetlar faqat butun holda olinadi. Qiymat/og'irlik nisbati bo'yicha greedy noto'g'ri:

Sig'im: 4
Predmetlar: A (og'irlik: 3, qiymat: 9), B (og'irlik: 2, qiymat: 5), C (og'irlik: 2, qiymat: 5)

Greedy (nisbat bo'yicha): A (3.0), B (2.5), C (2.5)
  A ni oladi → sig'im 1 qoladi, B ni ola olmaydi.
  Natija: 9

Optimal: B va C → qiymat: 10

Tangalar (ba'zi hollarda): agar tangalar 1, 3, 4 va maqsad 6 bo'lsa: - Greedy: 4 + 1 + 1 = 3 tanga - Optimal: 3 + 3 = 2 tanga

Qisqa yo'l: baʼzan qisqa bosqichlar uzunroq umumiy yo'lga olib keladi. Dijkstra manfiy edge bo'lmaganda ishlaydi, lekin umumiy grafda greedy yo'l topish xato berishi mumkin.

Greedyni isbotlash: almashtirish argumenti

Greedy algoritmning to'g'riligini odatda exchange argument (almashtirish argumenti) bilan isботlaydi:

  1. Optimal yechim bor deb faraz qilinadi.
  2. Agar optimal yechim greedy tanlagan variantdan farq qilsa, uni almashtirib ko'riladi.
  3. Almashtirish natijani yomonlashtirmasligini ko'rsatiladi.
  4. Demak, greedy tanlovi optimal yechimdan kam bo'lmagan natija beradi.

Misol: faoliyat tanlashda "agar boshqa faoliyat birinchi tanlansa" deb ko'riladi. Eng erta tugaydigani bilan almashtirilganda kamroq faoliyat qo'lga kiritilmaydi — shuning uchun greedy optimal.

Greedy vs dinamik dasturlash

Ikkalasi ham optimal substructure xossasiga tayanadi. Farq overlapping subproblems (takrorlanuvchi pastki masalalar) xossasida:

Xususiyat Greedy Dinamik dasturlash
Qaror qabul qilish Hozirgi qadamda eng yaxshi Barcha variantlarni ko'rib
Qarorni bekor qilish Mumkin emas Tegishli emas (pastki masalalar saqlanadi)
Xotira O(1) odatda O(n) yoki O(n²)
Tezlik Tez Sekinroq
To'g'rilik Kafolatlanmagan Kafolatlangan (formulani to'g'ri tuzsa)

Greedy to'g'ri bo'lganda DP dan tezroq. Greedy to'g'ri emasligiga shubha qilsangiz — DP muqobil.

Keng tarqalgan greedy masalalar

  • Jump game: massivdagi eng katta sakrash uchun greedy — hozirgi qadamdan eng uzoqqa yetish.
  • Interval birlashma: kesimlarni tartiblash va kesishganlari birlashtirish.
  • Gas station: dumaloq marshrut bo'ylab benzin-sarflanishi farqlarida boshlash nuqtasini topish.
  • Meeting rooms: uchrashuvlarni eng erta boshlash bo'yicha tartiblash, minimal xona soni.
  • Assign cookies: bolalar va pechenye — qoniqtirish uchun greedy taqsimot.

Keng tarqalgan xatolar

"Greedy har doim ishlaydi" deb taxmin qilish. Masala ko'rinishi greedy'ga o'xshasa ham, avval counterexample qidirib ko'rish kerak — kichik sonlarni qo'lda sinab ko'rish.

Tartiblash mezoni noto'g'ri tanlash. Tartiblash kriteriyi greedy choice property ga mos bo'lishi shart. Faoliyat tanlashda boshlanish vaqti yoki uzunlik emas — tugash vaqti.

Fraksional va butun knapsackni aralashtirish. Fraksional knapsack greedy bilan optimal, butun knapsack DP talab qiladi.

Greedy choice isbotlanmagan holda qo'llanishi. Greedy ishlatishdan oldin "lokal optimallik global optimallikka olib keladimi?" savolini aniqlamaslik — yashirin xato.

Qachon greedy ishlatish kerak?

  • Tartiblash, interval, resurs taqsimoti masalalarida
  • Masalada "minimal tanlov, maksimal qamrov" tuzilmasi bo'lganda
  • Exchange argument bilan isbotlash mumkin bo'lganda
  • DP kerak bo'lganda, lekin greedy bilan ham to'g'ri ekanligini ko'rsatish mumkin bo'lganda

Qachon greedy ishlatmaslik kerak?

  • Counterexample topsangiz
  • Pastki masalalar natijasi biriga bogʻliq bo'lsa — DP kerak
  • "Barcha kombinatsiyalarni ko'rib chiqish" tuzilmasi bo'lsa — backtracking kerak
  • Manfiy qiymatlar yoki murakkab cheklovlar bo'lsa

Xulosa

Greedy — har qadamda lokal optimallikni tanlash orqali global optimallikka erishishga urinish. Faoliyat tanlash, fraksional knapsack, Huffman kodlash kabi masalalarda provably optimal.

Greedyning kuchi: soddaligi va tezligi. Cheklovi: har masalada to'g'ri emas — exchange argument yoki counterexample bilan tekshirilmasa, noto'g'ri natija berishi mumkin.

Greedy choice property va optimal substructure — greedy to'g'ri ishlashining kafolati. Agar masalada bu ikki xossa bo'lsa, greedy DP dan ko'proq ma'qul: oddiy, tez, kam xotira.