尝试解决具有 133 个节点和 737 条边的有向图的最长路径问题。 https://en.wikipedia.org/wiki/Longest_path_problem
我尝试使用 python 的 networkx 库，但它无法计算。是否值得寻找像在 c 中使用 dfs 这样更快的实现？这似乎是 NP 难，这让我泄气。我不确定这是否需要几分钟、几小时、几天，或者直到宇宙热寂。
尝试使用 NetworkX 查找周期，但无法在一小时内计算。
图形大小对于寻找最大循环来说是具有挑战性的。
第一个观察结果是，一些顶点只有传入边，或只有传出边，因此它们永远不可能成为循环的一部分。因此，我决定在算法的第一阶段从图中消除这些：这可以产生级联效应，以便其他节点也以这种方式被隔离。
事实证明，在第一阶段可以删除 9 个顶点和 79 条边。
然后我多次尝试寻找（长）周期
这看起来很暗淡：运行了一个小时左右并没有产生结论性的结果。
在尝试了更多启发式方法之后，DFS 方法最终为我提供了一个针对“所有”节点（在第一阶段中未删除的节点）的循环，即清理后的图上的汉密尔顿循环。通过反复试验使其发挥作用的启发式方法感觉不对，所以后来我想到在 DFS 方法中应用“随机性”，并在某个时间片到期时自动中止并重试。有点基于蒙特卡罗采样。 这给出了令人满意的结果：虽然所需的时间可能在一秒到几分钟之间变化，但如果在该图中花费超过 5 分钟才能找到汉密尔顿循环，那真是太倒霉了。 这是我最终得到的代码。当然，当不存在哈密顿循环时，它找不到最大循环。
实施
这是Python代码：
import random
import time
class Edge:
def __init__(self, *nodes):
self.nodes = tuple(nodes)
self.active = False # Means it is not really connecting the vertices yet
self.chosen = False # Means it has not yet been selected as part of a cycle attempt
self.activate()
def activate(self): # Make edge really part of the graph
if self.active:
raise ValueError("attempting to activate an edge that is already active")
self.active = True
self.nodes[0].neighbors[1].append(self)
self.nodes[1].neighbors[0].append(self)
def deactivate(self): # Temporarily remove the edge from the graph
if not self.active:
raise ValueError("attempting to deactivate an edge that is not active")
if self.chosen:
return []
self.active = False
self.nodes[0].neighbors[1].remove(self)
self.nodes[1].neighbors[0].remove(self)
removed_edges = [self]
removed_edges.extend(self.nodes[0].isolate_when_leaf())
removed_edges.extend(self.nodes[1].isolate_when_leaf())
return removed_edges # This is like an undo log so this action can be undone later
def choose(self): # Choose this edge as part of our cycle attempt
if self.chosen:
raise ValueError("attempting to choose an edge that is already chosen")
self.chosen = True
self.deactivated_edges = []
# Other, alternative edges can no longer be part of the cycle attempt:
# temporarily remove them from the graph
for side, node in enumerate(self.nodes):
for edge in list(node.neighbors[1-side]):
if edge != self and edge.active:
deactivated = edge.deactivate()
if not deactivated:
return False
self.deactivated_edges.extend(deactivated)
return True
def unchoose(self): # Undo the earlier choose action
if not self.chosen:
raise ValueError("attempting to unchoose an edge that is not chosen")
self.chosen = False
for edge in self.deactivated_edges:
edge.activate()
self.deactivated_edges = []
def get_cycle(self): # If this edge is on a cycle, return it
edge = self
cycle = [self.nodes[0].label]
while True:
edges = edge.nodes[1].neighbors[1]
if not edges:
return cycle[:1] # No cycle, but can never become one
edge = edges[0]
if not edge.chosen:
return [] # It's not a cycle
if edge == self:
return cycle # It's a cycle
cycle.append(edge.nodes[0].label)
def __repr__(self):
return repr(self.nodes)
class Node:
def __init__(self, label):
self.label = label
self.neighbors = ([], [])
def __repr__(self):
return f"{self.label}({len(self.neighbors[0])},{len(self.neighbors[1])})"
def isolate_when_leaf(self): # Remove edges around this vertex when it only has outgoing or only incoming
if (not self.neighbors[0]) == (not self.neighbors[1]):
return [] # Not a leaf, or already detached
removed_edges = []
for edges in list(self.neighbors):
if edges and edges[0].chosen:
return [] # Don't isolate this node. We need to rollback
for edge in list(edges):
if edge.active:
removed_edges.extend(edge.deactivate())
return removed_edges
class Graph:
def __init__(self, edges):
self.nodes = [
Node(label)
for label in {label for edge in edges for label in edge}
]
label_to_node = {node.label: node for node in self.nodes}
self.edges = [
Edge(label_to_node[a], label_to_node[b])
for a, b in edges
]
def remove_leaves(self):
removed_edges = []
for node in self.nodes:
removed_edges.extend(node.isolate_when_leaf())
node_count = len(self.nodes)
self.nodes = [node for node in self.nodes if node.neighbors[0]]
print(f"Removed {node_count - len(self.nodes)} nodes and {len(removed_edges)} edges")
def hamiltoncycle(self):
print(f"Start search on a graph with {len(self.nodes)} nodes")
longest_cycle = []
deadline = time.time()
def recur(num_edges):
nonlocal longest_cycle
# Get list of nodes that still have an incoming and outgoing edge and are not
# joining two already selected edges.
nodes = [
node
for node in self.nodes
if node.neighbors[0] and node.neighbors[1] and not (
node.neighbors[0][0].chosen and node.neighbors[1][0].chosen)
]
# Select one of those nodes that has least of freedom (either incoming, or outgoing)
*_, node, side = min((
(len(node.neighbors[side]), len(node.neighbors[1-side]), i, node, side)
for i, node in enumerate(nodes) for side, edges in enumerate(node.neighbors)
if not edges[0].chosen
))
# We have to select one of the edges from the selected node and side (either outgoing/incoming):
# Try them in a random order until time slice expires (kinda Monte Carlo).
edges = list(node.neighbors[side])
random.shuffle(edges)
for edge in edges:
if edge.choose():
cycle = edge.get_cycle()
if cycle:
if len(cycle) > len(longest_cycle): # improvement
print(f"Found a cycle with {len(cycle)} vertices...")
longest_cycle = cycle
if len(cycle) == len(self.nodes):
return True # Hamilton cycle found!
else: # Not a cycle yet: add more edges through recursion
if recur(num_edges + 1):
return True
edge.unchoose()
if time.time() > deadline:
break
while len(longest_cycle) < len(self.nodes):
print("Start from scratch")
deadline += 10 # Allow 10 seconds for a depth-first search
longest_cycle = [] # Yes, we really throw away the best result so far ;-)
recur(0)
return longest_cycle
edges = [ ... your input comes here ... ]
# Create the data structure
graph = Graph(edges)
# Remove vertices that only have incoming edges or only outgoing edges:
# these can never be part of a cycle. Apply this with cascading effect:
graph.remove_leaves()
# Apply main algorithm:
cycle = graph.hamiltoncycle()
# Report the solution:
print(f"Found this cycle of size {len(cycle)}:")
print(cycle)
# Verify the solution:
for edge in zip(cycle, cycle[1:] + [cycle[0]]):
if edge not in edges:
print(f"Cycle has an edge that doesn't exist in the graph: {edge}")
exit(1)
if len(set(cycle)) < len(cycle):
print("Cycle has duplicates")
exit(1)
print("Cycle was verified and found OK")
由于该算法的随机性，每次运行的输出都不同。这是一个输出：
Removed 9 nodes and 79 edges
Start search on a graph with 124 nodes
Start from scratch
Found a cycle with 3 vertices...
Found a cycle with 7 vertices...
Found a cycle with 18 vertices...
Found a cycle with 59 vertices...
Found a cycle with 86 vertices...
Start from scratch
Found a cycle with 2 vertices...
Found a cycle with 3 vertices...
Found a cycle with 4 vertices...
Found a cycle with 7 vertices...
Found a cycle with 11 vertices...
Found a cycle with 22 vertices...
Found a cycle with 55 vertices...
Found a cycle with 56 vertices...
Found a cycle with 124 vertices...
Found this cycle of size 124:
[290, 295, 324, 276, 256, 2026, 2653, 6, 2572, 2655, 2306, 2628, 197, 66, 277, 201, 2305, 150, 258, 59, 153, 221, 183, 97, 2116, 2132, 2567, 202, 2459, 2711, 2117, 2006, 2084, 2649, 195, 2050, 2309, 189, 193, 77, 158, 2294, 2509, 135, 164, 84, 127, 356, 2751, 328, 41, 278, 23, 36, 62, 2440, 166, 167, 2638, 68, 2005, 21, 2439, 249, 2226, 242, 309, 2199, 9, 264, 204, 2483, 265, 275, 120, 2429, 2247, 349, 2426, 151, 252, 239, 2641, 248, 235, 2032, 2433, 326, 2229, 2348, 2393, 2390, 259, 103, 152, 52, 57, 2579, 2633, 142, 238, 96, 344, 12, 26, 254, 30, 38, 25, 24, 87, 228, 154, 2335, 8, 145, 2, 245, 99, 333, 251, 2636, 98, 5]
Cycle was verified and found OK
这里的结果是从头开始执行 DFS 搜索
两次迭代后找到的。需要多少会有所不同。