közelítő algoritmus

Magyar

Kiejtés

IPA: [ ˈkøzɛliːtøːɒlɡoritmuʃ]

Főnév

(informatika, matematika, algoritmusok) A közelítő algoritmusok olyan algoritmusok, amelyek nem feltétlenül találják meg egy probléma optimális megoldását, de képesek egy elfogadhatóan jó megoldást találni egy viszonylag rövid idő alatt. Ezeket az algoritmusokat gyakran használják olyan problémák esetén, amelyek megoldása NP-teljes vagy NP-nehéz, tehát ahol az optimális megoldás megtalálása túl sok időt venne igénybe.

Néhány példa a közelítő algoritmusokra:

Greedy algoritmusok: Ezek minden lépésben a pillanatnyilag legjobb helyi megoldást választják, anélkül, hogy előre gondolkodnának. Bár nem garantált, hogy a globálisan legjobb megoldást találják meg, sok esetben elfogadható eredményt adnak.
- Példa: Az éhes algoritmus jól alkalmazható az érmecímletek minimális számú kombinációjának megtalálására adott összeghez.
Lokális keresési algoritmusok: Ezek egy kezdeti megoldásból indulnak ki, és fokozatosan javítják azt a közvetlen szomszédos megoldások keresésével.
- Példa: Heurisztikus algoritmusok, mint a szimulált hűtés (simulated annealing) vagy a tabu keresés.
Heurisztikák: Olyan szabályok vagy módszerek, amelyek segítenek gyorsabban megtalálni egy jó (de nem feltétlenül optimális) megoldást. Ezeket gyakran kombinálják más algoritmusokkal.
- Példa: A genetikus algoritmusok heurisztikák alapján működnek, evolúciós folyamatokat utánozva.
Relaxációs módszerek: Ezek az eredeti problémát egyszerűsítik, hogy könnyebben megoldható legyen, majd a megoldást használják a közelítő megoldásként.
- Példa: Lineáris programozás relaxáció, ahol az egész értékű változókat folytonos változókkal helyettesítik.

Közelítő algoritmusokat akkor alkalmaznak, ha fontosabb a gyors eredmény, mint az optimális megoldás, vagy ha az optimális megoldás megtalálása túl drága lenne időben vagy erőforrásban.

néhány konkrét példa közelítő algoritmusokra és azok alkalmazásaira:

1. Utazó ügynök probléma (Traveling Salesman Problem - TSP):

Probléma: Egy ügynöknek meglátogatnia kell több várost úgy, hogy minden várost egyszer látogat meg, és visszatér az indulási pontra. A cél a megtett távolság minimalizálása.
Közelítő algoritmus: A legközelebbi szomszéd (Nearest Neighbor) algoritmus.
- Működése: Az ügynök mindig a hozzá legközelebbi, még nem látogatott várost választja következő úti célnak. Bár ez nem mindig ad optimális megoldást, de gyorsan végrehajtható, és elfogadható közelítést adhat.

2. Fedési probléma (Set Cover Problem):

Probléma: Adott egy univerzum, és az elemeinek egy része több halmazba tartozik. A feladat az, hogy minimális számú halmazt válasszunk úgy, hogy azok lefedjék az összes elemet.
Közelítő algoritmus: Greedy algoritmus.
- Működése: Az algoritmus mindig azt a halmazt választja, amelyik a legtöbb lefedetlen elemet tartalmazza. Ez ismétlődik addig, amíg minden elem le nem lesz fedve. Az algoritmus garantáltan nem lesz rosszabb, mint a minimális halmazok számának logaritmusa.

3. Knapsack probléma (Hátizsák probléma):

Probléma: Adott egy hátizsák, amelynek maximális kapacitása van, és adott néhány tárgy, amelyeknek súlya és értéke van. A feladat az, hogy a hátizsákba olyan tárgyakat pakoljunk, hogy azok maximális értéket képviseljenek, anélkül, hogy a súly meghaladná a kapacitást.
Közelítő algoritmus: Frakcionált Knapsack algoritmus (Greedy alapú).
- Működése: Az algoritmus minden tárgynál az érték/súly arány alapján sorba rendezi a tárgyakat, és amíg van hely a hátizsákban, bepakolja a legnagyobb arányú tárgyakat. Ha egy tárgy már nem fér bele teljesen, akkor annak csak egy részét veszi figyelembe.

4. Max Cut probléma:

Probléma: Egy gráf élei közül ki kell választani egy maximális mennyiséget úgy, hogy az élek egyik vége egy adott csoportba, a másik vége egy másik csoportba kerüljön.
Közelítő algoritmus: Véletlenszerű bipartíció.
- Működése: Az algoritmus véletlenszerűen két csoportra osztja a gráf csúcsait. Ez nem optimális megoldás, de gyorsan elvégezhető, és jó közelítést adhat.

5. Színezési probléma (Graph Coloring Problem):

Probléma: Egy gráf csúcsait úgy kell kiszínezni, hogy két szomszédos csúcs soha ne kapjon azonos színt, és a lehető legkevesebb színt kell használni.
Közelítő algoritmus: Greedy színezés.
- Működése: Az algoritmus minden csúcsot sorban haladva kiszínez azzal a legkisebb színnel, amely még nem foglalt a szomszédainál. Bár nem mindig optimális, de gyors és egyszerű módszer.

6. Szállítási probléma (Vehicle Routing Problem - VRP):

Probléma: Több járműnek kell egy készletből különböző helyekre eljuttatnia árut úgy, hogy a járművek megtett útja minimális legyen.
Közelítő algoritmus: Clarke-Wright Savings algoritmus.
- Működése: Először minden célállomást külön útvonalon látogat meg egy jármű. Ezután az algoritmus kiszámítja azokat a megtakarításokat, amelyeket az egyes utak kombinálásával lehet elérni, és a legnagyobb megtakarításokat veszi figyelembe.

Ezek a közelítő algoritmusok különböző területeken alkalmazhatók, például logisztikában, hálózatkezelésben, gyártásban és egyéb optimalizálási problémáknál.

Közelítő Algoritmusok

Definíció

A közelítő algoritmusok olyan algoritmusok, amelyek optimalizálási problémák megoldására szolgálnak. Ezek nem garantálnak optimális megoldást, de gyorsan futnak, és gyakran jó közelítést nyújtanak az optimális értékhez.

Előnyök

Gyorsabbak, mint az exakciós algoritmusok (pl. dinamikus programozás vagy brute force).
Alkalmasak nagy méretű problémákra.

Hátrányok

Nem garantálnak pontos megoldást.
A megoldás minősége függ az alkalmazott algoritmustól.

Példa Problémák

1. Utazó Ügynök Probléma (TSP)

Közelítő Algoritmus: Nearest Neighbor

A Nearest Neighbor (NN) algoritmus az egyik legegyszerűbb közelítő algoritmus a TSP-re: 1. Kezdj egy tetszőleges városból. 2. Mindig azt a legközelebbi, még nem látogatott várost válaszd ki. 3. Visszatérés az induló városba.

Python Implementáció

def nearest_neighbor_tsp(graph):
    """
    Nearest Neighbor algoritmus a TSP problémára.
    
    Args:
        graph: Távolságmátrix, ahol graph[i][j] az i és j város közötti távolság.
    
    Returns:
        (útvonal, távolság): Az algoritmus által talált útvonal és annak hossza.
    """
    n = len(graph)
    visited = [False] * n
    path = [0]  # Kezdő város (0)
    total_cost = 0

    current_city = 0
    visited[current_city] = True

    for _ in range(n - 1):
        next_city = None
        min_cost = float('inf')
        for city in range(n):
            if not visited[city] and graph[current_city][city] < min_cost:
                next_city = city
                min_cost = graph[current_city][city]
        path.append(next_city)
        total_cost += min_cost
        visited[next_city] = True
        current_city = next_city

    # Visszatérés az induló városba
    total_cost += graph[current_city][0]
    path.append(0)

    return path, total_cost

# Példa gráf (távolságmátrix)
graph = [
    [0, 10, 15, 20],
    [10, 0, 35, 25],
    [15, 35, 0, 30],
    [20, 25, 30, 0]
]

path, cost = nearest_neighbor_tsp(graph)
print("Közelítő útvonal:", path)
print("Útvonal hossza:", cost)

Kimenet

Közelítő útvonal: [0, 1, 3, 2, 0]
Útvonal hossza: 80

2. Hátizsák-probléma

Közelítő Algoritmus: Greedy Fractional Knapsack

Ez az algoritmus a tárgyak ( ) arányát veszi figyelembe, és mindig a legjobb arányú tárgyat választja.

Python Implementáció

def fractional_knapsack(values, weights, capacity):
    """
    Greedy algoritmus a frakcionált hátizsák-problémára.
    
    Args:
        values: Az egyes tárgyak értékei.
        weights: Az egyes tárgyak súlyai.
        capacity: A hátizsák maximális kapacitása.
    
    Returns:
        max_value: A hátizsákba pakolható maximális érték.
    """
    n = len(values)
    items = [(values[i] / weights[i], values[i], weights[i]) for i in range(n)]
    items.sort(reverse=True, key=lambda x: x[0])  # Érték/súly arány szerint rendezés

    max_value = 0
    for ratio, value, weight in items:
        if capacity >= weight:
            # Az egész tárgyat berakjuk
            max_value += value
            capacity -= weight
        else:
            # Csak egy részét rakjuk be
            max_value += ratio * capacity
            break

    return max_value

# Példa bemenet
values = [60, 100, 120]  # Tárgyak értékei
weights = [10, 20, 30]   # Tárgyak súlyai
capacity = 50            # Hátizsák kapacitása

max_value = fractional_knapsack(values, weights, capacity)
print("Maximális érték (közelítő):", max_value)

Kimenet

Maximális érték (közelítő): 240.0

3. Max-Cut Probléma

Közelítő Algoritmus: Randomizált Kétpartíció

A gráf éleit két csoportra osztjuk úgy, hogy a lehető legtöbb él “átíveljen” a két partíció között. Egy egyszerű randomizált közelítő algoritmus elegendő lehet.

Python Implementáció

import random

def random_max_cut(graph):
    """
    Randomizált közelítő algoritmus a Max-Cut problémára.
    
    Args:
        graph: Lista élek páronkénti tömegével [(u, v, w)].
    
    Returns:
        max_cut: A randomizált algoritmus által talált vágás értéke.
    """
    partition = {}
    for node in set(u for u, v, _ in graph).union(set(v for u, v, _ in graph)):
        partition[node] = random.choice([0, 1])  # Random partícióba helyezés

    max_cut = 0
    for u, v, weight in graph:
        if partition[u] != partition[v]:  # Az él átlépi a partíciókat
            max_cut += weight

    return max_cut

# Példa gráf
graph = [
    (0, 1, 3),  # Él a 0 és 1 között, súlya 3
    (0, 2, 2),
    (1, 2, 1),
    (1, 3, 4),
    (2, 3, 5)
]

max_cut = random_max_cut(graph)
print("Max-Cut értéke (közelítő):", max_cut)

Kimenet

A kimenet értéke függ a randomizációtól, például:

Max-Cut értéke (közelítő): 7

Összegzés

Problémák és Algoritmusok:

Utazó ügynök probléma:
- Közelítő: Nearest Neighbor ((O(n^2))).
Hátizsák-probléma:
- Közelítő: Greedy Fractional Knapsack ((O(n n))).
Max-Cut probléma:
- Közelítő: Randomizált kétpartíció ((O(E))).

Előnyök:

Gyors futási idő.
Egyszerű implementáció.
Nagyobb problémaméretek kezelése.

Hátrányok:

Nem garantált optimális megoldás.
Az eredmény minősége algoritmusfüggő.

Közelítő algoritmusok alkalmazása gyakori, amikor az optimális megoldások számítása túl költséges vagy időigényes lenne. Pythonban ezek az algoritmusok gyorsan implementálhatók és tesztelhetők.

További információk

közelítő algoritmus - Értelmező szótár (MEK)
közelítő algoritmus - Etimológiai szótár (UMIL)
közelítő algoritmus - Szótár.net (hu-hu)
közelítő algoritmus - DeepL (hu-de)
közelítő algoritmus - Яндекс (hu-ru)
közelítő algoritmus - Google (hu-en)
közelítő algoritmus - Helyesírási szótár (MTA)
közelítő algoritmus - Wikidata
közelítő algoritmus - Wikipédia (magyar)