这是一个创建于 738 天前的主题，其中的信息可能已经有所发展或是发生改变。
有描述不清楚的地方还请大佬们积极提出，我会积极回答。
现有一个 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) 最大化
 |
1
DIO OP 验证的时间复杂度倒好说，就是状态转移想不出优化的办法，只能是 n!吗
|
 |
2
sillydaddy 2022-11-16 13:28:53 +08:00
楼主说的状态转移，是指通过迭代的方式吗：
把 25!个排列中的每一个都看作一个状态，如果两个状态可以通过交换 2 个元素(不一定相邻)的方式切换，就说这两个状态是相邻的。也就是说，每个状态都有 25*24/2=300 个相邻的状态。 最终要求解的，是能够使Σpoint(ij)取得最大值的一个状态。 如果对于任一状态，该状态总是存在至少一个相邻的状态使得相邻状态的Σpoint(ij)值比该状态的值大，这样就总是能收敛到最大值了：因为每跌代一次，就使得Σpoint(ij)增大一次，而Σpoint(ij)的最大值是有限的，所以最终一定会收敛到最大值。 但我不确定这个假设条件是不是满足，感觉这个假设条件太强了。如果不满足的话，就是只会收敛到极大值而不是最大值。不过可以试验一下。 水平有限，我的思考目前就只能到这儿了。 |
|
3
sillydaddy 2022-11-16 13:32:05 +08:00
「如果对于任一状态，该状态总是存在至少一个相邻的状态使得相邻状态的Σpoint(ij)值比该状态的值大」
这个描述不对，应该是「除了使Σpoint(ij)取得最大值的状态外的任一状态」。 |
Select Language