Skip to Main Content
算法技术手册(原书第2 版)
book

算法技术手册(原书第2 版)

by George T.Heineman, Gary Pollice, Stanley Selkow
August 2017
Intermediate to advanced content levelIntermediate to advanced
360 pages
8h 35m
Chinese
China Machine Press
Content preview from 算法技术手册(原书第2 版)
180
7
7-11:两步之后的井字棋棋局
不过,要实现如此大幅削减,唯一的途径是可行走法有序,而且最优走法排在最前面。
但是,我们的解并不会这样对井字棋的走法排序,所以可能会得到一些异常结果。例如,
将上面的棋局旋转
180
°
(见图
7-12
),那么
AlphaBeta
需要探测
960
棋局状态(节
省了
88.3%
)。这是由于它在扩展博弈树使用了另外一种排序法。因此,有些算法会
在静态评估函数重新排序以减少博弈树的规模。
7-12:两步之后的井字棋棋局,它是图 7-11 的旋转版本
7.6 搜索树
有些游戏只需要一个玩家参与,目标是为了从初始状态(搜索树的顶端结点)开始,经
过一系列的走法达到目标状态。
搜索树
就适用于这种情况。构建一棵树的原因就是为了
防止重复访问同一状态。算法在这里负责决定访问状态的顺序以达到目标。
八数码游戏是在一个
3
×
3
的网格上,放着
8
个小方块,分别标上
1~8
,有一个空的格子
没有方块。空格周围(水平的或者垂直的)方块可以移动到这里,方块原有位置便是一
个新的空格。这个游戏的目标就是从一个初始状态开始,移动空格周围的方块,达到目
标状态。我们可以看到图
7-13
的解路径便是用粗体标出来的从初始结点到目标结点
路径,一共用了
8
步。
搜索树通常会快速增长到数百万亿个状态,本章的算法将会告诉我们如何在搜索树中高
效快速地搜索。为了了解问题本身的复杂度,我们首先使用采用
深度优先搜索
广度优
先搜索
的寻路算法然后使用强有力的
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.
Start your free trial

You might also like

机器学习实战:基于Scikit-Learn、Keras 和TensorFlow (原书第2 版)

机器学习实战:基于Scikit-Learn、Keras 和TensorFlow (原书第2 版)

Aurélien Géron
Go语言编程

Go语言编程

威廉·肯尼迪
C++语言导学(原书第2版)

C++语言导学(原书第2版)

本贾尼 斯特劳斯特鲁普

Publisher Resources

ISBN: 9787111562221