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.
188
｜
第
7
章
将最大搜索深度设置为较大值看起来更好些，但图
7-17
表明这种方法只会导致巨大
的搜索树，并不能保证一定找到解。
随着深度的增加，解的质量可能会越来越不尽如人意
随着深度限制的增加，尽管我们会不断找到更多的解，但是这些解有时都远远大于
期望的规模（即更长的时间、更多的步数等）。
图 7-17：随着深度增加，深度优先搜索搜索树的规模
有意思的是，对于
N1
，没有限制的
深度优先搜索
会在访问
30
个棋局状态之后迅速找到
一个
30
步的解，而这时
开集
中仍然有
23
个棋局状态。但是，这种好事可不会发生在
N2
和
N3
上。
7.8 广度优先搜索
广度优先搜索
通过系统地评估距离初始棋局状态最近的尝试寻找到一条最短路径。它保
证如果找到一条到目标状态的路径，那么这条路径肯定是最短路径。
事实上，
深度优先搜索
和
广度优先搜索
最本质的区别就是
广度优先搜索
使用队列来保存
开集，而
深度优先搜索
使用栈。每次迭代时，
广度优先搜索
从队列头拿出一个未访问的
状态，然后从这个状态开始，计算后继状态。如果达到了目标状态，那么搜索结束。和
深度优先搜索
一样，
广度优先搜索
也不会访问一个状态两次。对于任何找到的后继状态，
如果它已经在
闭集
中，那么算法会抛弃这个状态，否则的话它会被放入开集队列尾部，
以供后续搜索。
从图
7-18
的状态开始，计算出的搜索树如图
7-19
所示，我们可以看到算法在寻找过所
有
4
步路径之后，找到了一个
5
步的解（几乎所有
5
步的路径都被探测过）。图中
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.
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.