RGZN_2图搜索技术中的状态空间法
11 9 4 15 1 2 3 4 1 3 ? 12 -----------------------------, 5 6 7 8
7 5 8 6 9 10 11 12 13 2 10 14 13 14 15 ? 初始棋局 目标棋局
图2.1 十五数码难题
2
3
4
5
6
7
8
图(a) 图(b)
9
10
i
ji
j
11
12
1212
1231223
1223123
13
14
X1 X2 X3 X1 X2 X3
<------------, X4 ? X5 ? X4 X5
X6 X7 X8 X6 X7 X8
15
,
,
16
,
17
nn i j
i
jji
i
j
nn i j
18
i1i2ik
ij-1ij
i1ik
i
j
ji
j为i
ij
19
iji
j
初始状态 -----------,目标状态 解
某指定节点 ---------, 另一节点 路径 –-最小费用
20
21
22
23
24
,
10
7
?
, ,
0 C
,
(A) 7 6
(AB) (AC) (AD) (AE)
25
26
27
goto(U)(W ,0 ,Y ,z )(U ,0 ,Y ,z )
pushbox(V)(W ,0 ,W ,z )(V ,0 ,V ,z )
28
climbbox(W ,0 ,W ,z )(W ,1 ,W ,z )
grasp (C ,1 ,C ,0 )(C ,1 ,C ,1 )
29
30
31
Γ
Γ
32
33
34
35
S
if ? then ?
if ? then ? .G
规则
编码规则下载淘宝规则下载天猫规则下载麻将竞赛规则pdf麻将竞赛规则pdf
应用费用 控制策略费用
系 统 总 费 用
计规 控制策略费用 则算 应 用费(为选优而增加的费用) 费用 用
搜索空间大
小费用
0
0 启发信息量
36
37
Γ
38
OPEN表格式 CLOSED表格式
状态结构 返回指针 编号 状态结构 返回指针
39
40
41
42
43
44
45
46
?
失败退出
(N)
47
48
49
A A B
B C C
初始态 目标态
50
51
52
53
注:
OPEN表格式 CLOSED表格式
状态字符串 代价g(i) 状态字符串 代价g(i)
54
55
56
57
58
59
60
61
62
63
64
65
66
67
f =?
68
i
8
? l ii
i=1
f =?
69
70
=? S
71
*
72
ij
73
i
i
*
ii
*
*
74
75
76
77