59 / 69

Greedy Algorithm

Greedy algoritm nima?

Greedy algoritm (ochko'z algoritm) — bu masalani yechishda har bir qadamda ayni paytdagi eng yaxshi (lokal optimal) variantni tanlashga asoslangan yondashuvdir. U hozirgi tanlangan eng yaxshi natija yakunda global optimal yechimga olib keladimi yoki yo'qligi haqida qayg'urmaydi.

Algoritm hatto qilingan tanlov noto'g'ri bo'lib chiqqan taqdirda ham oldingi qarorlarni hech qachon qayta ko'rib chiqmaydi yoki bekor qilmaydi. U yuqoridan-pastga (top-down) yondashuv asosida ishlaydi.

Bu algoritm barcha masalalar uchun ham eng yaxshi natijani bermasligi mumkin. Chunki u global eng yaxshi natijaga erishish umidida faqat lokal eng yaxshi tanlovga intiladi.

Biroq, agar masala quyidagi xususiyatlarga ega bo'lsa, uni greedy yondashuv orqali muvaffaqiyatli yechish mumkinligini aniqlashimiz mumkin:

1. Greedy Choice Property (Ochko'z tanlov xususiyati)

Agar masalaning optimal yechimiga har bir qadamda eng yaxshi tanlovni amalga oshirish orqali va avvalgi tanlangan qadamlarni qayta ko'rib chiqmasdan erishish mumkin bo'lsa, bu masala greedy yondashuv yordamida yechilishi mumkin. Ushbu xususiyat greedy choice property deyiladi.

2. Optimal Substructure (Optimal qism-tuzilma)

Agar masalaning umumiy optimal yechimi uning qism-masalalari (subproblems) optimal yechimlaridan tashkil topsa, bu masala greedy yondashuv bilan yechilishi mumkin. Bu xususiyat optimal substructure deyiladi.

Greedy yondashuvning afzalliklari

  • Algoritmni tushunish va bayon qilish osonroq.
  • Ushbu algoritm boshqa algoritmlarga nisbatan samaraliroq (tezroq) ishlashi mumkin (ammo barcha holatlarda emas).

Greedy yondashuvning kamchiligi

Yuqorida ta'kidlanganidek, greedy algoritm har doim ham optimal yechim bermaydi. Bu ushbu algoritmning eng asosiy kamchiligidir.

Masalan, quyidagi daraxtda ildizdan (root) barggacha (leaf) bo'lgan eng uzun yo'lni (maksimal yig'indiga ega yo'l) topmoqchimiz deylik. Keling, bu yerda greedy algoritmini qo'llab ko'ramiz.

Greedy yondashuv orqali eng uzun yo'lni qidirish

Greedy yondashuv orqali eng uzun yo'lni qidirish

Greedy yondashuv tahlili:

  1. Ildiz tuguni bo'lgan 20 dan boshlaymiz. O'ng tugun og'irligi 3, chap tugun og'irligi esa 2.
  2. Masalamiz eng katta yig'indili yo'lni topishdan iborat. Ayni paytdagi eng yaxshi tanlov 3 hisoblanadi. Shuning uchun greedy algoritm 3 ni tanlaydi.
  3. So'ngra 3 tugunining yagona bolasi bo'lgan 1 ga o'tadi. Natijada biz olgan yakuniy qiymat: 20 + 3 + 1 = 24.

Biroq, bu optimal yechim emas! Quyidagi rasmda ko'rsatilganidek, ancha katta vaznga ega bo'lgan boshqa yo'l mavjud (20 + 2 + 10 = 32).

Eng uzun optimal yo'l

Eng uzun optimal yo'l

Shuning uchun, greedy algoritmlar har doim ham optimal yoki maqbul yechim beravermaydi.

Greedy algoritmning umumiy ishlash tartibi

  1. Dastlab, yechimlar to'plami (javoblar ro'yxati) bo'sh bo'ladi.
  2. Har bir qadamda, yechimga erishilgunga qadar yechimlar to'plamiga yangi element qo'shiladi.
  3. Agar hosil bo'lgan yechimlar to'plami maqbul (feasible) bo'lsa, joriy element to'plamda saqlanadi.
  4. Aks holda, ushbu element rad etiladi va boshqa hech qachon ko'rib chiqilmaydi.

Keling, ushbu algoritm yordamida amaliy masalani yechib ko'ramiz.

Misol: Greedy yondashuv

text
Masala: Berilgan summani imkon qadar eng kam miqdordagi tangalar yordamida hosil qiling.
Summa: 18 so'm

Mavjud tangalar:
  5 so'mlik tanga
  2 so'mlik tanga
  1 so'mlik tanga
Har bir tangadan istalgancha miqdorda foydalanish mumkin.

Yechim:

  1. Bo'sh yechim_to'plami = { } yaratamiz. Mavjud tangalar: {5, 2, 1}.
  2. Maqsadimiz summa = 18 ni hosil qilish. Dastlab summa = 0 dan boshlaymiz.
  3. Har doim eng katta qiymatga ega tangani (ya'ni 5) summa > 18 bo'lmaguncha tanlayveramiz. (Har bir qadamda eng katta qiymatni tanlash orqali manzilga tezroq yetib borishga umid qilamiz. Bu tushuncha greedy choice property deyiladi.)
  4. 1-qadamda: yechim_to'plami = {5} va summa = 5.
  5. 2-qadamda: yechim_to'plami = {5, 5} va summa = 10.
  6. 3-qadamda: yechim_to'plami = {5, 5, 5} va summa = 15.
  7. 4-qadamda: yechim_to'plami = {5, 5, 5, 2} va summa = 17. (Bu yerda yana 5 ni tanlay olmaymiz, chunki 15 + 5 = 20 > 18 bo'lib ketadi. Shuning uchun keyingi eng katta tanga bo'lgan 2 ni tanlaymiz.)
  8. 5-qadamda: 1 ni tanlaymiz. Endi summa = 18 va yechim_to'plami = {5, 5, 5, 2, 1}.

Jami 5 ta tanga ishlatildi va bu ayni holat uchun eng optimal yechimdir.

Dasturiy kod

package main

import "fmt"

// coinChangeGreedy berilgan summani eng kam tangalar bilan maydalaydi
func coinChangeGreedy(coins []int, amount int) []int {
	var result []int
	for _, coin := range coins {
		for amount >= coin {
			amount -= coin
			result = append(result, coin)
		}
	}
	return result
}

func main() {
	coins := []int{5, 2, 1}
	amount := 18

	result := coinChangeGreedy(coins, amount)
	fmt.Printf("Maydalash natijasi (%d so'm): %v\n", amount, result)
	fmt.Printf("Ishlatilgan tangalar soni: %d\n", len(result))
}

Greedy algoritmlarning mashhur turlari

Quyidagi mashhur algoritmlar aynan greedy (ochko'z) yondashuv tamoyillariga asoslangan: