Karger算法

我試圖在Java中實現min-cut Karger算法。爲此，我創建了一個Graph類，它存儲一個SortedMap，一個整數索引作爲鍵，一個Vertex對象作爲值，以及一個Edge對象的ArrayList。邊緣存儲其入射頂點的索引。比我合併一些隨機邊的頂點，直到頂點的數量達到2.我重複這個步驟安全的次數。奇怪的是，在我的輸出中，我得到了兩倍的交叉邊緣。我的意思是，如果正確答案是10，在執行n次算法（對於n足夠大）之後，這些執行結果的最小值是20，這使我相信實現幾乎是正確的。這是代碼的相關部分：Karger算法

void mergeVertex(int iV, int iW) { 

    for (int i = 0; i < edges.size(); i++) { 
     Edge e = edges.get(i); 
     if (e.contains(iW)) { 
      if (e.contains(iV)) { 
       edges.remove(i); 
       i--; 
      } else { 
       e.replace(iW, iV); 
      } 
     } 
    } 

    vertices.remove(iW); 
} 

public int kargerContraction(){ 

    Graph copy = new Graph(this); 
    Random r = new Random(); 
    while(copy.getVertices().size() > 2){ 
     int i = r.nextInt(copy.getEdges().size()); 
     Edge e = copy.getEdges().get(i); 
     copy.mergeVertex(e.getVertices()[0], e.getVertices()[1]); 
    } 

    return copy.getEdges().size()/2; 
}

來源

2015-08-08 Giovanni Oliveira

除了無法解釋的除以2之外，您的代碼看起來很好。請記住，Karger算法的成功概率**的可能性很低，所以您必須多次調用它才能確信找到最小數目的削減。 –

這是我試圖找出。無需這個部門，返回的價值是正確答案的2倍，奇怪的是，總是平均。我執行該方法大量的關於頂點數量，我很確定算法已經執行了足夠多的次數來找到minCut。 –

也許你正在使用的'Graph'對象是爲有向圖設置的？嘗試使用更簡單的測試數據運行代碼。比如一棵樹，它應該有一個minCut爲1. –

其實這個問題是要簡單得多比我想象。在讀取包含圖形數據的.txt文件時，我每邊計數兩次，因此邏輯上，minCut返回的結果是右minCut的2倍。

來源

2015-08-11 17:32:02

回答

相關問題