if no prior state or nextState.score < prior.score then
if prior exists
❸
remove (open, prior)
❹
insert (open, nextState)
❺
return "No Solution"
end
❶
A*
搜索
对棋局状态评分后将其存储在一个优先队列中。
❷
需要迅速在
开集
中找到匹配的状态。
❸
如果
A*
搜索
访问过一个
开集
中的状态,而这个状态现在有更小的分数(以及
走法)。
❹
用这个比较小的分数(以及走法)更新
开集
中的这个状态。
❺
因为
开集
是一个优先队列,所以
nextState
将会根据其评分放在合理的位置上。
7.9.1 输入/ 输出
该算法从搜索树的一个初始棋局状态开始,寻找一个目标状态。假设已经存在一个评估
函数
f
(
n
)
以及一个能可接受的函数
h
(
n
)
。该算法返回一个走法的序列,表示从初始状态
到目标状态的近似费用最小的路径(或者输出解不存在)。
7.9.2 使用环境
我们使用图
7-20
所示的八数码,图
7-21
和图
7-22
是从图
7-20
所示位置开始计算出的两 ...
Become an O’Reilly member and get unlimited access to this title plus top books and audiobooks from O’Reilly and nearly 200 top publishers, thousands of courses curated by job role, 150+ live events each month, and much more.