python 2.7中的karger最小割算法 [英] karger min cut algorithm in python 2.7

问题描述

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

Here is my code for the karger min cut algorithm.. To the best of my knowledge the algorithm i have implemented is right. But I don get the answer right. If someone can check what's going wrong I would be grateful.

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"，然后运行程序

Please copy it in a text file and save it as "data.txt" and run the program

答案应该是: 最小切割数为2， 切口在边缘[[1,7)，(4,5)]

The answer should be : the number of min cuts is 2 and the cuts are at edges [(1,7), (4,5)]

推荐答案

因此，Karger的算法是一种随机算法".也就是说，每次运行它都会产生一个解决方案，绝不能保证它是最好的.通用方法是多次运行并保留最佳解决方案.对于许多配置，将有许多最佳或近似最佳的解决方案，因此您可试探性地迅速找到一个好的解决方案.

So Karger's algorithm is a `random alogorithm'. That is, each time you run it it produces a solution which is in no way guaranteed to be best. The general approach is to run it lots of times and keep the best solution. For lots of configurations there will be many solutions which are best or approximately best, so you heuristically find a good solution quickly.

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

As far as I can see, you are only running the algorithms once. Thus the solution is unlikely to be the optimal one. Try running it 100 times in for loop and holding onto the best solution.

这篇关于python 2.7中的karger最小割算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！