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.
AI
寻路
｜
199
AI
寻路
值得注意的是，
深度优先搜索
和
广度优先搜索
从开集中得到下一个棋局状态只需要常数
时间，这得益于使用的队列或者栈。如果
开集
是一个有序链表，那么插入棋局状态的性
能将会是
O
(
n
)
，而这里也不能使用二叉堆，因为我们事先不知道有多少棋局状态需要评
估。综上所述，平衡二叉树是一个不错的选择，插入棋局状态和得到最小费用的棋局状
态的性能都是
O(log
n
)
。
7.9.4 算法分析
A*
搜索
的行为完全取决于启发式函数。
Russel
和
Norvig
的研究结果（
2003
）描述了高
效启发式函数的性质。
Barr
和
Feigenbaum
（
1981
）给出了一些当无法高效计算出一个可
接受的函数时的其他选择。随着棋局状态变得越来越复杂，启发式函数越来越重要，同
时也越来越难以设计。首先启发式函数必须足够高效，否则将会影响整个搜索过程。即
便如此，草草设计的启发式函数也能够较好地剪枝搜索空间。例如，对于
15
数码问题（八
数码问题的一个扩展），我们只需要几分钟的时间便能在八数码问题的
GoodEvaluator
函数基础上创建出
15
数码的版本。当需要从图
7-24
（右）的初始状态变为图
7-24
（左）
的目标状态时，
A*
搜索
能在处理仅仅
39
个棋局状态之后，就能迅速找到一个
15
步的解，
而此时
开集
中还有
43
个棋局状态。
图 7-24：15 数码问题的初始状态（右）和目标状态（左）
由于有着
15
步的限制，
深度优先搜索
在处理
22 136
个棋局状态之后，仍然没有找到解。
而
广度优先搜索
在处理
172 567
个状态（
85 213 ...
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.