有描述不清楚的地方还请大佬们积极提出,我会积极回答。
现有一个 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)取得最大值的状态外的任一状态」。 |