在二進制矩陣找到一個「廣義對角線」

A「廣義對角線」在一個NxN矩陣是選擇N個單元，以使得：在二進制矩陣找到一個「廣義對角線」

恰好一個單元從每一行和從每一列中選擇
每個選定單元格中包含一個非零值

我在尋找一種算法來找到一個廣義的對角線爲O（n^3）。在我看來，以下動態編程算法「足夠好」，但我不知道如何分析其複雜性。

Set<Set<Integer>> failedCache = new HashSet<Set<Integer>>(); 

List<Integer> find(int[][] matrix, Set<Integer> used, int row) { 
    int N = matrix.length; 
    if (failedCache.contains(used)) 
     return null; 

    if (row == N) return new ArrayList<Integer>(); 

    for (int col = 0; col < N; ++col) { 
     if (matrix[row][col] == 0) 
      continue; 

     if (used.contains(col)) 
      continue; 

     Set<Integer> newUsed = new HashSet<Integer>(used); 
     newUsed.add(col); 
     List<Integer> answer = find(matrix, newUsed, row + 1); 
     if (answer != null) { 
      answer.add(col); 
      return answer; 
     } 
    } 

    failedCache.add(used); 
    return null; 
}

來源

2011-02-05 ripper234

您是否在尋找分析上述算法的幫助，或者在解決O（n^3）中的問題？我認爲我有一個O（n^3）算法，它使用完全不同的技術解決了這個問題，但是如果這裏沒有主題，我不想發佈它。另外，請您詳細介紹該算法的來源？我不明白它是如何工作的或者它想要做什麼，沒有對你如何到達的高層次描述，我不知道我能提供多少幫助。 – templatetypedef 2011-02-05 12:23:51

該算法運行在最壞情況下的指數時間，因爲在下面的矩陣

它會嘗試約N！可能的組合。

對於多項式時間解決方案，使用矩陣創建一個二分圖，並找到perfect matching。

例如，具有矩陣

011 
101 
001

創建圖表

A X 
B Y 
C Z

與邊緣A-> Y，A-> Z，B-> X，B-> Z，C - >ž。

來源

2011-02-05 12:29:23 sdcvvc

感謝您的分析和改進的算法。 – ripper234 2011-02-05 14:43:26

在二進制矩陣找到一個「廣義對角線」

回答

相關問題