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.
200
｜
第
7
章
图 7-25：15 数码问题的复杂情况
很明显，这个草草写就的启发式函数并不高效，因为
15
数码问题可能有超过
10
25
个状
态（
Korf
，
2000
）。
7.9.5 衍生算法
如果逆向思维一下，可以不用局限于从初始状态向前搜索（
Kaindl
和
Kain
，
1997
），也
可以同时从目标状态向后搜索。一开始这种方法由于不切实际（资源受限）而被早期的
AI
研究人员放弃，但是
Kaindl
和
Kainz
提出了强有力的理由，坚称这种方法应该被重
新考虑。
另外一种广为人知的
A*
搜索
衍生算法叫作
迭代加深
A*
（也写作
IDA*
），它依赖于一系
列逐渐扩展深度限制的深度优先搜索（
Reinefeld
，
1993
）。对于每次迭代，搜索深度限
制都根据前次迭代的结果增加。
IDA*
比单独的
深度优先搜索
或者
广度优先搜索
要高效
得多，因为它是根据实际的走法而不是启发式函数的估计来计算实际的费用。
Korf
（
2000
）
曾描述过将启发式函数和
IDA*
结合起来是多么得高效——这种方法曾用于解决
15
数码
问题。在整个搜索过程中，
IDA*
会对超过
4
亿个棋局状态进行评分。
虽然
A*
搜索
能得到最小费用的解，但是搜索空间可能会过大以至于无法继续计算。针
对这些规模庞大的问题，我们可以通过以下几种方法来改进
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.