不可能完成的旅行

cities = {
    "A": (14, 36),
    "B": (21, 79),
    "C": (33, 21),
    "D": (55, 83),
    "E": (92, 82),
    "F": (37, 41),
    "G": (75, 61),
}

import math
import itertools
import networkx as nx


cities = {
    "A": (14, 36),
    "B": (21, 79),
    "C": (33, 21),
    "D": (55, 83),
    "E": (92, 82),
    "F": (37, 41),
    "G": (75, 61),
}


def distance(a, b):
    x1, y1 = cities[a]
    x2, y2 = cities[b]

    return math.hypot(x1 - x2, y1 - y2)


def route_length(route):
    return sum(
        distance(route[i], route[i + 1])
        for i in range(len(route) - 1)
    )


# 构造完整的无向度量图
G = nx.Graph()
G.add_nodes_from(cities)

for a, b in itertools.combinations(cities, 2):
    G.add_edge(a, b, weight=distance(a, b))


# 1. 求最小生成树
tree = nx.minimum_spanning_tree(
    G, weight="weight"
)

tree_cost = tree.size(weight="weight")


# 2. 找出生成树里的奇度顶点
odd_vertices = [
    v for v, degree in tree.degree()
    if degree % 2 == 1
]


# 3. 在奇度顶点之间求最小权完美匹配
odd_graph = G.subgraph(odd_vertices).copy()

matching = nx.min_weight_matching(
    odd_graph,
    weight="weight"
)

matching_cost = sum(
    G[u][v]["weight"]
    for u, v in matching
)


# 4. 组合为允许重复边的多重图
multi = nx.MultiGraph(tree)

for u, v in matching:
    multi.add_edge(
        u, v,
        weight=G[u][v]["weight"]
    )

assert nx.is_eulerian(multi)


# 5. 求欧拉回路
start = next(iter(cities))

euler_walk = [start]

for u, v in nx.eulerian_circuit(
    multi, source=start
):
    euler_walk.append(v)


# 6. 跳过重复城市
visited = set()
tour = []

for city in euler_walk:
    if city not in visited:
        visited.add(city)
        tour.append(city)

tour.append(tour[0])

approx_cost = route_length(tour)


# 验证质量保证
print("最小生成树:", round(tree_cost, 2))
print("匹配成本:", round(matching_cost, 2))

print("欧拉回路:")
print(" -> ".join(euler_walk))

print("Christofides路线:")
print(" -> ".join(tour))

print("路线长度:", round(approx_cost, 2))

assert approx_cost <= (
    tree_cost + matching_cost + 1e-9
)

tree = nx.minimum_spanning_tree(G)

matching = nx.min_weight_matching(odd_graph)

nx.eulerian_circuit(multi)

from itertools import permutations


def brute_force_tsp():
    start = "A"

    others = [
        city for city in cities
        if city != start
    ]

    best_route = None
    best_cost = float("inf")

    for order in permutations(others):
        candidate = [
            start,
            *order,
            start
        ]

        cost = route_length(candidate)

        if cost < best_cost:
            best_cost = cost
            best_route = candidate

    return best_route, best_cost


optimal_tour, optimal_cost = brute_force_tsp()

print("真实最优路线:")
print(" -> ".join(optimal_tour))

print("真实最优长度:", round(optimal_cost, 2))

print(
    "当前路线与最优路线之比:",
    round(approx_cost / optimal_cost, 4)
)

assert approx_cost <= 1.5 * optimal_cost + 1e-9

import networkx as nx

route = nx.approximation.christofides(
    G,
    weight="weight"
)

length = route_length(route)

print("路线:", " -> ".join(route))
print("长度:", round(length, 2))