You can not select more than 25 topics
Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
30 lines
1.1 KiB
30 lines
1.1 KiB
11 months ago
|
import numpy as np
|
||
|
|
import networkx as nx
|
||
|
|
|
||
|
|
inf = float('inf')
|
||
|
|
|
||
|
|
|
||
|
|
def find_hamiltonian_cycles(distances):
|
||
|
|
num_nodes = distances.shape[0]
|
||
|
|
graph = nx.DiGraph()
|
||
|
|
for i in range(num_nodes):
|
||
|
|
for j in range(num_nodes):
|
||
|
|
if distances[i][j] != inf:
|
||
|
|
graph.add_edge(i, j, weight=distances[i][j])
|
||
|
|
|
||
|
|
hamiltonian_cycles = list(nx.simple_cycles(graph))
|
||
|
|
hamiltonian_cycles = [cycle + [cycle[0]] for cycle in hamiltonian_cycles if len(cycle) == num_nodes - 1]
|
||
|
|
|
||
|
|
return hamiltonian_cycles
|
||
|
|
|
||
|
|
|
||
|
|
# distances = np.array([[inf, 69, 48, inf, 41, 78], [69, inf, 48, 53, 91, inf], [48, 48, inf, 19, 86, inf], [inf, 53, 19, inf, 96, 10], [41, 91, 86, 96, inf, inf], [78, inf, inf, 10, inf, inf]])
|
||
|
|
distances = np.array([[inf, 94, 67, 65, inf], [94, inf, inf, 41, inf], [67, inf, inf, inf, 65], [65, 41, inf, inf, 54], [inf, inf, 65, 54, inf]])
|
||
|
|
all_hamiltonian_cycles = find_hamiltonian_cycles(distances)
|
||
|
|
|
||
|
|
if all_hamiltonian_cycles:
|
||
|
|
print("存在的哈密尔顿回路路径为：")
|
||
|
|
for cycle in all_hamiltonian_cycles:
|
||
|
|
print(cycle)
|
||
|
|
else:
|
||
|
|
print("不存在哈密尔顿回路")
|