«Обобщенная диагональ» в матрице 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;
}