1

这个问题紧随其后：How to sort a 2D Matrix

在上一个问题中，OP 询问如何对矩阵进行排序，例如对行和列进行排序（M[i][j] <= M[i+1][j] and M[i][j] <= M [i][j+1])。我的回答很简单：像一维数组一样对行进行排序，对列也进行排序。然后我意识到解决方案不是唯一的。

我的问题是：什么算法可以为我们提供这个问题的所有解决方案？一个明显的解决方案是回溯算法，但我相信我们可以做得更好......

相同数组的解决方案示例：

0 0 1 2 
2 2 3 3 
3 5 5 6 
6 6 6 6 
7 7 9 9

和：

0 2 3 6
0 2 5 6
1 3 5 6
2 3 6 6
7 7 9 9

和：

0 2 3 6
0 2 5 6
1 3 5 7
2 3 6 7
6 6 9 9

和：

0 2 3 6
0 2 5 6
1 3 5 7
2 3 6 9
6 6 7 9

ETC...

4

2 回答 2

1

这将是最有效的生成解决方案，但是由于有很多方法，我提出了以下算法（它在伪 C++ 中）

int mat[n][m] = {-1}; // initialize all cells with -1
int sortedArray[n * m]; // the sorted array of all numbers, increasing order

void generateAllSolutions(set<pair<int, int> > front, int depth) {
    if (depth == n * m) {
        printMatrix();
        return;
    }

    for (pair<int, int> cell : front) {
         mat[cell.first][cell.second] = sortedArray[depth];
         newFront = front;
         newFront.remove(cell);
         if (cell.first < n - 1 &&
              (cell.second == 0 || mat[cell.first + 1][cell.second - 1] != -1)) {
             newFront.add(<cell.first + 1, cell.second>);
         }
         if (cell.second < m - 1 &&
              (cell.first == 0 || mat[cell.first - 1][cell.second + 1] != -1))
             newFront.add(<cell.first, cell.second + 1>);
         }
         generateAllSolutions(newFront, depth + 1);
         mat[cell.first][cell.second] = -1; // backing the track
    }
}

void solve() {
   set<pair<int, int> > front = {<0, 0>}; // front initialized to upper left cell
   generateAllSolutions(front, 0);
}

我正在做的是保持所有可能候选下一个最小数字的单元格的“前面”。这些基本上是所有的单元格，它们的上下邻居已经用较小的数字填充了。

因为我提出的算法可以优化为使用所有解决方案中所有单元格数量的操作，所以这对于您的任务来说应该是最佳可能的解决方案性能。

我想知道如果您只针对计算所有可能的解决方案是否有任何聪明的解决方案（我可以立即设计一个量级为 O(min(m n , nm ))的解决方案

于 2013-07-06T09:52:18.157 回答
0

一些修剪以改进回溯算法：

请注意，例如在 5*4 排序矩阵 M 中，

M[0][0]是所有元素集合中的最小值，S是M[4][3]最大值。

M[0][1]并且M[1][0]是 中的两个最小值S - ({M[0][0]}∪{M[4][3]})，而

M[3][3]并且M[4][2]是其中的两个最大值。

只有2 * 2个案例。

同样，M[1][1]是 中的最小值，M[3][2]是 中的最大值S - {M[0][0],M[4][3],M[0][1] , M[1][0],M[3][3] , M[4][2]}，这是确定的。

于 2013-07-06T09:52:46.440 回答