1

Kargersの最小カットアルゴリズムを実装しようとしています。アルゴリズムはランダム化されたアルゴリズムで(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を押すだけで手動で呼び出すと、結果に変化が生じます。初めて特定の入力で実行すると、次回は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すべてがルビーの値で渡されるため、これは、2回目（および3回目、4回目、5回目など）kargerに、すでに処理されたグラフで呼び出していることを意味します。したがって、メソッドは何も実行しません。

graph内部にネストされた配列とgraphそれ自体を変更しているように見えるため、メソッドgraph=graph.dupの先頭で変更するkargerだけでは不十分です。rubyに組み込まれている標準のディープコピーはありませんが、これを実現する簡単な方法は、オブジェクトをダンプして逆シリアル化することです。

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