极地之途

小铃铛 发表于 2023-2-6 08:27:15

这是第10季《最强大脑》中的一个游戏项目，要求玩家划出一条尽可能长的路线，路线的两端为圆点盲道块。
16块盲道块组成一块组合块，共有这样的块16个，每块内部已固定，玩家可调整这16块组合块，但只能平移，不能旋转，拼成4X4的盲道墙。
然后在这个4X4的盲道墙里划线。

小铃铛 发表于 2023-2-8 05:42:29

节目中，王宇轩选手划出了149格的线，但并不算最优解。
那么这题的最优解是多少格呢？

aimisiyou 发表于 2023-2-8 10:42:14

排列组合么？复杂度太高了。

mathe 发表于 2023-2-8 11:27:14

首先对于每个block可以穷举出每两个边界之间的最长路径。
比如第一个block应该只有5种可能的路径

但是第二个block好像可以14种可能的路径
另外一点比较麻烦的是两条不同的路径可能可以共存（不相交），但是也可能不行（相交）

然后应该考虑贪心法，尽量把可能的长的路径进行拼接。

小铃铛 发表于 2023-2-8 14:37:26

这题我也试玩了一下，用足了时间，大概数了一下，有163格。
坛友们也可以解闷玩玩看，能不能再多点。

小铃铛 发表于 2023-2-9 11:43:07

题板的组合块中有17块盲道小块是比较特殊的块，其中1-13号是无效块，14-17号中必定会有2块是无效块，所以，这题的最优解最多为256-15=241块

小铃铛 发表于 2023-2-11 20:15:44

在13,16号中我选择这样的路线，这会放弃一些格子，但只要需要且可控的情况下是可以接受的，这样的话，最优解可以超过211格。

小铃铛 发表于 2023-2-12 19:54:08

小铃铛发表于 2023-2-8 14:37
这题我也试玩了一下，用足了时间，大概数了一下，有163格。
坛友们也可以解闷玩玩看，能不能再多点。

把6号，12号组合块交换一下位置，尽管解决了错误，但损失了2格。应该长度有161格。

mathe 发表于 2023-2-13 10:21:28

代码搜索一个结果：
1. 仅考虑小段路径从一个小方块的一个边界到另外一个边界
2. 不考虑头尾两段从圆点到边界的小段路径。
当然在找到一个不错的结果后，通过适当添加和减少部分路径使得头尾变成圆点就可以变成满足要求的路径了。
结果先给出方块的排布顺序，然后对于每个方块，列出了里面所有的小段路径，比如
B14 （表示开始列方块 14的小段路径）
   Length 9 (se:D0R0) （说明这小段路径长度为9，从低端左边第0格开始到右边上面第0个结束，注意计数都是从0到3）
dhhh （图中小写字母代表路径经过格子，大写字母代表不经过
sHDD
ddSS
ddSS
   Length 6 (se:D2D3) （方块14使用了两段路径，这一段从底边后两格出发和结束）
DHHH
SHdd
DDss
DDss

Found weight=188
Block Layout
14 09 02 06
15 03 10 12
07 11 04 16
05 13 01 08
Output path in block:
B14
   Length 9 (se:D0R0)
dhhh
sHDD
ddSS
ddSS
   Length 6 (se:D2D3)
DHHH
SHdd
DDss
DDss
B09
   Length 7 (se:D0R0)
dhhh
sDDD
sSSD
sSSD
   Length 6 (se:D1D2)
DHHH
SddD
SssD
SssD
B02
   Length 4 (se:L0R0)
hhhh
DHDH
SHDH
DHHH
   Length 10 (se:R2R3)
HHHH
dhdH
sHdh
dhhh
B06
   Length 2 (se:D1L3)
HDHD
HSDD
HDSH
hdSD
   Length 5 (se:L0L2)
hdHD
HsDD
hdSH
HDSD
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
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 4 (se:D0R3)
DSSS
HDSS
HHDD
dhhh
B10
   Length 3 (se:D2L3)
DSSH
DSDD
HDHS
hhdS
   Length 3 (se:D3R1)
DSSH
DSDd
HDHs
HHDs
B12
   Length 3 (se:T1L1)
ddHS
dHHH
DSSD
DHDS
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
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
B16
   Length 4 (se:D2D3)
HDSS
DDDD
DSdd
HDss
B05
   Length 2 (se:T0T1)
ddHH
SSDD
DDSS
HHSS
   Length 3 (se:D3R1)
DDHH
SSDd
DDSs
HHSs
B13
   Length 8 (se:T2L1)
HDsS
hdsS
DssS
DddD
   Length 4 (se:T3R3)
HDSs
HDSs
DSSs
DDDd
B01
   Length 6 (se:T0R2)
sDHH
sDHH
dhhh
HHHH
   Length 4 (se:L3R3)
SDHH
SDHH
DHHH
hhhh
   Length 6 (se:R0R1)
Sdhh
Sdhh
DHHH
HHHH
B08
   Length 7 (se:T2L0)
hdsS
DssS
DddS
HHHD
   Length 7 (se:T3L3)
HDSs
DSSs
DDDs
hhhd
   Length 2 (se:L1L2)
HDSS
dSSS
dDDS
HHHD
dhhhdhhhhhhhhdHD
sHddsddDdhdHHsDD
ddsssssDsHdhhdSH
ddsssssDdhhhhdSD
dhdddssSDSSHddHS
dhhhhdsSDSDddHHH
sdddhhdDHDHsDSSD
ssdddhhhhhdsDHDS
sdhhddhhhhdsHDSS
sdddhddhhhdsDDDD
sssdhhddhhdsDSdd
ssdhhhdsdhhdHDss
ddHHHDsssdhhhdss
SSDdhdsssdhhdsss
DDSsDsssdhhhddds
HHSsDdddhhhhhhhd

小铃铛 发表于 2023-2-13 13:26:04

这个183格的线路还是有很多格子被浪费了，离最优解还有一些距离。

页: [1] 2

数学研发论坛's Archiver

极地之途