python 2.7中的karger-min-cut算法

Question

这是我的卡格最小割算法的代码。。据我所知，我实现的算法是正确的。但我没有找到正确的答案。如果有人能检查出什么问题，我将不胜感激。

import random
from random import randint

#loading data from the text file#
with open('data.txt') as req_file:
    mincut_data = []
    for line in req_file:
        line = line.split()
        if line:
            line = [int(i) for i in line]
            mincut_data.append(line)

#extracting edges from the data #            
edgelist = []
nodelist = []
for every_list in mincut_data:
    nodelist.append(every_list[0])
    temp_list = []
    for temp in range(1,len(every_list)):
        temp_list = [every_list[0], every_list[temp]]
        flag = 0
        for ad in edgelist:
            if set(ad) == set(temp_list):
                flag = 1
        if flag == 0 :
            edgelist.append([every_list[0],every_list[temp]])


#karger min cut algorithm#
while(len(nodelist) > 2):
    val = randint(0,(len(edgelist)-1))
    print val
    target_edge = edgelist[val]
    replace_with = target_edge[0]
    should_replace = target_edge[1]
    for edge in edgelist:
        if(edge[0] == should_replace):
            edge[0] = replace_with
        if(edge[1] == should_replace):
            edge[1] = replace_with
    edgelist.remove(target_edge)
    nodelist.remove(should_replace)
    for edge in edgelist:
        if edge[0] == edge[1]:
            edgelist.remove(edge)

print ('edgelist remaining: ',edgelist)
print ('nodelist remaining: ',nodelist)

测试用例数据是：

1 2 3 4 7
2 1 3 4
3 1 2 4
4 1 2 3 5
5 4 6 7 8
6 5 7 8
7 1 5 6 8
8 5 6 7

请将其复制到文本文件中并保存为“data.txt”，然后运行程序

答案应该是： 最小切割次数为2次 切口位于边缘[（1,7），（4,5）]

Answer 1

正如菲尔所说，我必须运行我的程序100次。代码中还有一个修正是：

for edge in edgelist:
        if edge[0] == edge[1]:
            edgelist.remove(edge)

这部分代码没有正确地消除自循环。所以我不得不修改代码如下：

for i in range((len(edgelist)-1),-1,-1):
        if edgelist[i][0] == edgelist[i][1]:
            edgelist.remove(edgelist[i])

不需要这条线。因为目标节点将自动更改为自循环并将其移除。

edgelist.remove(target_edge)

然后如前所述，程序被循环100次，我通过随机化得到了最小的削减。：）

Answer 2

此代码也可以工作。

import random, copy
data = open("***.txt","r")
G = {}
for line in data:
    lst = [int(s) for s in line.split()]
    G[lst[0]] = lst[1:]   

def choose_random_key(G):
    v1 = random.choice(list(G.keys()))
    v2 = random.choice(list(G[v1]))
    return v1, v2

def karger(G):
    length = []
    while len(G) > 2:
        v1, v2 = choose_random_key(G)
        G[v1].extend(G[v2])
        for x in G[v2]:
            G[x].remove(v2)
            G[x].append(v1) 
        while v1 in G[v1]:
            G[v1].remove(v1)
        del G[v2]
    for key in G.keys():
        length.append(len(G[key]))
    return length[0]

def operation(n):
    i = 0
    count = 10000   
    while i < n:
        data = copy.deepcopy(G)
        min_cut = karger(data)
        if min_cut < count:
            count = min_cut
        i = i + 1
    return count


print(operation(100))

Answer 3

所以卡格的算法是一个“随机算法”。也就是说，每次运行时，它都会产生一个解决方案，但决不能保证它是最好的。一般的方法是多次运行它并保持最佳的解决方案。对于许多配置，会有许多最佳或近似最佳的解决方案，因此您可以快速地试探性地找到一个好的解决方案。

据我所见，你只运行了一次算法。因此，这个解不太可能是最优解。尝试在for循环中运行100次，并保持最佳解决方案。