正方形网格里的最长路

aimisiyou

KeyTo9_Fans 发表于 2022-9-21 14:21
再大就很难再穷举了。我们能否用局部调整法、启发式搜索、神经网络、模拟退火、蚁群、粒子群等智能优化算法 ...

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

KeyTo9_Fans

我创建了一个最优解方案数的数列：

https://oeis.org/A357516

同样需要展示代码：

1. #include<cstdio>
   
2. #include<cstring>
   
3. 
   
4. const int p=62000001,q=9999;
   
5. unsigned __int64 ak[p+q],bk[p+q];
   
6. int al[p+q],bl[p+q],as[p+q],bs[p+q];
   
7. int n,h,i,j,k,r,t,br[24],m,s,u,v,y;
   
8. unsigned __int64 x,w;
   
9. 
   
10. void ad(int d)
    
11. {
    
12.         if(j>n-2)
    
13.         {
    
14.                 if(br[n+1]>1)return;
    
15.                 br[n+1]=0;
    
16.         }
    
17.         if(d>1)
    
18.         {
    
19.                 for(k=1;k<n+2;k++)
    
20.                         if(br[k]>1)return;
    
21.                 k=al[h]+1;
    
22.                 r=as[h];
    
23.                 if(k==m)s+=r;
    
24.                 if(k>m)m=k,s=r;
    
25.                 return;
    
26.         }
    
27.         w=1,x=0,y=al[h]+d;
    
28.         for(k=1;k<n+2;k++,w*=5)
    
29.                 x+=w*br[k];
    
30.         for(k=int(x%p);bl[k];k++)
    
31.                 if(x==bk[k])
    
32.                 {
    
33.                         if(y<bl[k])return;
    
34.                         if(y>bl[k])bs[k]=0;
    
35.                         break;
    
36.                 }
    
37.         if(!bl[k])u++,bs[k]=0,bk[k]=x;
    
38.         bl[k]=y;
    
39.         bs[k]+=as[h];
    
40. }
    
41. 
    
42. int gp(int p)
    
43. {
    
44.         if(br[p]==3)
    
45.                 for(k=0;;p++)
    
46.                 {
    
47.                         if(br[p]==3)k++;
    
48.                         if(br[p]==4)
    
49.                         {
    
50.                                 k--;
    
51.                                 if(!k)return p;
    
52.                         }
    
53.                 }
    
54.         if(br[p]==4)
    
55.                 for(k=0;;p--)
    
56.                 {
    
57.                         if(br[p]==4)k++;
    
58.                         if(br[p]==3)
    
59.                         {
    
60.                                 k--;
    
61.                                 if(!k)return p;
    
62.                         }
    
63.                 }
    
64.         return p;
    
65. }
    
66. 
    
67. void go(int s)
    
68. {
    
69.         if(s==0)
    
70.         {
    
71.                 ad(0);
    
72.                 if(!i&&!j||i>n-2&&j>n-2)
    
73.                 {
    
74.                         br[j+1]=1;
    
75.                         br[j+2]=2;
    
76.                         ad(1);
    
77.                         br[j+1]=2;
    
78.                         br[j+2]=1;
    
79.                         ad(1);
    
80.                 }
    
81.                 br[j+1]=3;
    
82.                 br[j+2]=4;
    
83.                 ad(1);
    
84.                 return;
    
85.         }
    
86.         if(s==25||s==6||s==31||s==7||s==32||s==8||s==33||s==9||s==34)
    
87.         {
    
88.                 br[j+1]=0;
    
89.                 br[j+2]=0;
    
90.                 ad(0);
    
91.                 return;
    
92.         }
    
93.         if(s==50)
    
94.         {
    
95.                 br[j+1]=1;
    
96.                 ad(1);
    
97.                 br[j+1]=2;
    
98.                 br[j+2]=1;
    
99.                 ad(1);
    
100.                 if(!i&&!j||i>n-2&&j>n-2)
     
101.                 {
     
102.                         br[j+1]=1;
     
103.                         ad(2);
     
104.                 }
     
105.                 return;
     
106.         }
     
107.         if(s==75||s==100)
     
108.         {
     
109.                 br[j+1]=1;
     
110.                 ad(1);
     
111.                 br[j+1]=s/25;
     
112.                 br[j+2]=1;
     
113.                 ad(1);
     
114.                 if(!i&&!j||i>n-2&&j>n-2)
     
115.                 {
     
116.                         br[gp(j+1)]=2;
     
117.                         br[j+1]=1;
     
118.                         br[j+2]=1;
     
119.                         ad(1);
     
120.                 }
     
121.                 return;
     
122.         }
     
123.         if(s==11)
     
124.         {
     
125.                 if(!i&&!j||i>n-2&&j>n-2)
     
126.                 {
     
127.                         br[j+1]=1;
     
128.                         br[j+2]=1;
     
129.                         ad(2);
     
130.                 }
     
131.                 br[j+1]=1;
     
132.                 br[j+2]=2;
     
133.                 ad(1);
     
134.                 br[j+1]=2;
     
135.                 br[j+2]=1;
     
136.                 ad(1);
     
137.                 return;
     
138.         }
     
139.         if(s==61)
     
140.         {
     
141.                 br[j+1]=1;
     
142.                 br[j+2]=1;
     
143.                 ad(2);
     
144.                 return;
     
145.         }
     
146.         if(s==86||s==111)
     
147.         {
     
148.                 br[gp(j+2)]=2;
     
149.                 br[j+1]=1;
     
150.                 br[j+2]=1;
     
151.                 ad(1);
     
152.                 return;
     
153.         }
     
154.         if(s==16||s==21)
     
155.         {
     
156.                 br[j+2]=1;
     
157.                 ad(1);
     
158.                 br[j+1]=1;
     
159.                 br[j+2]=s/5;
     
160.                 ad(1);
     
161.                 if(!i&&!j||i>n-2&&j>n-2)
     
162.                 {
     
163.                         br[j+1]=s/5;
     
164.                         br[j+2]=1;
     
165.                         br[gp(j+1)]=2;
     
166.                         br[j+1]=1;
     
167.                         ad(1);
     
168.                 }
     
169.                 return;
     
170.         }
     
171.         if(s==66||s==71)
     
172.         {
     
173.                 br[gp(j+1)]=2;
     
174.                 br[j+1]=1;
     
175.                 br[j+2]=1;
     
176.                 ad(1);
     
177.                 return;
     
178.         }
     
179.         if(s==91||s==96||s==121)
     
180.         {
     
181.                 if(s==91)br[gp(j+2)]=3;
     
182.                 if(s==121)br[gp(j+1)]=4;
     
183.                 br[j+1]=1;
     
184.                 br[j+2]=1;
     
185.                 ad(1);
     
186.                 return;
     
187.         }
     
188.         if(s==23)
     
189.         {
     
190.                 br[j+1]=1;
     
191.                 br[j+2]=4;
     
192.                 ad(1);
     
193.                 if(!i&&!j||i>n-2&&j>n-2)
     
194.                 {
     
195.                         br[j]=2;
     
196.                         br[j+1]=1;
     
197.                         br[j+2]=1;
     
198.                         ad(1);
     
199.                 }
     
200.                 return;
     
201.         }
     
202.         if(s==73||s==98||s==123)
     
203.         {
     
204.                 br[j]=s/25;
     
205.                 br[j+1]=1;
     
206.                 br[j+2]=1;
     
207.                 ad(1);
     
208.                 return;
     
209.         }
     
210. }
     
211. 
     
212. int main()
     
213. {
     
214.         for(n=2;n<20;n++)
     
215.         {
     
216.                 memset(al,0,sizeof(al));
     
217.                 al[0]=1;
     
218.                 as[0]=1;
     
219.                 for(i=0;i<n;i++)
     
220.                 {
     
221.                         for(j=0;j<n;j++)
     
222.                         {
     
223.                                 for(u=h=0;h<p;h++)
     
224.                                         if(al[h])
     
225.                                         {
     
226.                                                 x=ak[h];
     
227.                                                 for(t=0,k=1;k<n+2;x/=5)
     
228.                                                 {
     
229.                                                         br[k]=int(x%5);
     
230.                                                         if(br[k++]==2)t++;
     
231.                                                 }
     
232.                                                 go(br[j]+br[j+1]*5+br[j+2]*25);
     
233.                                         }
     
234.                                 if(u>v)v=u;
     
235.                                 printf("%d %d %c",i,j,13);
     
236.                                 memcpy(ak,bk,sizeof(ak));
     
237.                                 memcpy(al,bl,sizeof(al));
     
238.                                 memcpy(as,bs,sizeof(as));
     
239.                                 memset(bl,0,sizeof(bl));
     
240.                         }
     
241.                         for(h=0;h<p;h++)
     
242.                                 ak[h]*=5;
     
243.                 }
     
244.                 printf("n=%d: length=%d, ways=%d, status=%d\n",n,m-1,s,v);
     
245.         }
     
246.         return 0;
     
247. }

复制代码

代码的运行结果如下：

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. --------------------------------
    
21. Process exited after 9448 seconds with return value 0
    
22. 请按任意键继续. . .

复制代码

王守恩

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楼的图能再来几个？谢谢！

mathe

假设一个最优解中蛇身位于角，边，内部的格子数目分别为$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$,给出了蛇长的一个上界

王守恩

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

王守恩

有点看懂了！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个数：阶梯(斜着走)增加的数