August 2017
Intermediate to advanced
360 pages
8h 35m
Chinese
Content preview from 算法技术手册（原书第2 版）
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,
O’Reilly covers everything we've got, with content to help us build a world-class technology community, upgrade the capabilities and competencies of our teams, and improve overall team performance as well as their engagement.I wanted to learn C and C++, but it didn't click for me until I picked up an O'Reilly book. When I went on the O’Reilly platform, I was astonished to find all the books there, plus live events and sandboxes so you could play around with the technology.I’ve been on the O’Reilly platform for more than eight years. I use a couple of learning platforms, but I'm on O'Reilly more than anybody else. When you're there, you start learning. I'm never disappointed.I'm always learning. So when I got on to O'Reilly, I was like a kid in a candy store. There are playlists. There are answers. There's on-demand training. It's worth its weight in gold, in terms of what it allows me to do.
192
｜
第
7
章
限制，要不然它很有可能会在不会有任何结果的路径上花费大量的时间。而本节将要介
绍的
A*
搜索
算法将会在搜索时利用启发式信息，智能地调整搜索策略。
A*
搜索
是一种迭代的有序搜索，它维护一个棋局状态的开集。在每次迭代时，
A*
搜索
都会使用一个评估函数
f
(
n
)
评估开集中的所有棋局状态，然后从中选择
f
(
n
)
最小的棋局
状态。我们定义
f
(
n
) =
g
(
n
) +
h
(
n
)
如下：
•
g
(
n
)
记录了从初始状态到状态
n
的最短走法。该值在算法执行过程中被不断修改并
记录。
•
h
(
n
)
估算从状态
n
到目标状态的最短走法。
因此，
f
(
n
)
估算的是从初始状态开始，经过状态
n
，到达目标状态的最短走法。
A*
搜索
只会在将棋局状态从开集中移除时才会检查是否已经达到目标状态（而
深度优先搜索
和
广度优先搜索
是在生成后继棋局状态时就会检查）。这点区别保证了
A*
搜索
找到的解
永远是离初始状态最短的（
g
(
n
)
），而且还有
h
(
n
)
并不会过高估计到目标状态的最短走法。
f
(
n
)
较小，则表明状态
n
更加靠近目标状态。而
f
(
n
)
最重要的部分则是如何智能地计算
出
h
(
n
)
，而
g
(
n
)
能够在算法不断进行的时候自动计算出来。如果
h
(
n
)
没有办法把比较可
靠的棋局状态（即能够达到目标状态）和不可靠的目标状态区分开来，那么
A*
搜索
基
本上不会比之前描述过的任何盲目搜索要好。尤其要注意的是，
h
(
n
)
的结果必须可接受
的（
admissible
），
即它不会计算出一个比到达目标状态的实际最小费用要高的费用。
如果
h
(
n
)
的结果过高，那么
A*
搜索
可能找不到最优解，但是，看出 ...
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.
Read now
Unlock full access
More than 5,000 organizations count on O’Reilly
O’Reilly covers everything we've got, with content to help us build a world-class technology community, upgrade the capabilities and competencies of our teams, and improve overall team performance as well as their engagement.Julian F.
I wanted to learn C and C++, but it didn't click for me until I picked up an O'Reilly book. When I went on the O’Reilly platform, I was astonished to find all the books there, plus live events and sandboxes so you could play around with the technology.Addison B.
I’ve been on the O’Reilly platform for more than eight years. I use a couple of learning platforms, but I'm on O'Reilly more than anybody else. When you're there, you start learning. I'm never disappointed.Amir M.
I'm always learning. So when I got on to O'Reilly, I was like a kid in a candy store. There are playlists. There are answers. There's on-demand training. It's worth its weight in gold, in terms of what it allows me to do.