一个算法问题，求大佬们给个思路

[DIO]

有描述不清楚的地方还请大佬们积极提出，我会积极回答。

现有一个 5*5 矩阵 Mat
[ a11 ，a12 , a13 , a14 , a15;
a21 ，a22 , a23 , a24 , a25;
a31 ，a32 , a33 , a34 , a35;
a41 ，a42 , a43 , a44 , a45;
a51 ，a52 , a53 , a54 , a55 ]

求一个矩阵 matR ，将 mat 再排列。 要求原矩阵 mat 中的相邻元素（横竖左右撇捺）在新生成 matR 中不相邻

对每个元素 aij 设定积分 point(ij). aij 在新矩阵 matR 中距离原相邻元素距离之和为 point(ij)
例如：aij 在原矩阵 Mat 的相邻元素{a(i-1)j,a(i-1)(j-1),......... } 在新矩阵 matR 中距离这些元素的直线距离单元格数为{1 ，1 ，1 ，1 ，1 ，1 ，1 ，1} 合计为 point(ij)=8

要求在生成的 matR 中 Σpoint(ij) 最大化

[DIO]

验证的时间复杂度倒好说，就是状态转移想不出优化的办法，只能是 n!吗

[sillydaddy]

楼主说的状态转移，是指通过迭代的方式吗：
把 25!个排列中的每一个都看作一个状态，如果两个状态可以通过交换 2 个元素(不一定相邻)的方式切换，就说这两个状态是相邻的。也就是说，每个状态都有 25*24/2=300 个相邻的状态。
最终要求解的，是能够使Σpoint(ij)取得最大值的一个状态。
如果对于任一状态，该状态总是存在至少一个相邻的状态使得相邻状态的Σpoint(ij)值比该状态的值大，这样就总是能收敛到最大值了：因为每跌代一次，就使得Σpoint(ij)增大一次，而Σpoint(ij)的最大值是有限的，所以最终一定会收敛到最大值。
但我不确定这个假设条件是不是满足，感觉这个假设条件太强了。如果不满足的话，就是只会收敛到极大值而不是最大值。不过可以试验一下。

水平有限，我的思考目前就只能到这儿了。

[sillydaddy]

「如果对于任一状态，该状态总是存在至少一个相邻的状态使得相邻状态的Σpoint(ij)值比该状态的值大」
这个描述不对，应该是「除了使Σpoint(ij)取得最大值的状态外的任一状态」。