greedy algorithm

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.

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.

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.

• 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.

• 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

def fractional_knapsack(values, weights, capacity):
    ratio = 
    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 = 
weights = 
capacity = 50

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

✅ 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

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

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

• 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)