V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
DIO
V2EX  ›  算法

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

  •  1
     
  •   DIO · 2022-11-15 17:14:15 +08:00 · 704 次点击
    这是一个创建于 500 天前的主题,其中的信息可能已经有所发展或是发生改变。

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

    现有一个 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) 最大化

    3 条回复    2022-11-16 13:32:05 +08:00
    DIO
        1
    DIO  
    OP
       2022-11-15 21:37:58 +08:00
    验证的时间复杂度倒好说,就是状态转移想不出优化的办法,只能是 n!吗
    sillydaddy
        2
    sillydaddy  
       2022-11-16 13:28:53 +08:00
    楼主说的状态转移,是指通过迭代的方式吗:
    把 25!个排列中的每一个都看作一个状态,如果两个状态可以通过交换 2 个元素(不一定相邻)的方式切换,就说这两个状态是相邻的。也就是说,每个状态都有 25*24/2=300 个相邻的状态。
    最终要求解的,是能够使Σpoint(ij)取得最大值的一个状态。
    如果对于任一状态,该状态总是存在至少一个相邻的状态使得相邻状态的Σpoint(ij)值比该状态的值大,这样就总是能收敛到最大值了:因为每跌代一次,就使得Σpoint(ij)增大一次,而Σpoint(ij)的最大值是有限的,所以最终一定会收敛到最大值。
    但我不确定这个假设条件是不是满足,感觉这个假设条件太强了。如果不满足的话,就是只会收敛到极大值而不是最大值。不过可以试验一下。

    水平有限,我的思考目前就只能到这儿了。
    sillydaddy
        3
    sillydaddy  
       2022-11-16 13:32:05 +08:00
    「如果对于任一状态,该状态总是存在至少一个相邻的状态使得相邻状态的Σpoint(ij)值比该状态的值大」
    这个描述不对,应该是「除了使Σpoint(ij)取得最大值的状态外的任一状态」。
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   我们的愿景   ·   实用小工具   ·   2841 人在线   最高记录 6543   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 31ms · UTC 13:44 · PVG 21:44 · LAX 06:44 · JFK 09:44
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.