algorithm - 最大化矩阵中的特殊元素

Question

下面是一个问题陈述:

有一个大小为m*n的矩阵，从1到m*n的所有数字都在其中占有一席之地。现在，元素被称为 special if(递归定义)

-it is the top left corner element(at position (0,0)) 
-an element at (x,y) is special if its neighbour is an element (m,n) such that (m,n) is    
 special and the element at (x,y) is greater than the element at(m,n) and all of the (m,n)'s neighbours.

单元格的邻居是与其共享边的单元格。因此，内部单元格有 4 个邻居，边缘单元格有 3 个邻居，角单元格有 2 个邻居。

问题指出矩阵中只有少数(可能是 0)个单元格已被填充。 其余的将以使用从 1 到 m*n 的所有数字的方式填充，并且我们将特殊元素的数量最大化。此外，如果可能有多个答案，则字典序最小矩阵将被视为答案。

如果一个矩阵的行主视图的字符串在字典序上比另一个矩阵小，则该矩阵在字典序上比另一个矩阵小。

Test case 1: //2 X 3 matrix
2 ? ? 
? ? 3 

Solution 1:
2 1 4 
5 6 3 

Test case 2: //6 X 6 matrix
? ? ? ? ? ? 
? ? ? ? ? ? 
? ? ? ? ? ? 
? ? ? ? ? ? 
? ? ? ? ? ? 
? ? ? ? ? ? 

Solution 2:
 1  2  3 13 14 15 
 4  6  8 10 11 16 
 5  7  9 12 19 17 
28 26 24 22 20 18 
29 27 25 23 21 36 
30 31 32 33 34 35

我的逻辑: 矩阵中的特殊元素总是连续的。因此，我们必须找出通过连接连续的特殊元素形成的最长此类路径。此外，在将元素放置在特殊元素(m，n)的相邻单元格(x，y)之前，我们首先填写特殊元素(m，n)的所有邻居(除了(x，y))和然后选择一个大于所有值的值来填充 (x,y)。

我不知道如何继续前进以及如何包含字典序最小的条件。请帮忙。

提前致谢。

Answer 1

最好的解决办法是找到一个算法来解决这个问题，并证明它是正确的。缺少它，还有更多选择。

回溯

这是一个组合问题，您可以使用 backtracking 求解.成功实现回溯算法以解决问题所需的关键点是:

1. 为下一步找到一个好的启发式
2. 找到一个好的早期停止启发式、分支定界

我会这样解决:

• 找到可以放置下一个特殊元素的所有可能位置。正如您已经指出的那样，这样的地方不会很多。
• 选择可用于添加下一个特殊值的所有可能的值组合，而不管回溯中的后续步骤如何。在每个步骤中跟踪哪些数字仍要放置，哪些是“常用”值和特殊值(通过使用递归或创建定制的数据模型)。矩阵的其余部分可以留空(或 0)，以便在回溯中进一步填充。对可能性进行排序，以便它们首先提供字典序较小的解决方案。尝试所有可行的可能性。
• 如果没有剩余的特殊值，则按字典顺序填充矩阵中的空位，这也是一项要求。

当您放置第 k 个特殊值 i 时，可以提前停止，这样您将永远无法比当前最佳解决方案做得更好。当然，当无法添加更多特殊值时，您还必须停止使用分支。创建一个像您建议的初始解决方案将是一个好的开始，并且比冷启动允许更多的分支切割。

或者可能需要一些猜测...

也许回溯会太慢，即使经过优化，因为它试图找到所有可能的解决方案。另一种方法是使用 heuristic algorithm , 比如 genetic algorithms , tabu search , variable neighborhood search , simulated annealing , ...

此类算法可能会很快找到可行的解决方案，但不利的一面是，该解决方案可能不是最佳解决方案。