trouver une « diagonale généralisée » dans une matrice binaire

Question

A « diagonale généralisée » dans une matrice nxn est une sélection de N cellules, telles que:

1. Exactement une cellule est sélectionnée à partir de chaque rangée et de chaque colonne
2. Chaque cellule sélectionnée contient une valeur non nulle

Je cherche un algorithme pour trouver une diagonale généralisée dans O (n^3). Il me semble que l'algorithme de programmation dynamique suivant est "assez bon", mais je ne suis pas sûr de savoir comment analyser sa complexité.

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; 
} 

Answer 1

L'algorithme exécute dans le pire des cas, un temps exponentiel, car la matrice suivante

11111 
11111 
11111 
11111 
00000 

il va essayer sur les n! combinaisons possibles. Pour la solution de temps polynomiale, créez un graphique bipartite à l'aide de la matrice et trouvez perfect matching.

Par exemple, avec la matrice

011 
101 
001 

de créer le graphique

A X 
B Y 
C Z 

avec des bords A-> Y, A-> Z, B-> X, B-> Z, C -> Z.