我正在尝试实现 Kargers min-cut 算法。该算法是一种随机算法,您应该运行(n(logn))^2
多次以确信您已经找到了最小切割。我已经完成了在 Ruby 中就地实现该算法的新手工作:
def karger(graph)
#graph will be an array
#each element of graph is an array
#these subarrays are of the form [[4], 43, 23, 1, 67]
#where the zeroth element is the vertex label
#the other elements represent edges to other vertices.
while graph.length > 2
#u & v are the indices of two random vertices that will be merged together
u = rand(0...graph.length)
v = rand(0...graph.length)
#while loop ensures u != v
while v == u
u = rand(0...graph.length)
v = rand(0...graph.length)
end
#merge u & v into a single vertex,
graph[u] += graph[v][1...graph[v].length]
graph[u][0].concat(graph[v][0])
graph.delete_at(v)
end
#this nested block eliminates self loops on the two remaining superveticies
graph.each do |z|
z.each do |x|
unless x.class == Array
if z[0].include?(x)
z.delete(x)
end
end
end
end
return (graph[0].length)-1 #-1 since the first element of both subarrays is the vertex label
end
我的问题是,当我尝试创建一个块或循环以在必要的(nlog(n))^2
时间内运行算法时,每个切割都是相同的值。因此,如果第一次调用karger()
产生 2 的剪切,那么之后的每个调用也将返回 2。但是,如果我karger()
手动调用,只需在 textmate 中按 cntrl R,我的结果就会有所不同。我第一次在某个输入上运行它时,我得到了 5,下一次,2。因此,我试图生成大量karger()
调用样本并找到最小结果的尝试不起作用,因为我只会有一个大量的 2 或 5 或其他样本。如果我运行调用karger()
(nlog(n))^2
时间的块,我会得到不同的答案,这取决于第一次调用karger()
返回的内容,因为其他所有调用都返回相同的结果。
希望这很清楚。
这是一个示例图:
testgraph1 = [[[1],2,2,3], [[2],1,1,3,4,5], [[3],1,2,4], [[4],2,3], [[5],2]]
编辑:
我认为如果添加用于迭代调用函数的方法可能会有所帮助:
def kargeriterate(graph)
n = graph.flatten.length
min = graph.flatten.length
((n)*(Math.log(n)))**2.to_i.times do |z|
a = karger(graph)
puts a #this puts is here just to see each output
if a < min
min = a
end
end
return min
end