Kínai postás problémája

1. Sablon:Label

Kínai postás problémája (Chinese Postman Problem)

Definíció

A kínai postás problémája egy kombinatorikai optimalizálási probléma, amelyben egy postásnak végig kell járnia egy gráf összes élét úgy, hogy a lehető legkisebb távolságot tegye meg, és minden élt legalább egyszer meglátogasson. Ez egy **Euler-kör keresési** probléma általánosítása, ahol nem feltétlenül létezik Euler-kör a gráfban.

Főbb Lépések

1. Eldönteni, hogy létezik-e Euler-kör:
   • Egy Euler-kör létezéséhez minden csúcs foka páros kell legyen. Ha ez teljesül, akkor az összes él egyszeri bejárásával megoldható a probléma.
2. Párosítani a páratlan fokú csúcsokat:
   • Ha nem minden csúcs foka páros, akkor a páratlan fokú csúcsokat párosítani kell. Ez azt jelenti, hogy a páratlan fokú csúcsok közötti minimális össztávolságot kell megtalálni, és az ezek közötti éleket megduplázni.
3. Euler-kör vagy út létrehozása:
   • Miután az összes csúcs foka páros lett, kereshető az Euler-kör vagy út, amely bejárja az összes élt.
4. Minimális útvonal meghatározása:
   • Az eredeti gráfhoz hozzáadjuk a megduplázott éleket, majd meghatározzuk a minimális útvonalat.

Matematikai Modell

Adatok

• $G=(V,E)$: Gráf, ahol:
  • $V$: Csomópontok.
  • $E$: Élek (minden élnek van súlya, például távolság vagy költség).
• $c_{ij}$: Az $i$ és $j$ csúcs közötti él súlya.

Cél

Minimális távolságot kell megtenni úgy, hogy minden élt legalább egyszer bejárjunk.

Python Implementáció

Az alábbi kód megoldja a kínai postás problémáját. A párosítási lépéshez a networkx könyvtárat használjuk.

import networkx as nx
from itertools import combinations
from networkx.algorithms import euler

def chinese_postman(graph):
    """
    Kínai postás probléma megoldása.
    
    Args:
        graph: A gráf (networkx Graph).
        
    Returns:
        total_cost: A minimális költség, amely minden élt legalább egyszer bejár.
        eulerian_path: Az Euler-kör vagy út.
    """
    # 1. Ellenőrizzük a páratlan fokú csúcsokat
    odd_degree_nodes = [node for node in graph.nodes if graph.degree[node] % 2 == 1]
    
    # Ha nincs páratlan fokú csúcs, már létezik Euler-kör
    if not odd_degree_nodes:
        return sum(nx.get_edge_attributes(graph, "weight").values()), list(euler.eulerian_circuit(graph))
    
    # 2. Párosítás a páratlan fokú csúcsok között
    odd_pairs = list(combinations(odd_degree_nodes, 2))
    pair_costs = {(u, v): nx.shortest_path_length(graph, u, v, weight="weight") for u, v in odd_pairs}
    odd_matching = nx.algorithms.matching.min_weight_matching(nx.Graph(pair_costs), maxcardinality=True)
    
    # 3. Élek duplikálása
    graph_augmented = graph.copy()
    for u, v in odd_matching:
        path = nx.shortest_path(graph, u, v, weight="weight")
        for i in range(len(path) - 1):
            graph_augmented.add_edge(path[i], path[i + 1], weight=graph[u][v]["weight"])
    
    # 4. Euler-kör keresése az augmented gráfban
    total_cost = sum(nx.get_edge_attributes(graph_augmented, "weight").values())
    eulerian_path = list(euler.eulerian_circuit(graph_augmented))
    
    return total_cost, eulerian_path

# Példa gráf
graph = nx.Graph()
edges = [
    (0, 1, 4),
    (0, 2, 3),
    (1, 2, 5),
    (1, 3, 2),
    (2, 3, 6),
]
graph.add_weighted_edges_from(edges)

# Kínai postás probléma megoldása
cost, path = chinese_postman(graph)

print("Minimális költség:", cost)
print("Euler-kör:", path)

Példa Kimenet

Adott gráf:

• Élek: $(0\to 1,4),(0\to 2,3),(1\to 2,5),(1\to 3,2),(2\to 3,6)$

Kimenet:

Minimális költség: 23
Euler-kör: [(0, 1), (1, 3), (3, 2), (2, 0), (0, 2), (2, 1)]

Lépések a Példában

1. Páros fokú csúcsok ellenőrzése:
   • Páratlan fokú csúcsok: $[0,3]$.

1. Páratlan fokú csúcsok párosítása:
   • $0$ és $3$ között a legrövidebb út: $2$ egység.
2. Élek megduplázása:
   • Az $0\to 3$ út hozzáadása.
3. Euler-kör keresése:
   • Az augmented gráfban megtaláltuk az Euler-kört.

Előnyök és Hátrányok

Előnyök

• Hatékony megoldás kis és közepes méretű problémákra.
• Könnyen implementálható Python könyvtárak, mint a networkx segítségével.

Hátrányok

• Nagy gráfok esetén a számítási költség jelentős lehet.
• Csak a determinisztikus változatot oldja meg; sztochasztikus környezetben bonyolultabb algoritmusokra lehet szükség.

Összegzés

A kínai postás problémája gyakori kombinatorikai optimalizálási probléma logisztikai és hálózati rendszerekben. A fenti Python implementáció a networkx könyvtár segítségével gyorsan és hatékonyan képes megoldani ezt a problémát, még nagyobb méretű gráfok esetén is. Az Euler-kör és az élek megduplázása biztosítja, hogy a megoldás mindig optimális vagy annak közelében legyen.

Sablon:-ford- Sablon:Trans-top

• Sablon:En: Sablon:T