在二进制矩阵找到一个“广义对角线”

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

在二进制矩阵找到一个“广义对角线”

回答

相关问题