作者nicknick0630 (NICK)
看板Prob_Solve
标题[问题] UVa 11007 魔术方块 最少步骤解
时间Tue May 21 00:09:53 2019
UVa 连结 :
https://reurl.cc/8OKXo
题目简易说明
这题是要解一个 2x2x2 的二阶魔术方块 ( 6 面、6 颜色 )
会给定一个魔术方块的状态
然後要找出可以还原魔术方块的最少步骤是多少
输入面的顺序为 : Top , Front, Right , Bottom, Back , Left
且每面的初始色 : White, Red , Yellow, Blue , Orange, Green
我的解法一
参考维基百科 :
https://reurl.cc/Ea3Qn
二阶魔方最有只有
3674160 种状态
而且最多只要
14 个步骤就能将方块还原
以下是需要转动步骤的状态数:
所需步骤 状态数量
0 1
1 6
2 27
3 120
4 534
5 2256
6 8969
7 33058
8 870072
9 360508
10 930508
11 1350852
12 782536
13 90280
14 276
所以我就将这 3674160 利用 BFS 由上到下暴力列举出来
列举方法:
以 Front、Right、Bottom 三面相交的那块方块为基准点
可以做的转动只有 6 种 : U Up L Lp B Bp
U : Top 那面面对自己做 顺 时针旋转
Up : Top 那面面对自己做 逆 时针旋转
L : Left 那面
B : Back 那面
就从步骤 0 开始 ( 方块还原状态 )
依序做 6 种转动，并得到步骤 1 的方块状态
直到步骤 14
其中可以用一些规则去避免重复 ( 不然 6^14 = 7百多亿 )
1. L L L = Lp ( 转 270度 = 转 -90度 )
2. 若上一步骤是 L，则这一步骤就不能为 Lp ( 做白工 )
3. L L = Lp Lp ( 我选择遇到 Lp Lp 就不要做 )
但是除了以上三种，还是会有很多重复是抓不到的
所以我将每种状态放入 Hash Table 中
(
C++ unordered_multimap )
key : 根据方块的状态 (每一面颜色) 所 "乱凑" 出来的数值
value : 该方块的资讯 (状态、还原所需步骤等等)
每新算出一种状态 ( 不违反上面 3 个规则 )
还要去 Hash Table 中检查有没有重复，没有的话就同样丢入 Table 中
最後
只要把题目输入的方块状态同样依据上面算 key 的方法算出来
再去 Hash Table 找，并得到该方块的资讯，就可以知道最短步骤
缺点
这样太慢，UVa 时限是 3 秒，我光是跑完列举就要大概 10 秒了
其中大部分的时间都是花在 Hash Table 查找
( 因为 hash 会碰撞，所以只能用 equal_range(key) 去查找，但还是剖慢)
我的解法二
为了避免掉 Hash Table 查找
所以直接对题目给的方块状态去做暴力 BFS
不过这次就不使用 Hash Table 来储存找到的状态
也不检查除了上面 3 个规则以外是否还有重复的
这样会比较快
但是因为数量增长太大，也是会很慢而且记忆体还会爆掉
问题
请问各位大大有没有甚麽更快的做法呢?
UVa 上的数据很多人都可以在 1 秒内 AC，但我一职 TLE ...
或是我还有哪里可以再加快的呢?
谢谢
附上写得不好的程式码 ( 解法一 )
https://pastebin.com/embed_iframe/c2e3idba
--
※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 140.117.183.79
※ 文章网址: https://webptt.com/cn.aspx?n=bbs/Prob_Solve/M.1558368596.A.153.html
※ 编辑: nicknick0630 (140.117.183.79), 05/21/2019 00:11:47
※ 编辑: nicknick0630 (140.117.183.79), 05/21/2019 00:13:39
※ 编辑: nicknick0630 (140.117.183.79), 05/21/2019 00:56:40
1F：推 achicn3: 可以问杨老师 XD 05/21 01:55
2F：推 FRAXIS: 不能把 3674160 个状态找个 encoding 法 + perfect hash? 05/21 11:58
3F：推 FRAXIS: 而且你真的需要 unordered_multimap 吗？ 05/21 12:15
4F：推 fatcat8127: 双向BFS吗? 05/21 13:35
5F：→ nicknick0630: 回 F 大 ：当然如果可以找到perfect hash 应该就可 05/21 16:03
6F：→ nicknick0630: 以解决问题了，只是这样hash的方法的我真的设计不出 05/21 16:03
7F：→ nicknick0630: 来啊QQ 05/21 16:03
8F：→ nicknick0630: 回 fatcat 大：我有试过，不过同样也要去检查有没 05/21 16:04
9F：→ nicknick0630: 有规则外的重复状态，所以还是有一样的问题 05/21 16:04
11F：推 FRAXIS: 应该不用设计吧 因为状态数是固定的 只要随机试几个 05/21 21:10
12F：→ FRAXIS: 自然就会找的到 perfect hash? 05/21 21:11
感谢大大XD
原来有这东西，不过我还要研究一下 ...
14F：推 firejox: IDDFS ? 05/21 21:22
15F：推 oToToT: 从解状态跟待解状态两边同时开始BFS/IDDFS会较佳，至少上 05/21 22:10
16F：→ oToToT: 礼拜某个比赛这样会过@@ 05/21 22:10
那这样是不是也会需要一个 Table 呢
就等同於我的解法一，只是变成是点到为止的感觉XD
我来试试看，感谢你~
※ 编辑: nicknick0630 (140.117.183.79), 05/21/2019 22:45:09
17F：推 firejox: 如果担心记忆体爆掉 就把资料压在72个bit就好 05/21 23:03
18F：→ firejox: 或许可以用A*，大概是计算顶点的曼哈顿距离之类的 05/21 23:20
19F：推 idiont: 双向BFS可以过 刚刚测试过了 跑了0.720秒 05/21 23:30
20F：→ idiont: 6^24 < 2^63 所以可以靠long long存就好了 而且不会碰撞 05/21 23:38
我刚刚也有用双向 BFS 写出来了，快很多( oT 大说的 2 种状态各自 BFS )
只是 UVa 网站挂掉还不知道可以跑多快XD
不过看起来我的写法应该和你不太一样
想请问你一下你的资料是怎麽存的呢? ( 6^24 是甚麽意思 )
我的方法是: 6个颜色就是6种状态，需要 4 个 bits
一面有 4 个颜色 --> 24 bits 一面
方块有 6 个面 --> 最少 144 bits 一个方块的状态
不过我是用 6 个 int 去存的
※ 编辑: nicknick0630 (140.117.183.79), 05/22/2019 01:10:34
21F：推 idiont: 一格有6种情况 24格就6^24种情况 不过实际上大部分都不存 05/22 01:26
22F：→ idiont: 在就是了 05/22 01:26
23F：→ idiont: 然後一个方块会有24种摆放方式 我是每种都算出他的hash值 05/22 01:29
24F：→ idiont: 取最小的 05/22 01:29