极地之途

mathe · 发表于 2023-2-13 13:53:11

Found weight=197
Block Layout
14 05 02 10
15 04 09 13
07 11 03 06
12 16 01 08
Output path in block:
B14
   Length 9 (se:D0R0)
dhhh
sHDD
ddSS
ddSS
   Length 6 (se:D2D3)
DHHH
SHdd
DDss
DDss
B05
   Length 6 (se:D2D3)
DDHH
SSdd
DDss
HHss
   Length 8 (se:L0R0)
ddhh
ssDD
ddSS
HHSS
B02
   Length 4 (se:L0R0)
hhhh
DHDH
SHDH
DHHH
   Length 6 (se:L1R3)
HHHH
dHDH
sHDH
dhhh
   Length 4 (se:R1R2)
HHHH
DHdh
SHdh
DHHH
B10
   Length 4 (se:T1L2)
DsSH
DsDD
hdHS
HHDS
   Length 3 (se:D2L3)
DSSH
DSDD
HDHS
hhdS
   Length 2 (se:L0L1)
dSSH
dSDD
HDHS
HHDS
B15
   Length 3 (se:T0T2)
dhdD
DHHH
SDDD
SSDD
   Length 1 (se:T3R0)
DHDd
DHHH
SDDD
SSDD
   Length 6 (se:D0R1)
DHDD
dhhh
sDDD
sSDD
   Length 6 (se:D1R2)
DHDD
DHHH
Sddd
Ssdd
B04
   Length 3 (se:T2L0)
hhdS
HHDS
HHDS
DHHD
   Length 7 (se:T3D0)
HHDs
HHDs
HHDs
dhhd
   Length 6 (se:L1L2)
HHDS
hhdS
hhdS
DHHD
B09
   Length 7 (se:D0R0)
dhhh
sDDD
sSSD
sSSD
   Length 6 (se:D1D2)
DHHH
SddD
SssD
SssD
   Length 1 (se:D3R3)
DHHH
SDDD
SSSD
SSSd
   Length 2 (se:R1R2)
DHHH
SDDd
SSSd
SSSD
B13
   Length 5 (se:T2D1)
HDsS
HDsS
DSsS
DddD
   Length 4 (se:L0L1)
hdSS
hdSS
DSSS
DDDD
   Length 2 (se:L2L3)
HDSS
HDSS
dSSS
dDDD
B07
   Length 4 (se:T0D0)
sDHH
sDDD
sSSD
sSDH
   Length 3 (se:T1R0)
Sdhh
SDDD
SSSD
SSDH
   Length 7 (se:D1R3)
SDHH
SddD
SssD
Ssdh
   Length 2 (se:R1R2)
SDHH
SDDd
SSSd
SSDH
B11
   Length 1 (se:T0L0)
dDHH
HDDH
HHDD
HHDS
   Length 3 (se:D2L3)
DDHH
HDDH
HHDD
hhdS
   Length 2 (se:D3R2)
DDHH
HDDH
HHDd
HHDs
   Length 5 (se:L1R0)
Ddhh
hdDH
HHDD
HHDS
   Length 5 (se:L2R1)
DDHH
HDdh
hhdD
HHDS
B03
   Length 1 (se:T0L0)
dSSS
HDSS
HHDD
DHHH
   Length 3 (se:T1L1)
DsSS
hdSS
HHDD
DHHH
   Length 5 (se:T2L2)
DSsS
HDsS
hhdD
DHHH
   Length 3 (se:T3R2)
DSSs
HDSs
HHDd
DHHH
   Length 4 (se:D0R3)
DSSS
HDSS
HHDD
dhhh
B06
   Length 7 (se:T1D2)
Hdhd
HSdd
HDsH
HDsD
   Length 4 (se:L2L3)
HDHD
HSDD
hdSH
hdSD
B12
   Length 2 (se:T0T1)
ddHS
DHHH
DSSD
DHDS
B16
   Length 4 (se:T2T3)
HDss
DDdd
DSDD
HDSS
B01
   Length 6 (se:T0R2)
sDHH
sDHH
dhhh
HHHH
   Length 6 (se:R0R1)
Sdhh
Sdhh
DHHH
HHHH
B08
   Length 7 (se:T2L0)
hdsS
DssS
DddS
HHHD
   Length 2 (se:L1L2)
HDSS
dSSS
dDDS
HHHD
dhhhddhhhhhhdsSH
sHddssdddHdhdsDD
ddssddsssHdhhdHS
ddssHHssdhhhhhdS
dhddhhdsdhhhhdsS
dhhhhhdssdddhdsS
sdddhhdssssddSsS
ssdddhhdsssddddD
sdhhddhhdsssHdhd
sdddhddhhdssHSdd
sssdhhddhhddhdsH
ssdhhhdsdhhhhdsD
ddHSHDsssdhhhdsS
DHHHDDddsdhhdssS
DSSDDSDDdhhhdddS
DHDSHDSSHHHHHHHD

bk1.185.out.zip (6.4 KB, 下载次数: 0)

mathe · 发表于 2023-2-13 14:18:24

bk2.220.out.zip (6.78 KB, 下载次数: 1)
按我的搜索标准，找出最大长度230，附件中包含了所有长度不少于220的结果。

小铃铛 · 发表于 2023-2-13 15:05:07

我就把这题的最优解贴一下吧。长度230格

mathe · 发表于 2023-2-15 15:11:07

现在介绍一下怎么用计算机穷举这个问题。由于有16个小块，我们可以现在每个小块里面穷举从一条边进入到从一条边离开的所有可能路径，这个递归穷举即可。比如
Length 6 (se:L0L1)
hhdS
hhdS
HHDS
DHHD
上面例子中字母H代表可以横移的格子，D代表必须拐弯的格子，S代表必须竖移的格子。
小写字母是选择的路径，上面标记L0L1表示从左边第0格进入，左边第1格离开。
所以上面移动路径经过的格子依次为L0进入到(0,0), (1,0),(2,0),(2,1),(1,1),(0,1)从L1离开。
需要注意所有进入和离开的方向必须是垂直边界的，比如
HdHH
HsHH
HsHH
HsHH
就不是合法的路径，因为上面的d虽然在边界上，但是在这里比如拐弯，导致还不能离开当前方格，所以必须继续延长路径变成
hdHH
HsHH
HsHH
HsHH
就合法了。

然后对于同一个4x4的小方块，我们可以搜索到多个不同的路径，这些路径有些会相交，所以不能同时出现，但有些不相交，就可以同时出现，比如对于第一个小方块，可以找到5条不同的路径:
output for board 0
Length 3 (se:T0L2)
sDHH
sDHH
dHHH
HHHH
Length 6 (se:T0R2)
sDHH
sDHH
dhhh
HHHH
Length 3 (se:T1R0)
Sdhh
SDHH
DHHH
HHHH
Length 4 (se:L3R3)
SDHH
SDHH
DHHH
hhhh
Length 6 (se:R0R1)
Sdhh
Sdhh
DHHH
HHHH
其中T0L2路径和T0R2路径都经过格子(0,0),必然不能共存。但T0L2路径和L3R3路径互不相交，可以同时出现。
代码里将同一个方块里面所有可能的路径按搜索的顺序编号，然后找出所有可以公共出现的路径集合（用索引编号的集合表示），
这部分搜索也很简单，枚举所有的子集，然后判断里面路径是否都不经过公共格子即可（每条路径经过的格子可以用集合表示）
比如上面列出的第一个方块中所有合法路径组合有
Block 0
16{ 1 3 4 }
13{ 1 2 3 }
13{ 0 3 4 }
12{ 1 4 }
10{ 1 3 }
10{ 0 2 3 }
10{ 3 4 }
9{ 1 2 }
9{ 0 4 }
7{ 0 3 }
7{ 2 3 }
6{ 1 }
6{ 0 2 }
6{ 4 }
4{ 3 }
3{ 0 }
3{ 2 }
0{ }
共18种，其中每个路径组合中前面数字代表它们经过的格子数目，{}里面的数字代表各路径编号。
而最后一个方块的路径组合最多，有256种不同的组合。
然后我们可以将每个方块的每个路径组合看成一个马赛克，总共有16类买赛克，每类中有最少18种最多256种不同的花纹。
我们需要从每一类中挑选一个花纹，组合出一个合法的路径。
然后就是递归穷举，按16个方块位置的顺序，每次从所有还没有使用过的类中挑选一个花纹，拼凑上去。
而拼凑过程的裁剪就非常重要了，因为完全裁剪复杂度太高了。
由于我们知道整条路径拼接完成以后，只有一个起始点和一个结束点，所以拼凑过程需要将大部分小路径在边界上完全拼接起来。
比如如果我们选择左上角第一个马赛克为:
Length 6 (se:T0R2)
sDHH
sDHH
dhhh
HHHH
加上
Length 4 (se:L3R3)
SDHH
SDHH
DHHH
hhhh
由于这个小方块在最左上角, 所以它左边和上边的端点都无法继续接上其它方块了。现在它的左上边界已经有T0,L3两个端点。这说明路径的其它端点都需要在后续方块之间的拼接中被完全接上。由于它两条路径余下两个端点是R2,R3, 为了能够完美拼接，排在它右边的第二个方块必须使用L2,L3两个端点和它对接，而且第二个方块的路径中也能有顶上的端点。这个淘汰机制使得大部分花纹都无法胜任从而将它们都过滤，大大降低了搜索时间。
另外一个可以使用的过滤过程是如果我们将每个小方块使用格子数目最多的花纹的格子数累加，可以得到242，这是一个路径能够经过的最大格子数目的上限。而搜索过程中，我们每确定一个方块的花纹，它实际使用的格子数目很可能少于这个方块的理论上界，从而总的上界242也会降低。而随着确定的方块的数目降低，这个总的上界会一直持续降低。所以如果我们只搜索长度大于某个值的路径（比如不小于220），那么只要理论上界降低到搜索目标之下，我们就可以裁剪掉了。这种方案，使得搜索的目标长度约长，可以裁剪掉越多的搜索空间，从而提高速度。
通过上面两种裁剪方案的组合，我们可以在比较短的时间穷举出长度不超过220的所有路径（可以发现大部分结果都是230路径的一部分）

bk2.zip (5.03 KB, 下载次数: 1)

账号		自动登录	找回密码
密码			欢迎注册

[讨论] 极地之途

点评