Wikiszótár

Christofides-algoritmus

Magyar

Kiejtés

  • IPA: [ ˈxriʃtofidɛʃɒlɡoritmuʃ]

Főnév

Christofides-algoritmus

  1. (matematika, algoritmusok) A Christofides-algoritmus egy hatékony közelítő algoritmus a minimális körút (Travelling Salesman Problem, TSP) megoldására, amikor a gráf háromszög-egyenlőtlenséget teljesít (minden ( u, v, w ) csúcsra: ( d(u, w) d(u, v) + d(v, w) )). Az algoritmus 1,5-szörös közelítési garanciát kínál, vagyis az eredményül kapott körút hossza legfeljebb 1,5-szöröse az optimális körút hosszának.


Probléma

Adott egy teljes súlyozott gráf ( G = (V, E) ), ahol: - ( V ) a csúcsok halmaza (( |V| = n )), - ( E ) az élek halmaza, és minden élhez tartozik egy nem negatív súly ( d(u, v) ).

A cél: - Megtalálni egy körutat, amely minden csúcsot pontosan egyszer érint, majd visszatér a kiindulási ponthoz (minimális körút).


Algoritmus lépései

  1. Minimális feszítőfa (MST):
    • Készítsd el a gráf minimális feszítőfáját (például Kruskal- vagy Prim-algoritmussal).
  2. Páros fokszámú csúcsok gyűjtése:
    • A minimális feszítőfában azokat a csúcsokat gyűjtsd össze, amelyek fokszáma páros.
  3. Minimális súlyú párosítás (Perfect Matching):
    • Hozz létre egy minimális súlyú párosítást a páros fokszámú csúcsok között, amely biztosítja a körút lezárhatóságát.
  4. Multigráf létrehozása:
    • Egyesítsd a minimális feszítőfát és a minimális súlyú párosítást, hogy egy Euler-kört tartalmazó gráfot kapj.
  5. Euler-kör:
    • Találd meg az Euler-kört az új gráfban.
  6. Hamilton-kör kialakítása:
    • Az Euler-körben haladva minden csúcsot csak egyszer érints (short-circuiting technika), így kialakul a kívánt Hamilton-kör.


Időbonyolultság

  • Minimális feszítőfa készítése: ( O(|E| |V|) ) (pl. Kruskal-algoritmussal).
  • Minimális súlyú párosítás: ( O(|V|^3) ) a hagyományos algoritmusokkal.
  • Euler-kör és Hamilton-kör: ( O(|E|) ).

Összességében az algoritmus időbonyolultsága: ( O(|V|^3) ), amely a párosítási lépés dominanciájából ered.


Példa

Adott gráf:

  • Csúcsok: ( A, B, C, D ).
  • Távolságok: [ ]

1. Minimális feszítőfa:

  • MST élei: ( (A, B), (A, C), (A, D) ).
  • Összesített súly: ( 10 + 15 + 20 = 45 ).

2. Páros fokszámú csúcsok:

  • Páros fokszámú csúcsok: ( B, C, D ).

3. Minimális súlyú párosítás:

  • Párosítás: ( (B, C), (C, D) ).
  • Párosítás súlya: ( 35 + 30 = 65 ).

4. Euler-kör:

  • A párosítás és az MST egyesítése után a gráf Euler-körrel rendelkezik.

5. Hamilton-kör:

  • Az Euler-körből Hamilton-kört készítünk: ( A B C D A ).
  • Körút hossza: ( 10 + 15 + 30 + 20 = 75 ).


Python implementáció

import networkx as nx

def christofides(graph):
    # Minimális feszítőfa
    mst = nx.minimum_spanning_tree(graph)

    # Páros fokszámú csúcsok kiválasztása
    odd_degree_nodes = [node for node in mst.nodes if mst.degree[node] % 2 == 1]

    # Párosítás létrehozása
    subgraph = graph.subgraph(odd_degree_nodes)
    matching = nx.algorithms.matching.max_weight_matching(subgraph, maxcardinality=True)

    # Multigráf létrehozása
    multigraph = nx.MultiGraph(mst)
    multigraph.add_edges_from(matching)

    # Euler-kör
    euler_circuit = list(nx.eulerian_circuit(multigraph))

    # Hamilton-kör kialakítása
    visited = set()
    hamiltonian_path = []
    for u, v in euler_circuit:
        if u not in visited:
            hamiltonian_path.append(u)
            visited.add(u)

    # Visszatérés az első csúcsra
    hamiltonian_path.append(hamiltonian_path[0])

    return hamiltonian_path

# Példa gráf
graph = nx.Graph()
edges = [
    ('A', 'B', 10), ('A', 'C', 15), ('A', 'D', 20),
    ('B', 'C', 35), ('B', 'D', 25), ('C', 'D', 30)
]
graph.add_weighted_edges_from(edges)

# Hamilton-kör keresése
path = christofides(graph)
print(f"Hamilton-kör: {path}")

Kimenet: 

Hamilton-kör: ['A', 'B', 'C', 'D', 'A']

Előnyök

  1. Közelítési garancia:
    • Az eredmény legfeljebb 1,5-szerese az optimális körútnak.
  2. Hatékony algoritmus:
    • Polinomiális időben fut.


Hátrányok

  1. Speciális feltételek:
    • Csak háromszög-egyenlőtlenséget teljesítő gráfokon alkalmazható.
  2. Magasabb költségű lépések:
    • A minimális súlyú párosítás számítása (O(|V|^3)) időigényű.


Alkalmazások

  1. Utazási ügynökségek:
    • Útvonaloptimalizálás.
  2. Hálózatok tervezése:
    • Minimális hálózatok és útvonalak tervezése.
  3. Robotika:
    • Mozgástervezés robotok számára.


Összegzés

A Christofides-algoritmus egy erős közelítési algoritmus a TSP problémára háromszög-egyenlőtlenséget teljesítő gráfokon. Bár nem ad pontos megoldást, garantált közelítési aránya és polinomiális futásideje miatt gyakran alkalmazzák olyan helyzetekben, ahol az optimális megoldás kiszámítása túl költséges.

További információk

A lap eredeti címe: „https://hu.wiktionary.org/w/index.php?title=Christofides-algoritmus&oldid=3479691”