Τι είναι οι αλγόριθμοι greedy και πότε λειτουργούν;

Question

Accepted Answer

Ένας **αλγόριθμος greedy** κάνει την **τοπικά βέλτιστη επιλογή** σε κάθε βήμα, με την ελπίδα ότι οδηγεί σε ένα παγκόσμιο βέλτιστο. Είναι απλός και γρήγορος, αλλά σωστός μόνο όταν το πρόβλημα έχει την **ιδιότητα greedy-choice** και την **βέλτιστη υποδομή**.

## Η ιδέα

Μη ξανασκεφτείτε τις προηγούμενες επιλογές — δεσμευθείτε στην καλύτερη άμεση επιλογή και προχωρήστε.

## Παράδειγμα: ανταλλαγή κερμάτων με κανονικά κέρματα

```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} όπου η greedy δίνει 4+1+1 για 6 αντί για 3+3.

## Πότε λειτουργεί η greedy

- **Βέλτιστη υποδομή:** μια βέλτιστη λύση περιέχει βέλτιστες υπολύσεις.
- **Ιδιότητα greedy-choice:** ένα τοπικό βέλτιστο είναι μέρος ενός παγκόσμιου βέλτιστου.

Παραδείγματα που λειτουργούν: Dijkstra, Kruskal/Prim (MST), Huffman coding, interval scheduling.

## Πολυπλοκότητα

Συνήθως γρήγορη — συχνά O(n log n) μετά την ταξινόμηση.

## Παγίδες

Η greedy **δεν είναι πάντα σωστή**. Αποδείξτε την ιδιότητα greedy-choice ή δοκιμάστε την έναντι ενός brute-force/DP baseline πριν την εμπιστευθείτε.

## Γιατί έχει σημασία

Όταν εφαρμόζεται η greedy, είναι πολύ πιο απλή και ταχύτερη από DP ή brute force.

Το να γνωρίζετε *πότε* είναι έγκυρη — και πότε σιωπηλά δίνει λάθος απαντήσεις — είναι ένα σημάδι αλγοριθμικής ωριμότητας.

Πολλοί βασικοί αλγόριθμοι γραφημάτων είναι greedy στην καρδιά τους.