greedy algorithm

Angol

Főnév

greedy algorithm (tsz. greedy algorithms)

1. (informatika) mohó algoritmus

---

A greedy algorithm (mohó algoritmus) egy egyszerű és hatékony megközelítés optimalizálási problémák megoldására, amely minden lépésben az aktuálisan legjobbnak tűnő döntést választja – abban a reményben, hogy ezzel a globálisan legjobb megoldást is megtalálja.

---

🧠 1. Alapelv

Egy mohó algoritmus lépésről lépésre építi a megoldást, mindig az aktuálisan legnagyobb (vagy legkisebb) nyereséggel járó döntést választva, visszalépés vagy újratervezés nélkül.

---

⚙️ 2. Működés lépései

1. Inicializálás: kezdő állapot létrehozása.
2. Lépésválasztás: válaszd az aktuálisan legjobb lehetőséget.
3. Érvényesség ellenőrzése: a döntés érvényes-e (pl. nem sért szabályt).
4. Megállási feltétel: ha nem lehet új lépést választani, az algoritmus véget ér.

---

✅ 3. Mohó algoritmus akkor működik jól, ha:

• A probléma optimális alegységekre bontható (→ greedy-choice property),
• Az optimális részmegoldások kombinálásával kapjuk a globális optimumot (→ optimal substructure).

Ha ezek nem teljesülnek, a mohó megoldás nem garantálja az optimálist.

---

📚 4. Klasszikus példák

Probléma	Leírás
Activity selection	Válassz maximum számú nem átfedő intervallumot
Hátizsák (fractional)	Válassz a legjobb érték/tömeg arány szerint
Prim algoritmus	Minimális feszítőfa építése gráfban
Kruskal algoritmus	Minimális feszítőfa élhozzáadásos módon
Dijkstra algoritmus	Legrövidebb út nem negatív súlyokkal
Huffman-kódolás	Minimális hosszú prefixkód-fát épít

---

🧮 5. Példa – Fractional Knapsack

• Minden tárgynak van értéke ${\textstyle v_{i}}$ és súlya ${\textstyle w_{i}}$
• Céltömeg: ${\textstyle W}$
• Mohó választás: válasszuk a legjobb ${\textstyle {\frac {v_{i}}{w_{i}}}}$ arányú tárgyakat

Python kód:

def fractional_knapsack(values, weights, capacity):
    ratio = [(v / w, v, w) for v, w in zip(values, weights)]
    ratio.sort(reverse=True)
    
    total_value = 0
    for r, v, w in ratio:
        if capacity >= w:
            capacity -= w
            total_value += v
        else:
            total_value += r * capacity
            break
    return total_value

values = [60, 100, 120]
weights = [10, 20, 30]
capacity = 50

print("Max value:", fractional_knapsack(values, weights, capacity))

---

📈 6. Előnyök és hátrányok

✅ Előnyök	❌ Hátrányok
Egyszerű implementáció	Nem mindig optimális
Gyors (általában ${\textstyle O(n\log n)}$)	Néha nagyon rossz megoldást ad
Kevés memóriaigény	Problémafüggő, működése nem univerzális

---

⚠️ 7. Mikor nem működik jól?

Példa: 0-1 hátizsákprobléma

• Nem lehet egy tárgyat „darabolni”
• Mohó választás nem garantál optimálist

---

🧾 8. Összefoglalás

Fogalom	Leírás
Greedy algoritmus	Mindig a helyileg legjobb lépést választja
Működése	Egyszerű, gyors, determinisztikus
Előnye	Hatékony, ha a probléma szerkezete engedi
Korlátozása	Nem mindig globálisan optimális
Példák	Prim, Kruskal, Dijkstra, Huffman, aktivitásválasztás

További információk

• greedy algorithm - Szótár.net (en-hu)
• greedy algorithm - Sztaki (en-hu)
• greedy algorithm - Merriam–Webster
• greedy algorithm - Cambridge
• greedy algorithm - WordNet
• greedy algorithm - Яндекс (en-ru)
• greedy algorithm - Google (en-hu)
• greedy algorithm - Wikidata
• greedy algorithm - Wikipédia (angol)