-
Notifications
You must be signed in to change notification settings - Fork 17
/
readme.txt
78 lines (50 loc) · 3.13 KB
/
readme.txt
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
不到 800 行代码,彻底搞定魔方还原问题
VC 可以编译运行,或者用 mingw 的 gcc 编译都可以
msys2 + mingw32 环境下编译方法:
gcc -Wall -o cube cube.c
总共代码不到 800 行,还原速度在 10s 左右,当然还可以进一步优化。
一些符号的含义:
F - 正面,程序运行后白色的这一面
B - 背面,黄色面
L - 左面,紫色面(标准魔方应该是橙色,但是 windows 控制台无法显示橙色,用紫色替代)
R - 右面,红色面
U - 上面,蓝色面
D - 下面,绿色面
命令说明:
魔方操作命令:
f - 正面顺时针旋转
f2 - 正面 180 度旋转
f' - 正面逆时针旋转
其他面以此类推:
f2 f' b b2 b' u u2 u' d d2 d' l l2 l' r r2 r'
init - 魔方复位
rand - 随机打乱魔方,可以直接 rand 或者 rand n,n 为随机打乱次数
input - 输入魔方状态,按照提示输入即可
solve - 自动还原魔方
help - 帮助信息
exit - 退出程序
所有命令都是用小写字母。
数据结构和算法说明:
数据结构方面,每个面都用简单的二维数组来表示。要点是六个面的旋转操作的实现,以及魔方状态的显示,和状态输入。
算法方面,主要是用到了启发式的广度优先搜索。要点在于魔方状态的评估函数,剪枝方法,搜索算法等。
当然,你还得懂魔方。
程序代码量不大,也写得足够精简,可仔细品味。如有不懂可以提问。
搜索算法说明:
程序将魔方状态分为以下阶段(每个阶段完全归位会加 4 分):
fcross0 - 正面十字还原,不包含第一层的边块
fcross1 - 正面十字还原,包含第一层的四个边块
fcorners - 第一层全部归位
medges - 一二层全部归位
bcross - 一二层全部归位,并且第三层做出十字
bsurface - 底面做出十字
bcorners - 第三层角块归位
bedges - 第三层边块归位(彻底还原)
在进行搜索时,按以上的顺序,分阶段的完成搜索。
cube_check_state 是魔方状态的评估函数:
当参数 flag 为 0 时,是从 fcross0 开始评估 cube 能到达的最好的还原阶段
当参数 flag 为大于 0 的数值时,实际上是指定了一个目标阶段,评估函数会从 fcross0 开始评估,直到达到这个目标阶段最多能得到多少分(也就是有多少方块归位)
flag 等于 0 时,主要用于计算当前的 cube 状态,是否达到了目标状态
flag 大于 0 时,用于计算在给定的目标状态下,当前 cube 能得多少分,主要用于剪枝操作。
比如说,我都已经两层还原了,如果当前扩展出来的节点,跟两层还原相比差太远了,我就没必要保留这个扩展节点了。
search 函数是一个广度优先搜索的算法实现,采用了 open 表 + close 表来扩展节点并进行搜索。
open 表做为一个队列来使用因此是广度优先。close 通常用来检查某个节点是否已经被扩展过,实测如果加上这个检查,反而速度变得非常慢,因此 close 表没有真正用到。