完成 Held-Karp 松弛

import networkx as nx
from itertools import combinations
import numpy as np
import math
import random


def is_1_arborescence(G):
    """
    Returns true if `G` is a 1-arborescence
    """
    return (
        G.number_of_edges() == G.order()
        and max(d for n, d in G.in_degree()) <= 1
        and nx.is_weakly_connected(G)
    )


# Generate a random adjacency matrix
size = (7, 7)
G_array = np.empty(size, dtype=int)
random.seed()
for r in range(size[0]):
    for c in range(size[1]):
        if r == c:
            G_array[r][c] = 0
            continue
        G_array[r][c] = random.randint(1, 100)

# Print that adjacency matrix
print(G_array)

G = nx.from_numpy_array(G_array, create_using=nx.DiGraph)
num_nodes = G.order()

combo_count = 0
min_weight_tour = None
min_tour_weight = math.inf
test_combo = nx.DiGraph()
for combo in combinations(G.edges(data="weight"), G.order()):
    combo_count += 1
    test_combo.clear()
    test_combo.add_weighted_edges_from(combo)
    # Test to see if test_combo is a tour.
    # This means first that it is an 1-arborescence
    if not is_1_arborescence(test_combo):
        continue
    # It also means that every vertex has a degree of 2
    arborescence_weight = test_combo.size("weight")
    if (
        len([n for n, deg in test_combo.degree if deg == 2]) == num_nodes
        and arborescence_weight < min_tour_weight
    ):
        # Tour found
        min_weight_tour = test_combo.copy()
        min_tour_weight = arborescence_weight

print(
    f"Minimum tour found with weight {min_tour_weight} from {combo_count} combinations of edges\n"
)
for u, v, d in min_weight_tour.edges(data="weight"):
    print(f"({u}, {v}, {d})")

~ time python3 brute_force_optimal_tour.py
[[ 0 45 39 92 29 31]
 [72  0  4 12 21 60]
 [81  6  0 98 70 53]
 [49 71 59  0 98 94]
 [74 95 24 43  0 47]
 [56 43  3 65 22  0]]
Minimum tour found with weight 144.0 from 593775 combinations of edges

(0, 5, 31)
(5, 4, 22)
(1, 3, 12)
(3, 0, 49)
(2, 1, 6)
(4, 2, 24)

real	0m9.596s
user	0m9.689s
sys     0m0.241s

~ time python3 brute_force_optimal_tour.py
[[ 0 26 63 59 69 31 41]
 [62  0 91 53 75 87 47]
 [47 82  0 90 15  9 18]
 [68 19  5  0 58 34 93]
 [11 58 53 55  0 61 79]
 [88 75 13 76 98  0 40]
 [41 61 55 88 46 45  0]]
Minimum tour found with weight 190.0 from 26978328 combinations of edges

(0, 1, 26)
(1, 3, 53)
(3, 2, 5)
(2, 5, 9)
(5, 6, 40)
(4, 0, 11)
(6, 4, 46)

real	7m28.979s
user	7m29.048s
sys     0m0.245s