Qanoat algoritmi nima va u muammo yechishda qanday…

Greedy algoritmi har heuristik bir yondashuv bo'lib, har bir bosqichda lokal ravishda eng yaxshi qarorni qabul qiladi va umid qiladiki, bu global ravishda eng yaxshi yechimga olib keladi.

Qo'llanilishi:

Faoliyatlarni tanlash muammosi:

Muammo: Berilgan to'plamdan vaqt bo'yicha mos kelmaydigan maksimal faoliyatlar sonini tanlang.
Greedy yechim: Faoliyatlarni tugash vaqtiga ko'ra o'sish tartibida saralash. Har bir bosqichda, allaqachon tanlanganlar bilan mos kelmaydigan, eng kichik tugash vaqtiga ega faoliyatni tanlang.

# Faoliyatlarni tanlash misoli
# activities = [(start_time, end_time)]

activities = [(1, 4), (3, 5), (0, 6), (5, 7), (3, 8), (5, 9), (6, 10), (8, 11), (8, 12), (2, 14), (12, 16)]
activities.sort(key=lambda x: x[1]) # Tugash vaqtiga ko'ra saralash

selected_activities = []
last_finish_time = -1

for activity in activities:
    if activity[0] >= last_finish_time:
        selected_activities.append(activity)
        last_finish_time = activity[1]

print(selected_activities) # [ (1, 4), (5, 7), (8, 11), (12, 16) ]

Kuzatuvchi muammo (Coin Change Problem) kanonik to'plamlar uchun:
- Muammo: Berilgan summani minimal miqdordagi tanga bilan to'lash.
- Greedy yechim: Eng katta nominatdagi tangalarni maksimal miqdorda ishlatib, summa to'liq to'lanmaguncha davom eting. Bu faqat ma'lum to'plamlar uchun ishlaydi (masalan, 1, 5, 10, 25).
```
# Misol uchun tangalarni almashtirish (kanonik tangalar uchun)
coins = [25, 10, 5, 1]
amount = 67
result = {}

for coin in coins:
    while amount >= coin:
        result[coin] = result.get(coin, 0) + 1
        amount -= coin

print(result) # {25: 2, 10: 1, 5: 1, 1: 2}
```
Kruskal algoritmi yordamida minimal kengayish daraxtini topish:
- Muammo: Ulanadigan barcha tugunlarni minimal umumiy og'irlik bilan bog'laydigan, og'irligi bo'yicha tartiblangan grafiga kiritilgan cheklovlar bilan bog'langan cheklovlar to'plamini topish.
- Greedy yechim: Barcha cheklovlarni og'irligiga ko'ra o'sish tartibida saralash. Ularni ketma-ket qo'shish, agar ular allaqachon tanlangan cheklovlar bilan sikl hosil qilmasa, n-1 chekloviga erishguncha davom eting (n - tugunlar soni).

Greedy algoritmlar oson amalga oshiriladi, ammo har doim ham global optimal yechimni topa olmaydi. Ba'zi muammolar uchun (masalan, tangalarni almashtirish, umumiy holatda sumkaga sig'dirish muammosi) greedy yondashuv optimal emas. Optimal yoki yaxshiroq yaqinlashishni ta'minlash uchun dinamik dasturlash yoki boshqa usullar talab qilinishi mumkin. Greedy algoritmni qo'llashdan oldin, uning muammo uchun mosligini tekshirish muhimdir.

Qanoat algoritmi nima va u muammo yechishda qanday qo'llaniladi?