1

我正在尝试实现 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
4

1 回答 1

2

方法喜欢delete并delete_at修改他们的论点。由于在 ruby​​ 中所有内容都是按值传递的，这意味着您调用的第二次（以及第三次、第四次、第五次等）karger是在已处理的图形上执行此操作，因此该方法不执行任何操作。

看起来你修改了嵌套在里面的数组graph以及它graph本身，所以graph=graph.dup在你的方法开始时这样做karger是不够的。ruby 没有内置标准的深拷贝，但实现此目的的一种简单方法是转储和反序列化您的对象：

def karger(graph)
  graph = Marshal.load(Marshal.dump(graph))
  ...
end
于 2012-07-15T21:07:02.460 回答