python 2.7中的karger min cut算法

Question

这是我的karger min cut算法的代码.据我所知,我实现的算法是正确的.但我没有得到正确答案.如果有人可以检查出了什么问题,我将不胜感激.

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

此代码也有效.

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 2

所以Karger的算法是一个"随机算术".也就是说,每次运行它都会产生一个绝不保证最佳的解决方案.一般的方法是运行很多次并保持最佳解决方案.对于许多配置,将会有许多最佳或近似最佳的解决方案,因此您可以尝试快速找到一个好的解决方案.

据我所知,你只运行算法一次.因此,解决方案不太可能是最佳解决方案.尝试在for循环中运行100次并保持最佳解决方案.