最大化矩阵中的特殊元素

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)。

我不知道如何继续，并如何包括字典上最小的条件。请帮忙。

提前感谢。

- Snu S

---

我不太理解这个定义。第一个测试用例中有多少个特殊元素？我理解为3个，即2、5和6。如果是这样的话，那么[2 1 6; 3 4 5]不是有更多的特殊元素（除了1之外的所有元素）吗？这是因为3大于2和1；4大于3和2；5大于1、3和4；6大于4和5。我是否正确理解了这个问题？ - justhalf

@justhalf 在第一个例子中，数字2和数字3被指定为左上角和右下角。因此，你的反例是无效的。 - jeffrey

m和n有上限吗？ - Mojo Risin

Answer 1

最好的解决方案是找到一种算法来解决问题，并证明其正确性。如果缺乏这方面的知识，还有其他更多的选择。

回溯法

这是一个组合问题，可以使用 回溯算法 解决。成功实现回溯算法以解决问题需要注意以下关键点：

1. 找到下一步的良好启发式算法
2. 找到良好的早期停止启发式算法，分支和界限

我会这样解决它：

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

当您放置第k个特殊值i时，可以进行早期停止，这样您将永远无法做得比当前最佳解决方案更好。当不能再添加更多特殊值时，您当然也必须停止一个分支。像您提议的那样创建初始解决方案将是一个很好的开始，并允许进行比从冷启动开始更多的分支剪枝。

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

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

这些算法可能会快速找到可行的解决方案，但缺点是该解决方案可能不是最优的。

- pvoosten