• 不同节点包含的状态可能是相同的
搜索问题的求解
搜索策略的性能
• 完备性：当问题有解时，这个算法是否保证能找 到一个解？
• 最优性：这个搜索策略是否能找到最优解？ • 时间复杂度：找一个解需要花费多长时间？ • 空间复杂度：在执行搜索过程中需要多少内存？
普通搜索问题：求出一条从初始状态到目标状态之间的行动序列 全局搜索问题：求出所有从初始状态到目标状态之间的行动序列 最优化搜索问题：求出从初始状态到目标状态之间耗散最少的行动序列
合法行动与后继的确定性： 满足棋盘上所有皇后不能互 相攻击的后继才是合法的
环境的静态性： 棋盘的格局和大小不会改变
路径的耗散函数的确定性： 相邻两个状态之间所需步骤为1
搜索问题：求出（所有）合法的目标状态
搜索问题的组成
• 初始状态：智能体所处的初始状态 • 后继函数：输入给定状态，可以输出合法行动和
Searching Problems in AI
人工智能中的搜索问题
什么是搜索问题
搜索问题：已知智能体的初始状态和目标状态，求 解一个行动序列使得智能体能从初始状态转移到目 标状态。如果所求序列可以使得总耗散最低，则问 题称为最优搜索问题。
• 智能体的初始状态是确定的 • 智能体当前状态是否为目标状态是可以检测的 • 智能体的状态空间是离散的 • 智能体在每个状态可以采取的合法行动和相应后继状态是
• 对于无边界的搜索问题，可以通过对深度优先搜 索提供一个预先设定的深度限制m来防止深度优 先搜索进入死循环
• 如果目标深度d>深度限制m，深度有限搜索可能 无法得到解，因此完备性也无法保证
无信息的搜索策略
迭代深入搜索
• 用来寻找最合适的深度限制的通用策略，经常和深度优先 搜索结合使用
• 不断增大深度限制，直到找到目标节点
搜索问题的求解
搜索策略的分类
• 无信息的搜索策略：无法知道当前状态离目标状 态的“远近”或者不利用类似的先验信息来进行 搜索的策略
• 广度优先搜索（BFS，Breadth-first search） • 代价一致搜索（UCS，Uniform-cost search） • 深度优先搜索（DFS，Depth-first search） • 深度有限搜索（Depth-limited search） • 迭代深入搜索（Iterative deepening search）
几个典型的搜索问题
起始状态
目标状态
8-Puzzle问题
华容道是不是一个搜索问题？
状态空间的离散性： 8个格子的排列方式是离散的
合法行动与后继的确定性： 只有空格四周的格子是可以 移动的
环境的静态性： 九宫格的大小和形状在格子移动 过程中不会改变
路径的耗散函数的确定性： 相邻两个状态之间所需步骤为1
确定的 • 环境是静态的 • 路径的耗散函数是已知的
几个典型的搜索问题
路径规划问题
搜索问题：从Arad到Bucharest的路径 最优化搜索问题：从Arad到Bucharest的最短路径
起始状态：Arad
目标状态：Bucharest
状态空间的离散性： 城市是离散的
合法行动与后继的确定性： 与某一城市相邻的城市才能 成为合法后继 环境的静态性： 城市的相对位置不会改变 路径的耗散函数的确定性： 城市之间的距离是已知的
搜索问题的求解
搜索树
所有搜索过程都可以用搜索树算法来进行表示
搜索问题的求解
搜索树实例
搜索问题的求解
搜索树实例
搜索问题的求解
搜索树实例
搜索问题的求解
节点与状的区别
• 节点（Node）是一种数据结构，每个节点的信 息包括当前状态、父节点、子节点、深度和路径 耗散
• 状态（State）只是一种系统可能存在的形式
点序列
ED
C
B
GF ED C
GFE D
EDC
G F ED
无信息的搜索策略
代价一致搜索
• 累积路径耗散最小的节点先被扩展 • 倘若每一步的耗散都为正，则保证可以得到最优
解 • 若单步耗散相等，该算法和广度优先搜索一样
？ 为累积路径耗 散最小的节点
ED
C
B
EDC
？？ ？
无信息的搜索策略
深度优先搜索
• 后被访问的节点先进行扩展 • 每次扩展深度最深的节点 • “一条路走到黑”，对于无边界搜索问题无法保
• 有信息的（启发式）搜索策略：利用启发式信息 来进行搜索的策略
• 贪婪最佳优先搜索（Greedy best first search） • A*搜索（A* search）
不同搜索策略的区别仅在于扩展节点的顺序
无信息的搜索策略
广度优先搜索
• 先被访问的节点先进行扩展 • 每次扩展深度最浅的节点 • 可以用一个先进先出的数据结构来保存待扩展节
证完备性 • 可以用一个后进先出的数据结构来保存待扩展节
点序列
无信息的搜索策略
深度优先搜索
DE
C
B
HI EC D
DEC
HI EC
无信息的搜索策略
深度优先搜索
I EC H HI EC
I EC
EC I EC
无信息的搜索策略
深度有限搜索
• 深度优先搜索它可能错误地选择一条分支并且沿 着一条很长的（甚至是无限的）路径一直走下去
相应的后继状态 • 目标测试：用来确定给定的状态是否为目标状态 • 路径耗散函数：在两个给定状态之间进行转移所
需的“代价”
普通搜索问题：求出一条从初始状态到目标状态之间的行动序列 全局搜索问题：求出所有从初始状态到目标状态之间的行动序列 最优化搜索问题：求出从初始状态到目标状态之间耗散最少的行动序列
搜索问题：从起始状态到目标状态的移动方法 最优化搜索问题：从起始状态到目标状态步骤最少的移动方法
几个典型的搜索问题
八皇后问题
起始状态：空的棋盘
目标状态：棋盘上摆了八个皇后，并 且任意两个皇后都不能互相攻击。目 标状态不确定，但是当前状态是否为 目标状态是可以检测的。
状态空间的离散性： 0-8个皇后在棋盘上的摆放方式
• 结合了深度有限搜索的优点，又保证了完备性，还能保证 得到最优解
无信息的搜索策略
迭代深入搜索
无信息的搜索策略
策略之间的比较
为了避免含有相同状态的节点被重复扩展，可以用一个数据结构来记录所有被访 问过的节点。如果当前待扩展节点与某个已访问过的节点对应的状态相同的话， 则当前节点将不会被扩展。 这时树搜索（Tree Search）策略将成为图（Graph Search）策略