1、第二部分第二部分 知识表示与推理知识表示与推理 谓词逻辑与归结原理谓词逻辑与归结原理 命题逻辑命题逻辑 谓词逻辑谓词逻辑 *归结原理归结原理 Herbrand定理定理 知识表示知识表示 知识概述知识概述 *产生式表示产生式表示 语义网络表示语义网络表示 框架表示框架表示 其他表示方法其他表示方法第三部分 人工智能高级专题 基于模型的诊断基于模型的诊断 配置问题配置问题 智能规划智能规划 调度调度搜索算法把问题作为输入，并以行动序列的形式返回搜索算法把问题作为输入，并以行动序列的形式返回问题的解。一旦找到一个解，那么它所建议的行动就问题的解。一旦找到一个解，那么它所建议的行动就可以付诸实施，这被
2、称为执行阶段。因而我们可以对可以付诸实施，这被称为执行阶段。因而我们可以对问题求解算法进行设计，即问题求解算法进行设计，即“形式化、搜索、执行形式化、搜索、执行”问题的形式化问题的形式化：一个问题可以形式化地定义为四个组：一个问题可以形式化地定义为四个组成部分：成部分：初始状态初始状态；可能的可能的行动行动的描述。最常见的形式化是使用一个后继的描述。最常见的形式化是使用一个后继函数。给定一个特殊的状态函数。给定一个特殊的状态x，Successor(x)返回一个返回一个由有序对由有序对（行动，后继）组成行动，后继）组成的集合，其中每个行动都是状态的集合，其中每个行动都是状态x下的合法行动之一，下
3、的合法行动之一，每个后继都是行动后从状态每个后继都是行动后从状态x能够达到的状态。能够达到的状态。定义明确的问题及解定义明确的问题及解总之，初始状态和它的后继函数隐含的定义了问题的总之，初始状态和它的后继函数隐含的定义了问题的状态空间状态空间-即从初始状态可以达到的所有状态的集即从初始状态可以达到的所有状态的集合。状态空间形成一个图，其中节点是状态，节点之合。状态空间形成一个图，其中节点是状态，节点之间的弧就是行动，状态空间中的一条路径就是通过行间的弧就是行动，状态空间中的一条路径就是通过行动序列连接起来的一个状态序列。动序列连接起来的一个状态序列。目标测试目标测试，用来确定当前状态是不是目标
4、状态。，用来确定当前状态是不是目标状态。路径耗散函数路径耗散函数为每条路径分配一个数值化的耗散值。为每条路径分配一个数值化的耗散值。问题求解算法选择能反映它自己性能度量的耗散函数。问题求解算法选择能反映它自己性能度量的耗散函数。上述四个元素定义了一个问题，可以把它们集合在一上述四个元素定义了一个问题，可以把它们集合在一起成为一个单一的数据结构，作为问题求解算法的输起成为一个单一的数据结构，作为问题求解算法的输入。问题的解就是从初始状态到目标状态的路径。解入。问题的解就是从初始状态到目标状态的路径。解的优劣由路径耗散函数度量，而最优解是所有的解里的优劣由路径耗散函数度量，而最优解是所有的解里路径
5、耗散值最小的解。路径耗散值最小的解。前面用初始状态、后继函数、目标测前面用初始状态、后继函数、目标测试和路径耗散来表示问题，这种形式试和路径耗散来表示问题，这种形式化表示是合理的，不过它忽略了现实化表示是合理的，不过它忽略了现实世界的许多方面，去除表示中细节的世界的许多方面，去除表示中细节的过程被称为过程被称为抽象化抽象化，而去除表示中细，而去除表示中细节的描述称为节的描述称为问题形式化问题形式化。问题实例问题实例初始状态初始状态目标状态目标状态它包括一个它包括一个3X3的棋盘，棋盘上摆放着的棋盘，棋盘上摆放着8个写有数字个写有数字的棋子，留下一个空位。与空位相邻的棋子可以滑入的棋子，留下一个
6、空位。与空位相邻的棋子可以滑入到空位中。游戏的目的是要达到一个特定的目标状态。到空位中。游戏的目的是要达到一个特定的目标状态。7 2 4568 3 11 2356 7 847 2 4568 3 1724568 3 17 2 45 68 3 17 2 4568317 2 45 68 3 1初始状态初始状态行动描述行动描述1 2356 7 84目标测试和计算路径消耗目标测试和计算路径消耗搜索和执行搜索和执行 标准的形式化如下：标准的形式化如下： 状态状态；描述了指定；描述了指定8个棋子中的每一个以及空位在棋盘的个棋子中的每一个以及空位在棋盘的9个方格上的分布。个方格上的分布。 初始状态初始状态：任
7、何状态都可以指定为初始状态。注：任何状态都可以指定为初始状态。注意要到达任何一个给定的目标，可能的初始状态意要到达任何一个给定的目标，可能的初始状态中恰好只有一半可以作为初始状态。中恰好只有一半可以作为初始状态。 后继函数后继函数：用来产生通过四个行动（把空位向：用来产生通过四个行动（把空位向Left，right,Up或或Down)能够达到的合法状态。能够达到的合法状态。 目标测试目标测试：用来检测状态是否是目标状态。：用来检测状态是否是目标状态。 路径耗散路径耗散：设每一步的耗散值是：设每一步的耗散值是1因此整个路径的因此整个路径的耗散值是路径中的步数。耗散值是路径中的步数。 这里的抽象化只
8、保留了游戏规则相关的描述，而这里的抽象化只保留了游戏规则相关的描述，而忽略所有物理操作的细节。忽略所有物理操作的细节。八八数码游戏数码游戏属于滑快问题家族，这类问题经常被用作属于滑快问题家族，这类问题经常被用作AI中新的搜索算法的测试问题。这类一般问题已知为中新的搜索算法的测试问题。这类一般问题已知为NP完完全问题，因此对这类问题不要期望在最坏情况下找到好全问题，因此对这类问题不要期望在最坏情况下找到好于我们后面要讲述的算法。八数码游戏共有于我们后面要讲述的算法。八数码游戏共有9！/2=181440个可达到的状态，这是很容易求解的。个可达到的状态，这是很容易求解的。15数码数码问题则大约有问题
9、则大约有1.3万亿个状态，用最好的搜索算法最优化万亿个状态，用最好的搜索算法最优化地求解一个随机的实例需要几毫秒。地求解一个随机的实例需要几毫秒。24数码游戏则大约数码游戏则大约有有1025个状态，用目前的机器和最优化算法求解随机的个状态，用目前的机器和最优化算法求解随机的实例仍是相当困难的。实例仍是相当困难的。四皇后问题四皇后问题在一个在一个4 44 4的国际象棋棋盘上，一次一个地的国际象棋棋盘上，一次一个地摆布四枚皇后棋子，摆好后要满足每行、每列和对角线摆布四枚皇后棋子，摆好后要满足每行、每列和对角线上只允许出现一枚棋子，即棋子间不许相互俘获。如图上只允许出现一枚棋子，即棋子间不许相互俘获
10、。如图其中其中a a，b b满足目标条件，满足目标条件，c c，d d，e e为不合法状态，即不为不合法状态，即不可能构成满足目标条件的中间势态。可能构成满足目标条件的中间势态。四皇后问题的几个状态四皇后问题的几个状态尽管对于这个问题和整个尽管对于这个问题和整个n皇后问题家族存在有效的皇后问题家族存在有效的专用算法，这类问题对于搜索算法仍然是个有趣的专用算法，这类问题对于搜索算法仍然是个有趣的测试问题。形式化主要有两类：一类是增量形式化，测试问题。形式化主要有两类：一类是增量形式化，包括了增加状态描述的算符，从空状态开始：对于包括了增加状态描述的算符，从空状态开始：对于四皇后问题意味着每次行动
11、添加一个皇后到状态中四皇后问题意味着每次行动添加一个皇后到状态中去。另一类是完全状态形式化，去。另一类是完全状态形式化，4个皇后都在棋盘上个皇后都在棋盘上开始，然后移动它们。开始，然后移动它们。增量形式化如下：增量形式化如下：状态状态：把：把0到到4个皇后放棋盘上的任何安排都是一个状个皇后放棋盘上的任何安排都是一个状态。态。初始状态初始状态；棋盘上没有皇后。；棋盘上没有皇后。后继函数后继函数；把一个皇后添加到棋盘上的任何空格。；把一个皇后添加到棋盘上的任何空格。目标测试目标测试：4个皇后都在棋盘上，并且互相攻击不到。个皇后都在棋盘上，并且互相攻击不到。在这个形式化中，我们需要调查在这个形式化中
12、，我们需要调查16X15X14X13个可能个可能的序列。的序列。更好的形式化方法更好的形式化方法是禁止把一个皇后放到任何是禁止把一个皇后放到任何可能被攻击的格子里：可能被攻击的格子里：状态状态：摆放：摆放n个皇后个皇后(0 n 4)的安排，要求最左侧的安排，要求最左侧n列里列里每一列一个皇后，保证没有一个皇后能攻击另一个。每一列一个皇后，保证没有一个皇后能攻击另一个。后继函数后继函数：把一个皇后添加到最左侧空列的任何格子内，：把一个皇后添加到最左侧空列的任何格子内，只要该格子未被其他皇后攻击。这样的形式化把四皇后只要该格子未被其他皇后攻击。这样的形式化把四皇后问题的状态空间从问题的状态空间从4
13、万多降到万多降到3。如果是八皇后呢？如果是八皇后呢？在这个形式化中，需要调查在这个形式化中，需要调查64X63XX57 3X1014个状态个状态状态状态：摆放：摆放n个皇后个皇后(0 n 8)的安排，要求最左侧的安排，要求最左侧n列列里每一列一个皇后，保证没有一个皇后能攻击另一个。里每一列一个皇后，保证没有一个皇后能攻击另一个。后继函数后继函数：把一个皇后添加到最左侧空列的任何格子：把一个皇后添加到最左侧空列的任何格子内，只要该格子未被其他皇后攻击。这样的形式化把内，只要该格子未被其他皇后攻击。这样的形式化把四皇后问题的状态空间从四皇后问题的状态空间从3X1014降到降到2057，解就容，解就
14、容易找到了。对于易找到了。对于100个皇后，初始的形式化约有个皇后，初始的形式化约有10400个状态，而用个状态，而用改进的形式化方法改进的形式化方法约有约有1052个状态这是个状态这是一个相当大的缩减，但是仍然太大。我们以后将给出一个相当大的缩减，但是仍然太大。我们以后将给出一个简单算法，可以处理百万皇后问题。一个简单算法，可以处理百万皇后问题。现实世界问题现实世界问题我们已经看到寻径问题是如何根据特定的位置和沿它们之间我们已经看到寻径问题是如何根据特定的位置和沿它们之间的连接进行转移而定义的。寻径问题在实际中有许多应用。的连接进行转移而定义的。寻径问题在实际中有许多应用。诸如计算机网络的路
15、由、军事行动的规划、生产调度问题、诸如计算机网络的路由、军事行动的规划、生产调度问题、排课问题，以及飞机航线旅行规划系统等等。这些问题都是排课问题，以及飞机航线旅行规划系统等等。这些问题都是典型的描述起来复杂的问题。典型的描述起来复杂的问题。考虑一个考虑一个飞机航线旅行问题飞机航线旅行问题的简化例子，设定如下：的简化例子，设定如下：状态：每个状态由位置（例如机场）和当前的时间来表示。状态：每个状态由位置（例如机场）和当前的时间来表示。初始状态：由具体问题而定。初始状态：由具体问题而定。后继函数：返回的状态是下列因素的结果：乘坐的航班，起飞时刻距当后继函数：返回的状态是下列因素的结果：乘坐的航班
16、，起飞时刻距当前时刻的时间差加上从当前机场到另一个机场所需要的飞行时间。前时刻的时间差加上从当前机场到另一个机场所需要的飞行时间。目标测试：我们是否在某个预定的时刻到达目的地？目标测试：我们是否在某个预定的时刻到达目的地？路径耗散：取决于金钱的花费、等待的时间、飞行时间、过海关和入境路径耗散：取决于金钱的花费、等待的时间、飞行时间、过海关和入境的过程、座位的质量、一天中的哪个时间段、飞机类型、飞行常客的里的过程、座位的质量、一天中的哪个时间段、飞机类型、飞行常客的里程奖等。程奖等。商业旅行建议系统使用了这种问题形式化的方法，同时要考商业旅行建议系统使用了这种问题形式化的方法，同时要考虑很多附加
17、的复杂因素以应付航空公司强加的繁复的收费结虑很多附加的复杂因素以应付航空公司强加的繁复的收费结构。然而，任何经常作飞机的乘客都知道并不是所有的飞行构。然而，任何经常作飞机的乘客都知道并不是所有的飞行旅行都能够按计划顺利进行。好的系统应该包括应急计划。旅行都能够按计划顺利进行。好的系统应该包括应急计划。旅行问题与寻径问题有很近的关系，但是有很重要的不同。旅行问题与寻径问题有很近的关系，但是有很重要的不同。例如多个城市之间的旅行问题，从长春出发到其他例如多个城市之间的旅行问题，从长春出发到其他19个城市个城市中的每一个至少一次最后在回到出发地这样一个问题。如寻中的每一个至少一次最后在回到出发地这样
18、一个问题。如寻径一样，行动还是对应临近城市之间的旅行。然而，状态空径一样，行动还是对应临近城市之间的旅行。然而，状态空间就不一样了。每个状态不仅必须包括当前所在的位置，还间就不一样了。每个状态不仅必须包括当前所在的位置，还必须包括已经访问过的城市。因此初始状态可能是必须包括已经访问过的城市。因此初始状态可能是“in长长春春;visited长春长春，一个中间状态可能是，一个中间状态可能是”in上海；上海； visited长春，沈阳、上海长春，沈阳、上海“，而目标测试应该是检测是否，而目标测试应该是检测是否在长春并且已经访问过所有的在长春并且已经访问过所有的20个城市。其他实际问题个城市。其他实际
19、问题解的搜索解的搜索在对一些问题形式化之后，我们现在开始考虑在对一些问题形式化之后，我们现在开始考虑如何对它们求解，这是通过在状态空间中的搜如何对它们求解，这是通过在状态空间中的搜索完成的。下面讨论的搜索技术使用显式的搜索完成的。下面讨论的搜索技术使用显式的搜索树，搜索树是由初始状态和后继函数共同生索树，搜索树是由初始状态和后继函数共同生成的，同时也定义了状态空间。下图是一个简成的，同时也定义了状态空间。下图是一个简化的罗马尼亚道路图化的罗马尼亚道路图OradeaZerind7175AradTimisoara118111Lugol7075MehadiaDobreta151140Sibiu80R
20、imnicu120146Craiova99Fagaras97138Pitesti101211Giurgiu90Bucharest85Neamt87lasi92Vastui142Urziceni98Hirsova86Eforic一个简化的罗马尼亚道路图下图显示了为寻找从下图显示了为寻找从Arad到到Bucharest的路径对搜索树进行的某些扩展的路径对搜索树进行的某些扩展AradSibiutimisoaraZerindAradFagarasOradeaRimnicuAradLugolAradOradea初始状态初始状态AradSibiutimisoaraZerindAradFagarasOrad
21、eaRimnicuAradLugolAradOradea扩展扩展Arad之后之后AradSibiutimisoaraZerindAradFagarasOradeaRimnicuAradLugolAradOradea扩展扩展Sibiu之后之后非形式化算法非形式化算法Tree-Search1.根据问题初始状态初始化搜索树；根据问题初始状态初始化搜索树；2.While(不满足结束条件时不满足结束条件时)2.1 If(没有可扩展的结点没有可扩展的结点)返回失败信息；返回失败信息； 2.2 根据某种策略选择一个可扩展叶子结点；根据某种策略选择一个可扩展叶子结点； 2.3 If（当前结点满足目标状态）返回
22、解的信当前结点满足目标状态）返回解的信息；息；Else将该结点（可扩展结点）加入到搜索将该结点（可扩展结点）加入到搜索树中；树中；该算法如何进行优化？该算法如何进行优化？搜索树中节点的表示有多种方式，不过我们可以假设节点是一个包含五个要素的数据结构：状态：状态空间中与该方法相对应的格局；父节点：搜索树中生成该节点的节点；行动：由父节点产生该节点所采取的操作；路径耗散（成本）：从初始状态到该节点的路径耗散，一般记为g(n)，路径有父指针表示；深度：从根节点到该节点所经路径上的步数。节点与状态的区别？节点与状态的区别？7 2 45 68 3 1父节点父节点节点节点状态状态行动行动=Right深度深
23、度=3路径耗散路径耗散=3节点产生构造搜索树的数据结构，节点产生构造搜索树的数据结构，每个节点都具有父节点，状态和各每个节点都具有父节点，状态和各种记录域，图中箭头是由子节点指种记录域，图中箭头是由子节点指向父节点的指针。向父节点的指针。度量问题求解的性能度量问题求解的性能完备性完备性：当问题有解时，这个算法是否能保证：当问题有解时，这个算法是否能保证找到一个解？找到一个解？空间复杂度空间复杂度：执行搜索的过程中需要多少内存？：执行搜索的过程中需要多少内存？时间复杂度时间复杂度：找到一个解需要花费多少长时间？：找到一个解需要花费多少长时间？最优性最优性：该搜索策略是否能找到最优解？：该搜索策略
24、是否能找到最优解？时间和空间的复杂性度量往往要与问题难度的某种时间和空间的复杂性度量往往要与问题难度的某种度量一起考虑，在理论计算机科学中，一个典型的度量一起考虑，在理论计算机科学中，一个典型的度量是状态空间的大小。因为状态空间图被视为要度量是状态空间的大小。因为状态空间图被视为要输入到搜索程序的显示数据结构。在输入到搜索程序的显示数据结构。在AI 中，状态中，状态空间图是由初始状态和后继函数隐含地表示的，经空间图是由初始状态和后继函数隐含地表示的，经常是无限的，它的复杂度根据下列三个值来表达：常是无限的，它的复杂度根据下列三个值来表达：B，分支因子；分支因子；d，最浅的目标节点的深度；最浅的
25、目标节点的深度；m，状状态空间中任何路径的最大长度。态空间中任何路径的最大长度。时间复杂度一般根据搜索过程中产生的节点数目来时间复杂度一般根据搜索过程中产生的节点数目来度量，而空间复杂度则根据在内存中存储的最大节度量，而空间复杂度则根据在内存中存储的最大节点个数来度量。点个数来度量。无信息搜索 无信息搜索算法是经典计算机科学无信息搜索算法是经典计算机科学(Horowitz和和Sahni,1978)和运筹学（和运筹学（Dreyfus,1969)的一个中心的一个中心话题，话题，1988年年Gallo和和Pallottino给出了相关问题的给出了相关问题的综述文章。综述文章。 搜索问题搜索问题 回溯
26、策略回溯策略 图搜索策略图搜索策略 无信息图搜索：广度优先、代价一致搜索、深度无信息图搜索：广度优先、代价一致搜索、深度优先、深度有限搜索、迭代深入深度优先搜索、优先、深度有限搜索、迭代深入深度优先搜索、双向搜索、无信息搜索策略的比较、避免重复状双向搜索、无信息搜索策略的比较、避免重复状态。态。 人类的思维过程，可以看作是一个搜索的过人类的思维过程，可以看作是一个搜索的过程。从小学到现在，你也许遇到过很多种智程。从小学到现在，你也许遇到过很多种智力游戏问题，比如说传教士和野人问题：有力游戏问题，比如说传教士和野人问题：有3个传教士和个传教士和3个野人来到河边准备过河，河岸个野人来到河边准备过河
27、，河岸有一条船，每次至多可供有一条船，每次至多可供2人乘坐。问传教士人乘坐。问传教士为安全起见，应如何规划摆渡方案，使得任为安全起见，应如何规划摆渡方案，使得任何时候，在船上与河的两岸野人数目总是不何时候，在船上与河的两岸野人数目总是不超过传教士数目（但允许在河的某一侧只有超过传教士数目（但允许在河的某一侧只有野人而没有传教士）？如果要做这个智力游野人而没有传教士）？如果要做这个智力游戏，在每一次渡河之后，都会有几种渡河方戏，在每一次渡河之后，都会有几种渡河方案供你选择，究竟哪种方案才有利于在满足案供你选择，究竟哪种方案才有利于在满足题目所规定的约束条件下顺利过河呢？这就题目所规定的约束条件下
28、顺利过河呢？这就是搜索问题。是搜索问题。搜索问题搜索问题 经过反复努力和试探，你终于找到了一经过反复努力和试探，你终于找到了一种解决方法。在你高兴之余，你可能马种解决方法。在你高兴之余，你可能马上会想到，这个办法所用的步骤是否最上会想到，这个办法所用的步骤是否最少？也就是说，它是最优的吗？如果不少？也就是说，它是最优的吗？如果不是，如何才能找到最优的办法？你是学是，如何才能找到最优的办法？你是学过计算机程序设计的学生，你考虑过在过计算机程序设计的学生，你考虑过在计算机上又如何实现这样的搜索？这些计算机上又如何实现这样的搜索？这些问题就是我们要学习的内容。问题就是我们要学习的内容。 一般而言，很
29、多问题求解过程可以转化为状态空一般而言，很多问题求解过程可以转化为状态空间的搜索问题。比如，前面讲过的传教士与野人间的搜索问题。比如，前面讲过的传教士与野人问题，当用在河左岸的传教士人数、野人人数和问题，当用在河左岸的传教士人数、野人人数和船的情况表示问题时，该问题的初始状态可以用船的情况表示问题时，该问题的初始状态可以用三元组表示为（三元组表示为（3，3，1），结束状态可以表示），结束状态可以表示为（为（0，0，0），而中间状态可以表示为（），而中间状态可以表示为（2，2，0）、（）、（3，2，1）、（）、（3，0，0）等，每个三等，每个三元组对应了三维空间上的一个点。而问题的解，元组对应了
30、三维空间上的一个点。而问题的解，则是一个合法状态的序列，其中序列的第一个状则是一个合法状态的序列，其中序列的第一个状态是问题的初始状态，而最后一个状态则是问题态是问题的初始状态，而最后一个状态则是问题的结束状态，介于它们之间的是中间状态。除了的结束状态，介于它们之间的是中间状态。除了第一个状态外，该序列中任何状态都可以通过一第一个状态外，该序列中任何状态都可以通过一条规则由与它相邻的前一个状态转换得到。下页条规则由与它相邻的前一个状态转换得到。下页的图给出了一个搜索问题的示意图。含义是如何的图给出了一个搜索问题的示意图。含义是如何在一个比较大的问题空间中，只通过搜索比较小在一个比较大的问题空间
31、中，只通过搜索比较小的范围，就找到问题的解。寻找这样的序列过程的范围，就找到问题的解。寻找这样的序列过程称为称为搜索搜索。搜索方法从搜索方式上来讲，搜索可以划分为两大类，即盲目搜索从搜索方式上来讲，搜索可以划分为两大类，即盲目搜索和启发式搜索。和启发式搜索。所谓盲目搜索，就是未利用问题的知识，采用固定的所谓盲目搜索，就是未利用问题的知识，采用固定的方式生成状态的方法。显然这种方法的搜索效率是低下的，方式生成状态的方法。显然这种方法的搜索效率是低下的，但方法具有通用性。当一时难以找到求解问题的有效知识但方法具有通用性。当一时难以找到求解问题的有效知识时，是一种不得不采用的方法。时，是一种不得不采
32、用的方法。所谓启发式搜索，与盲目搜索正好相反，它利用问题所谓启发式搜索，与盲目搜索正好相反，它利用问题的知识，缩小问题的搜索范围，选择那些最有可能在（最的知识，缩小问题的搜索范围，选择那些最有可能在（最优）解路径上的状态优先搜索，以尽快地找到问题的（最优）解路径上的状态优先搜索，以尽快地找到问题的（最优）解。由于利用了问题的有关知识，一般来说，搜索效优）解。由于利用了问题的有关知识，一般来说，搜索效率会有所提高。但如何找到对求解问题有帮助的知识，以率会有所提高。但如何找到对求解问题有帮助的知识，以及如何利用这些知识，是问题的关键所在。及如何利用这些知识，是问题的关键所在。到目前为止，在人工智能
33、领域中已提出许多具体的搜索方法，概括起来到目前为止，在人工智能领域中已提出许多具体的搜索方法，概括起来有：有：（1）求任一解路的搜索策略）求任一解路的搜索策略回溯法（回溯法（Backtracking）爬山法（爬山法（Hill Climbing）宽度优先法（宽度优先法（Breadth-first）深度优先法（深度优先法（Depth-first）限定范围搜索法（限定范围搜索法（Beam Search） 好的优先法（好的优先法（Best-first）（2）求最佳解路的搜索策略求最佳解路的搜索策略大英博物馆法（大英博物馆法（British Museum）分枝界限法（分枝界限法（Branch and B
34、ound）动态规划法（动态规划法（Dynamic Programming）最佳图搜索法（最佳图搜索法（A）（3）求与或关系解图的搜索法求与或关系解图的搜索法一般与或图搜索法（一般与或图搜索法（AO）极小极大法（极小极大法（Minimax）剪枝法（剪枝法（Alpha-beta Pruning）启发式剪枝法（启发式剪枝法（Heuristic Pruning）今后对其中几个基本搜索策略作进一步的讨论。今后对其中几个基本搜索策略作进一步的讨论。 无信息的搜索策略这部分无信息搜索（也称为盲目搜索）主要包括广度优先搜这部分无信息搜索（也称为盲目搜索）主要包括广度优先搜索、代价一致搜索、深度优先搜索、深度有
35、限搜索和迭代深索、代价一致搜索、深度优先搜索、深度有限搜索和迭代深度优先搜索和双向搜索几种。以下我们分别进行讲述和对度优先搜索和双向搜索几种。以下我们分别进行讲述和对比比 。广度优先搜索广度优先搜索：它是一种简单的搜索策略，首先扩展根节点，：它是一种简单的搜索策略，首先扩展根节点，接下来扩展根节点的所有后继，然后再扩展它们的后继，依接下来扩展根节点的所有后继，然后再扩展它们的后继，依此类推。一般来讲，在下一层的任何节点扩展之前搜索树上此类推。一般来讲，在下一层的任何节点扩展之前搜索树上当前层的所有节点都已经扩展完。当前层的所有节点都已经扩展完。1959年年Moore最早使用广最早使用广度优先搜
36、索形式化并解决迷宫问题。度优先搜索形式化并解决迷宫问题。广度优先搜索广度优先搜索可以调用函数可以调用函数TREE-SEARCH来实现，该函来实现，该函数以一个空的数以一个空的边缘边缘为参数，而边缘是一个先进先出为参数，而边缘是一个先进先出(FIFO)队队列，保证先访问的节点先扩展。这意味着浅层的节点会在深列，保证先访问的节点先扩展。这意味着浅层的节点会在深层节点之前被扩展。层节点之前被扩展。一个简单二叉树的搜索过程一个简单二叉树的搜索过程ABFCGEDABFCGEDABFCGEDABFCGED在每一个阶段，下一个要扩展的节点由箭头指示在每一个阶段，下一个要扩展的节点由箭头指示出来。出来。广度优
37、先搜索算法的评价广度优先搜索算法的评价从完备性和最优性来看从完备性和最优性来看我们很容易知道广度优先搜索是完备的如果最浅的目标节点处于一个有限的深度d，广度优先搜索在扩展完比它浅的所有节点（假设分支因子b是有限的）后最终能找到这个目标节点。但最浅的目标不一定是最优的目标节点：从技术上讲，如果路径耗散是节点深度的非递减函数，广度优先算法才是最优的。从时间和空间复杂性来看从时间和空间复杂性来看我们考虑一个假想的状态空间，状态空间中每个状态都我们考虑一个假想的状态空间，状态空间中每个状态都有有b个后继。这样搜索树的根节点生成第一层的个后继。这样搜索树的根节点生成第一层的b个子节个子节点，每个子节点又
38、生成点，每个子节点又生成b个子节点，在第二层共有个子节点，在第二层共有b2个节个节点，这些节点中的每一个又生成点，这些节点中的每一个又生成b个子节点，如此类推，个子节点，如此类推，假设解的深度为假设解的深度为d，在最坏情况下，我们将扩展在最坏情况下，我们将扩展d层除了层除了最后一个节点外的所有节点（因为目标节点本身尚未被最后一个节点外的所有节点（因为目标节点本身尚未被扩展），那么在扩展），那么在d+1层会产生层会产生bd+1-b个节点，个节点， 这时已经生成的节点数是多少？这时已经生成的节点数是多少？b+b2+b3+bd+(bd+1-b)=O(bd+1)每个生成的节点都必须保存在内存中，因为它
39、既是边缘节点的一部分又是边缘节点的祖先，因此该算法的时间复杂度和空间复杂度相等（再加上一个根节点）。广度优先搜索时间与空间复杂度分析广度优先搜索时间与空间复杂度分析深度深度 节点数节点数 时间数时间数 内存内存 2 1100 0. 11秒秒 1Mbit下图是分支因子下图是分支因子b=10的时候广度优先搜索到不同的时候广度优先搜索到不同的解深度的解深度d所需要的时间和空间开销，并假定每秒所需要的时间和空间开销，并假定每秒生成生成10000个节点，并且存储一个节点需要个节点，并且存储一个节点需要1k字节。字节。 4 111,100 11秒秒 106M 6 107 19分钟分钟 10G 8 109
40、31小时小时 1T(KG) 10 1011 129天天 101T 12 1013 35年年 10P(KT) 14 1015 3523年年 1E(KP)从上图我们可以得到两个结论：从上图我们可以得到两个结论：第一个结论，在广度优先搜索算法第一个结论，在广度优先搜索算法中内存的需求是比执行时间消耗更中内存的需求是比执行时间消耗更大的问题。大的问题。第二个结论，时间需求仍是个主要第二个结论，时间需求仍是个主要因素。因素。一般来讲，除最小的实例外指数级一般来讲，除最小的实例外指数级复杂度的搜索问题不能用无信息的复杂度的搜索问题不能用无信息的方法解决。方法解决。代价一致搜索代价一致搜索当所有单步消耗相等
41、时，广度优先搜索是最优的，因为它们总是扩展深度最浅的未扩展节点。但代价一致搜索扩展的是路径消耗最低的节点n。 在什么条件下广度优先搜索与代价一致搜索相 同？代价一致搜索时对一条路径的步数并不关心，而只是关心所经步骤总的耗散。因此若扩展到一个具有能返回同一状态的零耗散行动的节点时会陷入无限循环，造成不完备性。若每一步的耗散都大于等于某个最小的正常数时，能够保证其完备性与最优性。沿着路径的耗散总是增加的，因此第一个被扩展的目标节点就是最优解（记住，算法只对被选中扩展的节点进行目标测试）。代价一致算法的度量代价一致搜索由路径的耗散引导而不是深度，因此它的复杂度不能简单地使用b和d来刻画。我们使用C*
42、表示最优解的耗散值，并且假定每个行动的耗散至少为。那么算法的时间和空间复杂度为 ，要比bd大得多。 为什么？什么条件下一广度优先算法复杂度一样？我们学过代价一致的搜索吗？)(/*CbO深度优先搜索深度优先搜索深度优先搜索总是扩展搜索树的当前边缘中最深的节点，搜索直接推进到搜索树的最深层，那里的节点没有后继节点。当那些节点被扩展完之后，它们被从边缘中去掉，然后搜索算法“向上回到”下一个还有未扩展后继节点的稍浅的节点。 在搜索算法Tree-Search中采用什么策略能够使搜索过程按照深度优先进行？ABFCGEDHIJ K L M N OABFCGEDHIJ K L M N OOABFCGEDHIJ
43、 K L M NABFCGEDHIJ K L M N OABFCGEDHIJ K L M N OABFCGEDHIJ K L M N OABFCGEDHIJ K L M N OABFCGEDHIJ K L M N OABFCGEDH IJ K L M N OABFCGEDHIJ K L M N OABFCGEDHIJ K L M N OABFCGEDHIJ K L M N O深度优先搜索对内存的需求很少，它只需要存储一条从根节点到叶节点的路径，以及该路径上每个节点的所有未被扩展的兄弟节点即可。一旦一个节点被扩展，当它的所有后代都被扩展和这个节点从内存中删除。因此，对上面的搜索图，若分支因子为b
44、，最大深度为m的状态空间，深度优先搜索只需要存储bm+1个节点。与广度优先相同假设下，并且假设与目标节点在同一深度的节点没有后继节点，我们看到在深度d=12时深度优先搜索只需要118k字节而不是10P 字节，节省了大约百亿倍的空间。深度优先搜索的缺点是它有可能错误地选择一条分支并且沿着一条很长（甚至是无限的）路径一直走下去，而如果做出不同的选择则可能引导对树根节点附近的解进行搜索。1初始化。取图中任意结点s(G=s)作为初始结点将其赋值到OPEN表，CLOSED表置空。2循环执行以下语句直至找到解或OPEN表为空2.1n=first(OPEN);2.2 IF GOAL(n) return(SU
45、CCESS)；算法结束；2.3 REMOVE(n,OPEN)，ADD(n,CLOSE);2.4 EXPAND(n)-mi; G=ADD(mi,G);2.5 ADD(mj,OPEN),并标记mj到n的指针；把不在OPEN或CLOSE中的结点放在OPEN表的最前面，使浓度大的结点可优先扩展。深度优先搜索算法的框架深度优先搜索算法的框架深度有限搜索深度有限搜索前面我们看到，深度优先搜索虽然占用的内存比较小，但这种算法不是完备的也不是最优的。为此，我们可以通过对深度优先搜索提供一个预先设定的的深度限制l 来解决，就是说深度为l的节点被当作没有后继的节点对待，这种办法称为深度有限搜索。对深度限制解决了无
46、穷路径问题。但问题是如果我们选择的ld的话，搜索也不是最优的，深度优先可以看作深度有限的一种特殊情况。那么如何来优化这种方法呢？深度有限搜索可以通过对一般的树搜索算法或者递归深度优先搜索算法进行简单的修改来实现。即对深度限制l不断进行迭代更新。迭代深入搜索迭代深入搜索迭代深入搜索（或迭代深入深度优先搜索）是一个用来寻找最合适的深度限制的通用策略，它经常与深度优先搜索结合使用。做法是不断地增大深度限制-首先为0，接着为1，然后是2，依此类推-直到找到目标节点。但深度限制达到d，即最浅的目标节点的深度时，就找到目标节点，下面的图给出了算法的搜索过程，该算法结合了深度优先和广度优先搜索的优点，它的空
47、间和深度优先搜索需求一样小，为O(bd)。它和广度优先搜索一样当分支因子有限时是完备的，当路径耗散是节点深度的非递减函数时是最优的。AL=0AABCL=1ABCABCABCABFCGEDL=2ABFCGEDABFCGEDABFCGEDABFCGEDABFCGEDABFCGEDABFCGEDABFCGEDHIJ K L M N OL=3ABFCGEDHIJ K L M N OABFCGEDHIJ K L M N OABFCGEDIJ K L M N OHABFCGEDJ K L M N OHIIABFCGEDJ K L M N OHIABFCGEDK L M N OHJIABFCGEDK L M
48、 N OHJIABFCGEDK L M N OHJIABFCGEDK L M N OHJIABFCGEDK L M N OHJIABFCGEDK L M N OHJ迭代深入搜索也许看起来比较浪费，因为有些状态被多次生成。但实际上代价不是很大。原因在于一棵每层的分支因子都相同（或相近）的搜索树中，底层节点（深度d)只被生成一次，倒数第二层的节点生成两次。依此类推，一直到根节点的子节点，它被生成d次。因此生成的总节点数为 (d+1)b0+db+(d-1)b2+2bd-1+bd，时间复杂度是O(bd)。与广度优先生成的节点数相比，它没有生成d+1层的节点而广度优先可能会生成一些d+1层的节点，因此它
49、比广度优先搜索要快。比如b=10,d=5，迭代深入搜索生成50+400+3000+20000+100000=123450个节点，而广度优先搜索生成10+100+1000+10000+100000+999990=1111110个节点。迭代深入搜索的性质迭代深入搜索的性质n完备吗? 是n时间复杂性? (d+1)b0 + d b1 + (d-1)b2 + + bd = O(bd)n空间复杂性? O(bd)n最优性? 是, if step cost = 1双向搜索双向搜索双向搜索的思想是同时进行两个方向的搜索，一个从初始状态向目标状态进行，另一个从目标状态向初始状态搜，动机的产生的节点是bd/2+bd
50、/2要比bd小得多，即两个小圆的面积之和比起点为中心达到目标的大圆面积大得多。双向搜索最吸引人的地方是时间复杂度的降低，但实际上如何从目标向初始状态搜并不容易。几种算法的比较几种算法的比较标准 广度优先 代价一致 深度优先 深度限制 迭代深入完备性完备性 是 是 否 否 是时间时间 O(bd+1) O(bC*/) O(bm) O(bl) O(bd)空间空间 O(bd+1) O(bC*/) O(bm) O(bl) O(bd)最优性最优性 是 是 否 否 是回溯策略回溯策略回溯策略回溯策略属于盲目搜索的一种。所谓回溯策略，简单地说是这样一种策略：首先将规则给出一个固定的排序，在搜索时，对当前状态（
