iseemu2009 发表于 2025-2-26 00:22:32

已有 1 人购买  本主题需向作者支付 1 枚金币 才能浏览 购买主题

mathe 发表于 2025-2-26 08:09:54

这个题目由于限制棋盘为6*6，其状态数为36*35!/(17!*18!)约等于163G个状态的最短路径问题，如果考虑旋转和翻转对称，可以再除以8，状态还是太多了的。
不过这个问题我们可以采用双向搜索，由于sqrt(163G)才0.4M,我们可以分别从起始和结束状态开始做广度优先搜索，记录所有中间状态，直到双方相遇。从概率上来说，数据量在M基本就会相遇了(生日悖论)

iseemu2009 发表于 2025-2-26 10:10:09

那试算一下4x4的盘面，初始状态和状态二都取图中左上部分4x4区域。其它不变

hujunhua 发表于 2025-2-26 10:31:12

状态数不能除以8，（旋转,反射）对称的两个状态不等价。因为从一个状态到另一个状态只能通过移动滑块，不能旋转、翻转棋盘。
把这些滑块在初始状态逐列从上到下编号1~15，任一状态都视为按此位置顺序的一个排列σ，那么每个状态都可赋一个逆序值τ(σ)。
滑块上下滑动不改变逆序值，左右滑动会改变6个，Δτ=±1±1±1±1±1±1≡0(mod2), 所以只有逆序值为偶数的状态才是可达的。

如果无视编号，只看颜色的话，同一个二色状态包括17!·18!个排列，其中奇偶各半，因为交换任何两个号块，奇偶改变。
所以任一个二色状态都包含可达排列，故都是可达的。

iseemu2009 发表于 2025-2-26 19:04:06

由于原题目中给出的数据有些大，计算量惊人，不便于思考和分析，我把相关数据作了一些精简，请大家重新考虑这个问题。

mathe 发表于 2025-2-27 08:53:34

4*4计算量很小，最少28步，体力值最小126
score:0
*011
0011
0011
0011
score:4
0*11
0011
0011
0011
score:7
0011
0*11
0011
0011
score:11
0011
01*1
0011
0011
score:17
00*1
0111
0011
0011
score:22
0*01
0111
0011
0011
score:27
*001
0111
0011
0011
score:30
0001
*111
0011
0011
score:34
0001
1*11
0011
0011
score:37
0001
1011
0*11
0011
score:40
0001
1011
0011
0*11
score:44
0001
1011
0011
01*1
score:50
0001
1011
00*1
0111
score:55
0001
1011
0*01
0111
score:60
0001
1011
*001
0111
score:63
0001
1011
0001
*111
score:67
0001
1011
0001
1*11
score:71
0001
1011
0001
11*1
score:75
0001
1011
0001
111*
score:81
0001
1011
000*
1111
score:86
0001
1011
00*0
1111
score:91
0001
1011
0*00
1111
score:97
0001
1*11
0000
1111
score:101
0001
11*1
0000
1111
score:105
0001
111*
0000
1111
score:111
000*
1111
0000
1111
score:116
00*0
1111
0000
1111
score:121
0*00
1111
0000
1111
score:126
*000
1111
0000
1111

mathe 发表于 2025-2-27 13:26:47

score:0
*011
0011
0011
0011
score:5
0*11
0011
0011
0011
score:10
01*1
0011
0011
0011
score:16
0111
00*1
0011
0011
score:20
0111
0*01
0011
0011
score:24
0111
*001
0011
0011
score:27
*111
0001
0011
0011
score:32
1*11
0001
0011
0011
score:37
11*1
0001
0011
0011
score:42
111*
0001
0011
0011
score:48
1111
000*
0011
0011
score:52
1111
00*0
0011
0011
score:56
1111
0*00
0011
0011
score:59
1*11
0100
0011
0011
score:64
11*1
0100
0011
0011
score:70
1101
01*0
0011
0011
score:76
1101
0110
00*1
0011
score:80
1101
0110
0*01
0011
score:86
1101
0110
0001
0*11
score:91
1101
0110
0001
01*1
score:94
1101
0110
00*1
0101
score:99
1101
0110
001*
0101
score:105
1101
0110
0011
010*
score:109
1101
0110
0011
01*0
score:112
1101
0110
00*1
0110
score:116
1101
0110
0*01
0110
score:120
1101
0110
*001
0110
score:126
1101
0110
0001
*110
score:131
1101
0110
0001
1*10
score:134
1101
0110
0*01
1010
score:137
1101
0*10
0101
1010
score:141
1101
*010
0101
1010
score:144
*101
1010
0101
1010
页: [1]
查看完整版本: 移动滑块的趣味难题