正方形网格里的最长路 - 第4页 - 趣题妙解 - 数学研发论坛

aimisiyou 发表于 2022-9-21 15:17:14

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

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

KeyTo9_Fans 发表于 2022-10-3 08:21:15

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

https://oeis.org/A357516

同样需要展示代码：
#include<cstdio>
#include<cstring>

const int p=62000001,q=9999;
unsigned __int64 ak,bk;
int al,bl,as,bs;
int n,h,i,j,k,r,t,br,m,s,u,v,y;
unsigned __int64 x,w;

void ad(int d)
{
if(j>n-2)
{
if(br>1)return;
br=0;
}
if(d>1)
{
for(k=1;k<n+2;k++)
if(br>1)return;
k=al+1;
r=as;
if(k==m)s+=r;
if(k>m)m=k,s=r;
return;
}
w=1,x=0,y=al+d;
for(k=1;k<n+2;k++,w*=5)
x+=w*br;
for(k=int(x%p);bl;k++)
if(x==bk)
{
if(y<bl)return;
if(y>bl)bs=0;
break;
}
if(!bl)u++,bs=0,bk=x;
bl=y;
bs+=as;
}

int gp(int p)
{
if(br==3)
for(k=0;;p++)
{
if(br==3)k++;
if(br==4)
{
k--;
if(!k)return p;
}
}
if(br==4)
for(k=0;;p--)
{
if(br==4)k++;
if(br==3)
{
k--;
if(!k)return p;
}
}
return p;
}

void go(int s)
{
if(s==0)
{
ad(0);
if(!i&&!j||i>n-2&&j>n-2)
{
br=1;
br=2;
ad(1);
br=2;
br=1;
ad(1);
}
br=3;
br=4;
ad(1);
return;
}
if(s==25||s==6||s==31||s==7||s==32||s==8||s==33||s==9||s==34)
{
br=0;
br=0;
ad(0);
return;
}
if(s==50)
{
br=1;
ad(1);
br=2;
br=1;
ad(1);
if(!i&&!j||i>n-2&&j>n-2)
{
br=1;
ad(2);
}
return;
}
if(s==75||s==100)
{
br=1;
ad(1);
br=s/25;
br=1;
ad(1);
if(!i&&!j||i>n-2&&j>n-2)
{
br=2;
br=1;
br=1;
ad(1);
}
return;
}
if(s==11)
{
if(!i&&!j||i>n-2&&j>n-2)
{
br=1;
br=1;
ad(2);
}
br=1;
br=2;
ad(1);
br=2;
br=1;
ad(1);
return;
}
if(s==61)
{
br=1;
br=1;
ad(2);
return;
}
if(s==86||s==111)
{
br=2;
br=1;
br=1;
ad(1);
return;
}
if(s==16||s==21)
{
br=1;
ad(1);
br=1;
br=s/5;
ad(1);
if(!i&&!j||i>n-2&&j>n-2)
{
br=s/5;
br=1;
br=2;
br=1;
ad(1);
}
return;
}
if(s==66||s==71)
{
br=2;
br=1;
br=1;
ad(1);
return;
}
if(s==91||s==96||s==121)
{
if(s==91)br=3;
if(s==121)br=4;
br=1;
br=1;
ad(1);
return;
}
if(s==23)
{
br=1;
br=4;
ad(1);
if(!i&&!j||i>n-2&&j>n-2)
{
br=2;
br=1;
br=1;
ad(1);
}
return;
}
if(s==73||s==98||s==123)
{
br=s/25;
br=1;
br=1;
ad(1);
return;
}
}

int main()
{
for(n=2;n<20;n++)
{
memset(al,0,sizeof(al));
al=1;
as=1;
for(i=0;i<n;i++)
{
for(j=0;j<n;j++)
{
for(u=h=0;h<p;h++)
if(al)
{
x=ak;
for(t=0,k=1;k<n+2;x/=5)
{
br=int(x%5);
if(br==2)t++;
}
go(br+br*5+br*25);
}
if(u>v)v=u;
printf("%d %d %c",i,j,13);
memcpy(ak,bk,sizeof(ak));
memcpy(al,bl,sizeof(al));
memcpy(as,bs,sizeof(as));
memset(bl,0,sizeof(bl));
}
for(h=0;h<p;h++)
ak*=5;
}
printf("n=%d: length=%d, ways=%d, status=%d\n",n,m-1,s,v);
}
return 0;
}
代码的运行结果如下：

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

--------------------------------
Process exited after 9448 seconds with return value 0
请按任意键继续. . .

王守恩 发表于 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楼的图能再来几个？谢谢！

mathe 发表于 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$,给出了蛇长的一个上界

王守恩 发表于 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个数：阶梯(斜着走)增加的数

页: 1 2 3 [4]

数学研发论坛's Archiver