რა არის ხირითი ალგორითმები და როდის მუშაობს ისინი?

Question

IT Interview Practice · Accepted Answer

**ხირითი ალგორითმი** აკეთებს **ლოკალურად ოპტიმალურ არჩევანს** ყოველ ეტაპზე, იმედით რომ ეს მიდის გლობალური მაქსიმუმისკენ. ეს არის მარტივი და სწრაფი, მაგრამ სწორია მხოლოდ მაშინ, როდესაც პრობლემას აქვს **greedy-choice property** და **optimal substructure**.

## იდეა

ნიდაგ არ გაიაზრო წინა არჩევანი — ისე დაუჭირე საუკეთესო მყისიერ ვარიანტს და წინსულ.

## მაგალითი: მონეტების გაცვლა კანონიკური მონეტებით

```python
def greedy_coins(amount, coins=(25, 10, 5, 1)):
    result = []
    for coin in coins:                 # largest first
        while amount >= coin:
            amount -= coin             # take as many as possible
            result.append(coin)
    return result

greedy_coins(36)                       # -> [25, 10, 1]
```

ეს ოპტიმალური აშშ-ს მონეტებისთვის, მაგრამ **ვერ იმუშავებს** ისეთი ნაკრებებისთვის, როგორიცაა {1, 3, 4}, სადაც ხირითი იძლევა 4+1+1 6-ის ნაცვლად 3+3-ის.

## როდის მუშაობს ხირითი

- **Optimal substructure:** ოპტიმალური გადაწყვეტილება შეიცავს ოპტიმალურ ქვეწყვილებს.
- **Greedy-choice property:** ლოკალური მაქსიმუმი გლობალური მაქსიმუმის ნაწილია.

მაგალითები, რომლებიც მუშაობს: Dijkstra, Kruskal/Prim (MST), Huffman coding, interval scheduling.

## რთულობა

ჩვეულებრივ სწრაფი — ხშირად O(n log n) დახარისხების შემდეგ.

## ხაფანგები

ხირითი **ყოველთვის სწორი არ არის**. დაამტკიცე greedy-choice property ან გამოცადე brute-force/DP საფუძვლობის მიმართ სანამ ენდობა.

## რატომ მნიშვნელოვანია

როდესაც ხირითი ვრცელდება, ეს ბევრად უფრო მარტივი და სწრაფია ვიდრე DP ან brute force.

ცნობა *როდის* ის მოქმედი — და როდის ჩუმად აძლევს არასწორ პასუხებს — ალგორითმული სიმწიფის ნიშანია.

მრავალი ძირეული გრაფიკის ალგორითმი ხირითი არის გულის სიგრძეზე.

იდეა

მაგალითი: მონეტების გაცვლა კანონიკური მონეტებით

როდის მუშაობს ხირითი

რთულობა

ხაფანგები

რატომ მნიშვნელოვანია

დაკავშირებული კითხვები