找回密码
 欢迎注册
楼主: KeyTo9_Fans

[原创] 正方形网格里的最长路

[复制链接]
发表于 2022-9-21 15:17:14 | 显示全部楼层
KeyTo9_Fans 发表于 2022-9-21 14:21
再大就很难再穷举了。我们能否用局部调整法、启发式搜索、神经网络、模拟退火、蚁群、粒子群等智能优化算法 ...

有没有“好”的基因片段可遗传的特性?

点评

适应函数不好找,一般的适应函数效果不是很好  发表于 2022-9-23 08:37
紧挨在一起的阶梯(斜着走)是最好的基因片段,越多越好  发表于 2022-9-21 17:04
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2022-10-3 08:21:15 | 显示全部楼层
我创建了一个最优解方案数的数列:

https://oeis.org/A357516

同样需要展示代码:
  1. #include<cstdio>
  2. #include<cstring>

  3. const int p=62000001,q=9999;
  4. unsigned __int64 ak[p+q],bk[p+q];
  5. int al[p+q],bl[p+q],as[p+q],bs[p+q];
  6. int n,h,i,j,k,r,t,br[24],m,s,u,v,y;
  7. unsigned __int64 x,w;

  8. void ad(int d)
  9. {
  10.         if(j>n-2)
  11.         {
  12.                 if(br[n+1]>1)return;
  13.                 br[n+1]=0;
  14.         }
  15.         if(d>1)
  16.         {
  17.                 for(k=1;k<n+2;k++)
  18.                         if(br[k]>1)return;
  19.                 k=al[h]+1;
  20.                 r=as[h];
  21.                 if(k==m)s+=r;
  22.                 if(k>m)m=k,s=r;
  23.                 return;
  24.         }
  25.         w=1,x=0,y=al[h]+d;
  26.         for(k=1;k<n+2;k++,w*=5)
  27.                 x+=w*br[k];
  28.         for(k=int(x%p);bl[k];k++)
  29.                 if(x==bk[k])
  30.                 {
  31.                         if(y<bl[k])return;
  32.                         if(y>bl[k])bs[k]=0;
  33.                         break;
  34.                 }
  35.         if(!bl[k])u++,bs[k]=0,bk[k]=x;
  36.         bl[k]=y;
  37.         bs[k]+=as[h];
  38. }

  39. int gp(int p)
  40. {
  41.         if(br[p]==3)
  42.                 for(k=0;;p++)
  43.                 {
  44.                         if(br[p]==3)k++;
  45.                         if(br[p]==4)
  46.                         {
  47.                                 k--;
  48.                                 if(!k)return p;
  49.                         }
  50.                 }
  51.         if(br[p]==4)
  52.                 for(k=0;;p--)
  53.                 {
  54.                         if(br[p]==4)k++;
  55.                         if(br[p]==3)
  56.                         {
  57.                                 k--;
  58.                                 if(!k)return p;
  59.                         }
  60.                 }
  61.         return p;
  62. }

  63. void go(int s)
  64. {
  65.         if(s==0)
  66.         {
  67.                 ad(0);
  68.                 if(!i&&!j||i>n-2&&j>n-2)
  69.                 {
  70.                         br[j+1]=1;
  71.                         br[j+2]=2;
  72.                         ad(1);
  73.                         br[j+1]=2;
  74.                         br[j+2]=1;
  75.                         ad(1);
  76.                 }
  77.                 br[j+1]=3;
  78.                 br[j+2]=4;
  79.                 ad(1);
  80.                 return;
  81.         }
  82.         if(s==25||s==6||s==31||s==7||s==32||s==8||s==33||s==9||s==34)
  83.         {
  84.                 br[j+1]=0;
  85.                 br[j+2]=0;
  86.                 ad(0);
  87.                 return;
  88.         }
  89.         if(s==50)
  90.         {
  91.                 br[j+1]=1;
  92.                 ad(1);
  93.                 br[j+1]=2;
  94.                 br[j+2]=1;
  95.                 ad(1);
  96.                 if(!i&&!j||i>n-2&&j>n-2)
  97.                 {
  98.                         br[j+1]=1;
  99.                         ad(2);
  100.                 }
  101.                 return;
  102.         }
  103.         if(s==75||s==100)
  104.         {
  105.                 br[j+1]=1;
  106.                 ad(1);
  107.                 br[j+1]=s/25;
  108.                 br[j+2]=1;
  109.                 ad(1);
  110.                 if(!i&&!j||i>n-2&&j>n-2)
  111.                 {
  112.                         br[gp(j+1)]=2;
  113.                         br[j+1]=1;
  114.                         br[j+2]=1;
  115.                         ad(1);
  116.                 }
  117.                 return;
  118.         }
  119.         if(s==11)
  120.         {
  121.                 if(!i&&!j||i>n-2&&j>n-2)
  122.                 {
  123.                         br[j+1]=1;
  124.                         br[j+2]=1;
  125.                         ad(2);
  126.                 }
  127.                 br[j+1]=1;
  128.                 br[j+2]=2;
  129.                 ad(1);
  130.                 br[j+1]=2;
  131.                 br[j+2]=1;
  132.                 ad(1);
  133.                 return;
  134.         }
  135.         if(s==61)
  136.         {
  137.                 br[j+1]=1;
  138.                 br[j+2]=1;
  139.                 ad(2);
  140.                 return;
  141.         }
  142.         if(s==86||s==111)
  143.         {
  144.                 br[gp(j+2)]=2;
  145.                 br[j+1]=1;
  146.                 br[j+2]=1;
  147.                 ad(1);
  148.                 return;
  149.         }
  150.         if(s==16||s==21)
  151.         {
  152.                 br[j+2]=1;
  153.                 ad(1);
  154.                 br[j+1]=1;
  155.                 br[j+2]=s/5;
  156.                 ad(1);
  157.                 if(!i&&!j||i>n-2&&j>n-2)
  158.                 {
  159.                         br[j+1]=s/5;
  160.                         br[j+2]=1;
  161.                         br[gp(j+1)]=2;
  162.                         br[j+1]=1;
  163.                         ad(1);
  164.                 }
  165.                 return;
  166.         }
  167.         if(s==66||s==71)
  168.         {
  169.                 br[gp(j+1)]=2;
  170.                 br[j+1]=1;
  171.                 br[j+2]=1;
  172.                 ad(1);
  173.                 return;
  174.         }
  175.         if(s==91||s==96||s==121)
  176.         {
  177.                 if(s==91)br[gp(j+2)]=3;
  178.                 if(s==121)br[gp(j+1)]=4;
  179.                 br[j+1]=1;
  180.                 br[j+2]=1;
  181.                 ad(1);
  182.                 return;
  183.         }
  184.         if(s==23)
  185.         {
  186.                 br[j+1]=1;
  187.                 br[j+2]=4;
  188.                 ad(1);
  189.                 if(!i&&!j||i>n-2&&j>n-2)
  190.                 {
  191.                         br[j]=2;
  192.                         br[j+1]=1;
  193.                         br[j+2]=1;
  194.                         ad(1);
  195.                 }
  196.                 return;
  197.         }
  198.         if(s==73||s==98||s==123)
  199.         {
  200.                 br[j]=s/25;
  201.                 br[j+1]=1;
  202.                 br[j+2]=1;
  203.                 ad(1);
  204.                 return;
  205.         }
  206. }

  207. int main()
  208. {
  209.         for(n=2;n<20;n++)
  210.         {
  211.                 memset(al,0,sizeof(al));
  212.                 al[0]=1;
  213.                 as[0]=1;
  214.                 for(i=0;i<n;i++)
  215.                 {
  216.                         for(j=0;j<n;j++)
  217.                         {
  218.                                 for(u=h=0;h<p;h++)
  219.                                         if(al[h])
  220.                                         {
  221.                                                 x=ak[h];
  222.                                                 for(t=0,k=1;k<n+2;x/=5)
  223.                                                 {
  224.                                                         br[k]=int(x%5);
  225.                                                         if(br[k++]==2)t++;
  226.                                                 }
  227.                                                 go(br[j]+br[j+1]*5+br[j+2]*25);
  228.                                         }
  229.                                 if(u>v)v=u;
  230.                                 printf("%d %d %c",i,j,13);
  231.                                 memcpy(ak,bk,sizeof(ak));
  232.                                 memcpy(al,bl,sizeof(al));
  233.                                 memcpy(as,bs,sizeof(as));
  234.                                 memset(bl,0,sizeof(bl));
  235.                         }
  236.                         for(h=0;h<p;h++)
  237.                                 ak[h]*=5;
  238.                 }
  239.                 printf("n=%d: length=%d, ways=%d, status=%d\n",n,m-1,s,v);
  240.         }
  241.         return 0;
  242. }
复制代码

代码的运行结果如下:
6.png
  1. n=2: length=3, ways=2, status=5
  2. n=3: length=5, ways=6, status=15
  3. n=4: length=7, ways=20, status=47
  4. n=5: length=17, ways=2, status=115
  5. n=6: length=23, ways=64, status=285
  6. n=7: length=31, ways=44, status=720
  7. n=8: length=39, ways=512, status=1821
  8. n=9: length=51, ways=28, status=4572
  9. n=10: length=63, ways=4, status=11458
  10. n=11: length=75, ways=64, status=28883
  11. n=12: length=89, ways=520, status=73410
  12. n=13: length=105, ways=480, status=187665
  13. n=14: length=121, ways=6720, status=480863
  14. n=15: length=139, ways=43232, status=1232943
  15. n=16: length=159, ways=14400, status=3164525
  16. n=17: length=179, ways=226560, status=8139616
  17. n=18: length=201, ways=1646080, status=20994447
  18. n=19: length=225, ways=403712, status=54291496

  19. --------------------------------
  20. Process exited after 9448 seconds with return value 0
  21. 请按任意键继续. . .
复制代码
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2022-10-4 17:50:16 | 显示全部楼层
KeyTo9_Fans 发表于 2022-10-3 08:21
我创建了一个最优解方案数的数列:

https://oeis.org/A357516

紧挨在一起的阶梯(斜着走)是最好的基因片段,越多越好

最优解方案数的数列应该不会超过这个数字串:

a(01)=1=1
a(02)=1,2=3
a(03)=2,3+1=6
a(04)=1+3,4+2,1=11
a(05)=1,2+4,5+3,2=17
a(06)=2,3+5,6+4,3+1=24
a(07)=1+3,4+6,7+5,4+2,1=33
a(08)=1,2+4,5+7,8+6,5+3,2=43
a(09)=2,3+5,6+8,9+7,6+4,3+1=54
a(10)=1+3,4+6,7+9,10+8,7+5,4+2,1=67
a(11)=1,2+4,5+7,8+10,11+9,8+6,5+3,2=81
a(12)=2,3+5,6+8,9+11,12+10,9+7,6+4,3+1=96
a(13)=1+3,4+6,7+9,10+12,13+11,10+8,7+5,4+2,1=113
a(14)=1,2+4,5+7,8+10,11+13,14+12,11+9,8+6,5+3,2=131
a(15)=2,3+5,6+8,9+11,12+14,15+13,12+10,9+7,6+4,3+1=150
a(16)=1+3,4+6,7+9,10+12,13+15,16+14,13+11,10+8,7+5,4+2,1=171
a(17)=1,2+4,5+7,8+10,11+13,14+16,17+15,14+12,11+9,8+6,5+3,2=193
a(18)=2,3+5,6+8,9+11,12+14,15+17,18+16,15+13,12+10,9+7,6+4,3+1=216
a(19)=1+3,4+6,7+9,10+12,13+15,16+18,19+17,16+14,13+11,10+8,7+5,4+2,1=241
a(20)=1,2+4,5+7,8+10,11+13,14+16,17+19,20+18,16+15,14+12,11+9,8+6,5+3,2=267
a(21)=2,3+5,6+8,9+11,12+14,15+17,18+20,21+19,18+16,15+13,12+10,9+7,6+4,3+1=294

25楼的图能再来几个?谢谢!
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2022-10-4 21:36:08 | 显示全部楼层
假设一个最优解中蛇身位于角,边,内部的格子数目分别为$c_1,e_1,i_1$, 而对应空白格子数目为$c_2,e_2,i_2$
于是$c_1+c_2=4, e_1+e_2=4(n-2),i_1+i_2=(n-2)^2$.
除了头尾两个格子,蛇身上每个格子必然还同另外两个蛇身上格子相邻,所以它最多还和两个空白格子相邻。
如果我们累计蛇身上每个格子相邻的空白格子数目,这个数目为$2+2i_1+e_1$,其中2代表头尾两个格子相邻数目都要加1.
而这种累加方案中,每个内部空白格子最多被计算4次,边上空白格子对多比计算3次,角上最多计算两次,所以得到不等式
$2+2i_1+e_1\le 2c_2+3e_2+4i_2$, 即
$2+2i_1+e_1 \le 2(4-c_1)+3(4(n-2)-e_1)+4((n-2)^2-i_1)$整理后化简为
$3i_1+2e_1+c_1\le 3+6(n-2)+2(n-2)^2$
所以得到
$3(i_1+e_1+c_1) \le 3+6(n-2)+2(n-2)^2 + 4(n-2)+4\times 2$
于是得到
$i_1+e_1+c_1 \le \frac{2n(n+1)-5}3$,给出了蛇长的一个上界

点评

@KeyTo9_Fans 这种计数过程中,如果任何时候,遇到两个空白格子挨在一起,那么不等式右边可用白格计数数目就要减2,由此,动态规划搜索过程中白格相邻的次数如果为k,那么蛇长上界就会改为$\frac{2n(n+1)-5-2k}3$.  发表于 2022-10-6 14:36
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2022-10-5 12:20:29 | 显示全部楼层
A:1, 3, 5,  7,  17, 23, 31, 39, 51, 63, 75, 89, 105, 121, 139, 159, 179, 201, 225, 249, 275, 303,
331, 361, 393, 425, 459, 495, 531, 569, 609, 649, 691, 735, 779, 825, 873, 921, 971, ......

B:1, 3, 7, 11, 17, 24, 33, 42, 53, 64, 77, 92, 107, 123, 142, 162, 182, 205, 229, 254, 280, 308,
337, 367, 399, 432, 466, 502, 539, 577, 617, 658, 700, 744, 789, 835, 883, 932, 982, ......

C:1, 3, 7, 11, 17, 24, 33, 43, 54, 67, 81, 96, 113, 131, 150, 171, 193, 216, 241, 267, 294, 323,
353, 384, 417, 451, 486, 523, 561, 600, 641, 683, 726, 771, 817, 864, 913, 963, 1014, ......

A:\(a(n)=\lfloor\frac{2n^2-4n+29\ \ }{3}\rfloor\)  A357234       
B:\(a(n)=\lfloor\frac{2n^2-3n+23\ \ }{3}\rfloor\)  A331968       
C:\(a(n)=\lfloor\frac{2n^2+1\ }{3}\rfloor\)  A331968       
  A<B<C
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2022-10-5 18:49:30 | 显示全部楼层
有点看懂了!25楼的图挺不容易的,谢谢KeyTo9_Fans!
a(01):01+0+00=01,
a(02):03+0+00=03,
a(03):05+1+01=07,
a(04):07+1+03=11,
a(05):09+1+07=17,
a(06):11+1+11=23,23+1=24
a(07):13+1+17=31,31+2=33
a(08):15+1+23=39,39+3=42
a(09):17+1+31=49,49+4=53
a(10):19+1+39=59,59+5=64
a(11):21+1+49=71,71+6=77
a(12):23+1+59=83,83+9=92
a(13):25+1+71=97,97+10=107
a(14):27+1+83=111,111+12=123
a(15):29+1+97=127,127+15=142
a(16):31+1+111=143,143+19=162
a(17):33+1+127=161,161+21=182
a(18):35+1+143=179,
a(19):37+1+161=199,
a(20):39+1+179=219,

第1个数:我们总可以让第1行与第1列是蛇身,
第2个数:连接第1个数与第3个数,
第3个数:前面已有的数,
第4个数:阶梯(斜着走)增加的数
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
您需要登录后才可以回帖 登录 | 欢迎注册

本版积分规则

小黑屋|手机版|数学研发网 ( 苏ICP备07505100号 )

GMT+8, 2024-4-19 08:05 , Processed in 0.050779 second(s), 22 queries .

Powered by Discuz! X3.5

© 2001-2024 Discuz! Team.

快速回复 返回顶部 返回列表