最大化矩阵中的特殊元素

Question

以下是问题陈述:

有一个大小为m×n个的矩阵和从1到m的所有数字*n个占据它的地方.现在,如果(递归定义),一个元素被称为特殊元素

-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

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

回溯

这是一个组合问题，可以通过回溯来解决。成功实现回溯算法来解决问题所需的关键点是：

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

我会这样解决：

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

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

或者也许有一点猜测......

即使进行了优化，回溯也可能会太慢，因为它试图找到所有可能的解决方案。另一种方法是使用启发式算法，如遗传算法、禁忌搜索、变量邻域搜索、模拟退火……

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