python - 最小切割(Karger 算法)
问题描述
我正在尝试实施 Krager 的 Min。python中的cut算法解决以下问题。这个问题来自斯坦福的 edx 课程,“算法:设计与分析,第 1 部分”
该文件包含一个简单无向图的邻接表表示。有 200 个顶点标记为 1 到 200。文件中的第一列表示顶点标签,特定行(除第一列之外的其他条目)告诉所有与该顶点相邻的顶点。例如,第 6 行看起来像:“6 155 56 52 120 ......”。这只是意味着标签为 6 的顶点与标签为 155、56、52、120、......等的顶点相邻(即共享一条边)
运行最小割问题的随机收缩算法,并在上图中使用它来计算最小割。
它涉及以下邻接列表:https ://pastebin.pl/view/39b087f8
这是我在 python 中编写的代码——我知道实现很幼稚,但我只想在优化之前把它弄好。
import random
import copy
with open('Contraction hwk.txt') as f: #Please input the correct file path
proto = f.readlines()
proto2 = [(x.replace('\t',' ').strip('\n')).split() for x in proto]
adjl = [[int(x) for x in i] for i in proto2]
solnset = []
for x in range(1000):#Repeated a 100 times cause the algo is not always correct
wadjl = copy.deepcopy(adjl)
nodes = list(range(1,len(adjl)+1))
while len(nodes) > 2:
randnodeval = random.choice(nodes) #Select a random node
randnode = wadjl[randnodeval-1] #Assign the random node to a var --> randnode
randedgeval = random.choice(randnode[1:]) # Picks another random node(edge node) that is adjacent to the initial this will contract with the original random node
if randedgeval == randnodeval:
continue
for node in wadjl[randedgeval-1][1:]:#This loop will go to all nodes adjacent to the edge node and replace the value of the edge node with the random node
if node == randnodeval:#If the node is the same as the random node it removes the node as an adjacent node (Deletion of edge node from random node)
modnode = wadjl[node-1][1:]
edgevalnode = modnode.index(randedgeval)
wadjl[node-1].pop(edgevalnode+1)
continue
modnode = wadjl[node-1][1:]
edgevalnode = modnode.index(randedgeval)
wadjl[node-1][edgevalnode+1] = randnodeval
randnodeidx = wadjl[randedgeval-1][1:].index(randnodeval)#This yeilds the index of the random node in the adjaceny list of the edge node
wadjl[randedgeval-1].pop(randnodeidx+1)#The random node is removed from that list(Deletion of random node from edgenode)
randnode.extend(wadjl[randedgeval-1][1:])#The adjacency list of the edge node is merged with that of the random node
del wadjl[randedgeval-1][1:]#The edge node is deleted
try:#repeates/edges to itself are removed from the random node
repeats = [i for i,x in enumerate(randnode) if x == randnodeval]
for repeate in repeats:
randnode.pop(repeat)
except:
pass
#Edge node is removed from the nodes list
noderemove = nodes.index(randedgeval)
nodes.pop(noderemove)
for entry in wadjl:
if len(entry) > 1:
minc = len(entry) - 1 #edges in min cut case
solnset.append(minc) #append solution to solution set
break
# print(solnset)
print(min(solnset))
根据一些互联网搜索,答案似乎是 17。我得到的答案是 20,而且我不认为我的算法实现是正确的,因为解决方案集太多样化了。我相信如果实施得当,解决方案应该经常出现在这个集合中。
解决方案
您发布的代码不会随机均匀地选择一条边,除非收缩图恰好具有均匀度(几乎总是不是这种情况)。通过选择一个随机节点,然后选择该节点的一个随机邻居,它会超重具有少数邻居的节点,这导致最佳切割边缘比它们应该更频繁地收缩,从而产生更大的最终切割。
理论上,Karger 的算法也需要 Θ(n choose 2) 次迭代才能以恒定概率成功,这里 n 选择 2 是 200 (200 - 1) / 2 = 19,900,但这张图并不接近最坏的情况,如 100大多数时候,迭代似乎绰绰有余。
这是我的实现:
import fileinput
import random
def find(parents, i):
r = i
while r in parents:
r = parents[r]
while i in parents:
p = parents[i]
parents[i] = r
i = p
return i
def unite(parents, i, j):
parents[i] = j
def karger(n, edges):
edges = list(edges)
random.shuffle(edges)
parents = {}
for i, j in edges:
if n <= 2:
break
i = find(parents, i)
j = find(parents, j)
if i == j:
continue
unite(parents, i, j)
n -= 1
return sum(find(parents, i) != find(parents, j) for (i, j) in edges)
def main():
lines = list(fileinput.input())
n = len(lines)
edges = set()
for line in lines:
fields = iter(map(int, line.split()))
u = next(fields)
edges.update((min(u, v), max(u, v)) for v in fields)
print(min(karger(n, edges) for k in range(1000)))
if __name__ == "__main__":
main()
推荐阅读
- c# - 例如,C# 为什么我不能将字符串从 networkstream 解析为 int?TCP客户端.服务器
- javascript - 加载页面时自动打开输入文件对话框
- python - 如何使用 pyspark 读取包含多行的 .sql 文件?
- python - 带代理的 Selenium 返回空网站
- c# - 将所有活动从一条记录移动到另一条记录,SSIS 还是 C#?
- postgresql - 如何在 Go API 中同时运行函数而不是顺序运行?
- html - 如何分隔 HTML 列表中的项目,使其在水平导航中就像三个元素在一侧,两个在另一侧
- dpdk - 从源代码交叉编译 DPDK
- laravel - Laravel Cashier Single Charge 是否适合这个任务
- java - java.util.Properties.load() 问题 OWASP Top 10 2017