Wikiszótár

mohó algoritmus

Magyar

Kiejtés

  • IPA: [ ˈmoɦoːɒlɡoritmuʃ]

Főnév

mohó algoritmus

  1. (informatika, matematika, számításelmélet, algoritmusok)

Mohó algoritmus

A mohó algoritmus egy optimalizálási megközelítés, amely mindig azt a lépést választja, amely az adott pillanatban a legjobb helyi megoldást nyújtja, abban a reményben, hogy ez a választás a teljes problémára is optimális megoldást eredményez.


Jellemzők

  1. Helyi optimalizáció:
    • A döntéseket lépésről lépésre, helyi információ alapján hozza meg.
  2. Globális optimalizációra való törekvés:
    • A mohó választások sorozatából állítja össze a végső megoldást.
  3. Egyszerűség:
    • Az algoritmus könnyen implementálható és gyors.

Előnyök:

  • Gyors végrehajtás: gyakran (O(n n)) vagy (O(n)) bonyolultság.
  • Könnyű implementáció.

Hátrányok:

  • Nem minden probléma esetén működik optimálisan.
  • Bizonyos problémák esetén a helyi optimum nem vezet a globális optimumhoz.


Általános működés

  1. Kezdj egy üres megoldással.
  2. Iteratívan válaszd ki a legjobb lehetséges elemet, amely kielégíti a feltételeket.
  3. Ismételd a folyamatot, amíg nem található további lépés.


Példák

1. Hátizsák probléma (töredékes verzió)

Probléma:

Adott (n) tárgy, mindegyiknek van egy súlya és értéke. A cél, hogy maximalizáljuk az értéket egy (W) kapacitású hátizsákban. Az egyes tárgyak töredékekben is elhelyezhetők.

Mohó stratégia:
  • Mindig azt a tárgyat válaszd ki, amelynek a legnagyobb az (érték / súly) aránya.

Pszeudokód:
function FractionalKnapsack(weights, values, capacity):
    Rendezés csökkenő (value / weight) arány szerint.
    total_value = 0
    minden tárgy w, v:
        ha w <= capacity:
            total_value += v
            capacity -= w
        különben:
            total_value += v * (capacity / w)
            térj vissza total_value

Python implementáció:
def fractional_knapsack(weights, values, capacity):
    items = sorted(zip(weights, values), key=lambda x: x[1]/x[0], reverse=True)
    total_value = 0

    for weight, value in items:
        if capacity >= weight:
            total_value += value
            capacity -= weight
        else:
            total_value += value * (capacity / weight)
            break

    return total_value

# Példa használat
weights = [10, 20, 30]
values = [60, 100, 120]
capacity = 50
print(f"Maximális érték: {fractional_knapsack(weights, values, capacity)}")

Kimenet: 

Maximális érték: 240.0

2. Érmecsere probléma

Probléma:

Adj vissza egy adott összegű pénzt a lehető legkevesebb érme használatával, adott érmecímletekkel.

Mohó stratégia:
  • Mindig a legnagyobb címletű érmét válaszd ki, amely kisebb vagy egyenlő az adott összeggel.

Pszeudokód:
function CoinChange(coins, amount):
    coins.sort(descending)
    result = 0
    minden érme c in coins:
        ha amount == 0:
            térj vissza result
        result += amount // c
        amount %= c
    ha amount > 0:
        térj vissza "Nincs megoldás"

Python implementáció:
def coin_change(coins, amount):
    coins = sorted(coins, reverse=True)
    result = 0

    for coin in coins:
        if amount == 0:
            break
        result += amount // coin
        amount %= coin

    if amount > 0:
        return -1  # Nincs pontos megoldás
    return result

# Példa használat
coins = [1, 5, 10, 25]
amount = 63
print(f"Minimális érmék száma: {coin_change(coins, amount)}")

Kimenet: 

Minimális érmék száma: 6

3. Intervallum ütemezés

Probléma:

Adott (n) intervallum (kezdési és befejezési időpontokkal). A cél a maximális számú, egymást nem átfedő intervallum kiválasztása.

Mohó stratégia:
  • Mindig azt az intervallumot válaszd ki, amely a legkorábban ér véget, de nem ütközik az eddig kiválasztott intervallumokkal.

Pszeudokód:
function IntervalScheduling(intervals):
    Rendezés növekvő befejezési idő szerint.
    selected = []
    last_end = -∞
    minden intervallum i in intervals:
        ha i kezdési idő > last_end:
            add i-t a selected listához
            last_end = i befejezési idő
    térj vissza selected

Python implementáció:
def interval_scheduling(intervals):
    intervals = sorted(intervals, key=lambda x: x[1])  # Befejezési idő szerint rendezve
    selected = []
    last_end = float('-inf')

    for start, end in intervals:
        if start >= last_end:
            selected.append((start, end))
            last_end = end

    return selected

# Példa használat
intervals = [(1, 3), (2, 5), (4, 7), (6, 9), (8, 10)]
print(f"Kiválasztott intervallumok: {interval_scheduling(intervals)}")

Kimenet: 

Kiválasztott intervallumok: [(1, 3), (4, 7), (8, 10)]

Összegzés

A mohó algoritmusok hatékony megoldást nyújtanak sok optimalizálási problémára, ha: - A probléma rendelkezik az optimális almotívum tulajdonságával (az optimális megoldás részmegoldásokból épül fel). - A probléma mohó tulajdonsága biztosítja, hogy a helyi döntések összeállnak egy globálisan optimális megoldássá.

Előnyök: - Gyors, egyszerű algoritmusok. - Jó közelítő megoldásokat adhat még akkor is, ha a globális optimumot nem garantálja.

Hátrányok: - Nem minden probléma oldható meg optimálisan mohó módszerekkel. - Bizonyos esetekben a helyi optimum nem vezet globális optimumhoz.

Fordítások

További információk

A lap eredeti címe: „https://hu.wiktionary.org/w/index.php?title=mohó_algoritmus&oldid=3480196”