人工智能ppt课件搜索问题

第一部分问题求解用搜索法对问题求解问题求解算法描述：问题实例：玩具世界与现实世界问题搜索求解性能的度量*无信息的搜索策略*有信息的搜索和探索*对抗搜索（与或图搜索）高级搜索第一部分问题求解用搜索法对问题求解1

第二部分知识表示与推理谓词逻辑与归结原理

命题逻辑谓词逻辑*归结原理

Herbrand定理知识表示

知识概述*产生式表示语义网络表示框架表示其他表示方法

第二部分知识表示与推理谓词逻辑与归结原理2第三部分人工智能高级专题基于模型的诊断配置问题智能规划调度第三部分人工智能高级专题基于模型的诊断3搜索算法把问题作为输入，并以行动序列的形式返回问题的解。一旦找到一个解，那么它所建议的行动就可以付诸实施，这被称为执行阶段。因而我们可以对问题求解算法进行设计，即“形式化、搜索、执行”问题的形式化：一个问题可以形式化地定义为四个组成部分：初始状态；可能的行动的描述。最常见的形式化是使用一个后继函数。给定一个特殊的状态x，Successor(x)返回一个由有序对<action,successor>（〈行动，后继〉）组成的集合，其中每个行动都是状态x下的合法行动之一，每个后继都是行动后从状态x能够达到的状态。定义明确的问题及解搜索算法把问题作为输入，并以行动序列的形式返回问题的解。一旦4总之，初始状态和它的后继函数隐含的定义了问题的状态空间----即从初始状态可以达到的所有状态的集合。状态空间形成一个图，其中节点是状态，节点之间的弧就是行动，状态空间中的一条路径就是通过行动序列连接起来的一个状态序列。目标测试，用来确定当前状态是不是目标状态。路径耗散函数为每条路径分配一个数值化的耗散值。问题求解算法选择能反映它自己性能度量的耗散函数。上述四个元素定义了一个问题，可以把它们集合在一起成为一个单一的数据结构，作为问题求解算法的输入。问题的解就是从初始状态到目标状态的路径。解的优劣由路径耗散函数度量，而最优解是所有的解里路径耗散值最小的解。总之，初始状态和它的后继函数隐含的定义了问题的状态空间---5前面用初始状态、后继函数、目标测试和路径耗散来表示问题，这种形式化表示是合理的，不过它忽略了现实世界的许多方面，去除表示中细节的过程被称为抽象化，而去除表示中细节的描述称为问题形式化。前面用初始状态、后继函数、目标测试和路径耗散来表示问题，这种6问题实例玩具世界与现实世界问题我们首先来看一个八数码游戏初始状态目标状态它包括一个3X3的棋盘，棋盘上摆放着8个写有数字的棋子，留下一个空位。与空位相邻的棋子可以滑入到空位中。游戏的目的是要达到一个特定的目标状态。7245683112356784问题实例玩具世界与现实世界问题初始状态目标状态它包括一个3X77245683172456831724568317245683172456831初始状态行动描述12356784目标测试和计算路径消耗搜索和执行7245683172456831724568317245688标准的形式化如下：状态；描述了指定8个棋子中的每一个以及空位在棋盘的9个方格上的分布。初始状态：任何状态都可以指定为初始状态。注意要到达任何一个给定的目标，可能的初始状态中恰好只有一半可以作为初始状态。后继函数：用来产生通过四个行动（把空位向Left，right,Up或Down)能够达到的合法状态。目标测试：用来检测状态是否是目标状态。路径耗散：设每一步的耗散值是1因此整个路径的耗散值是路径中的步数。这里的抽象化只保留了游戏规则相关的描述，而忽略所有物理操作的细节。标准的形式化如下：9八数码游戏属于滑快问题家族，这类问题经常被用作AI中新的搜索算法的测试问题。这类一般问题已知为NP完全问题，因此对这类问题不要期望在最坏情况下找到好于我们后面要讲述的算法。八数码游戏共有9！/2=181440个可达到的状态，这是很容易求解的。15数码问题则大约有1.3万亿个状态，用最好的搜索算法最优化地求解一个随机的实例需要几毫秒。24数码游戏则大约有1025个状态，用目前的机器和最优化算法求解随机的实例仍是相当困难的。四皇后问题在一个4×4的国际象棋棋盘上，一次一个地摆布四枚皇后棋子，摆好后要满足每行、每列和对角线上只允许出现一枚棋子，即棋子间不许相互俘获。如图其中a，b满足目标条件，c，d，e为不合法状态，即不可能构成满足目标条件的中间势态。八数码游戏属于滑快问题家族，这类问题经常被用作AI中新的搜索10四皇后问题的几个状态尽管对于这个问题和整个n皇后问题家族存在有效的专用算法，这类问题对于搜索算法仍然是个有趣的测试问题。形式化主要有两类：一类是增量形式化，包括了增加状态描述的算符，从空状态开始：对于四皇后问题意味着每次行动添加一个皇后到状态中去。另一类是完全状态形式化，4个皇后都在棋盘上开始，然后移动它们。四皇后问题的几个状态尽管对于这个问题和整个n皇后问题家族存在11增量形式化如下：状态：把0到4个皇后放棋盘上的任何安排都是一个状态。初始状态；棋盘上没有皇后。后继函数；把一个皇后添加到棋盘上的任何空格。目标测试：4个皇后都在棋盘上，并且互相攻击不到。在这个形式化中，我们需要调查16X15X14X13个可能的序列。更好的形式化方法是禁止把一个皇后放到任何可能被攻击的格子里：状态：摆放n个皇后(0n4)的安排，要求最左侧n列里每一列一个皇后，保证没有一个皇后能攻击另一个。后继函数：把一个皇后添加到最左侧空列的任何格子内，只要该格子未被其他皇后攻击。这样的形式化把四皇后问题的状态空间从4万多降到3。增量形式化如下：12如果是八皇后呢？在这个形式化中，需要调查64X63X…X573X1014个状态状态：摆放n个皇后(0n8)的安排，要求最左侧n列里每一列一个皇后，保证没有一个皇后能攻击另一个。后继函数：把一个皇后添加到最左侧空列的任何格子内，只要该格子未被其他皇后攻击。这样的形式化把四皇后问题的状态空间从3X1014降到2057，解就容易找到了。对于100个皇后，初始的形式化约有10400个状态，而用改进的形式化方法约有1052个状态这是一个相当大的缩减，但是仍然太大。我们以后将给出一个简单算法，可以处理百万皇后问题。如果是八皇后呢？13现实世界问题我们已经看到寻径问题是如何根据特定的位置和沿它们之间的连接进行转移而定义的。寻径问题在实际中有许多应用。诸如计算机网络的路由、军事行动的规划、生产调度问题、排课问题，以及飞机航线旅行规划系统等等。这些问题都是典型的描述起来复杂的问题。考虑一个飞机航线旅行问题的简化例子，设定如下：状态：每个状态由位置（例如机场）和当前的时间来表示。初始状态：由具体问题而定。后继函数：返回的状态是下列因素的结果：乘坐的航班，起飞时刻距当前时刻的时间差加上从当前机场到另一个机场所需要的飞行时间。目标测试：我们是否在某个预定的时刻到达目的地？路径耗散：取决于金钱的花费、等待的时间、飞行时间、过海关和入境的过程、座位的质量、一天中的哪个时间段、飞机类型、飞行常客的里程奖等。现实世界问题我们已经看到寻径问题是如何根据特定的位置和沿它们14商业旅行建议系统使用了这种问题形式化的方法，同时要考虑很多附加的复杂因素以应付航空公司强加的繁复的收费结构。然而，任何经常作飞机的乘客都知道并不是所有的飞行旅行都能够按计划顺利进行。好的系统应该包括应急计划。旅行问题与寻径问题有很近的关系，但是有很重要的不同。例如多个城市之间的旅行问题，从长春出发到其他19个城市中的每一个至少一次最后在回到出发地这样一个问题。如寻径一样，行动还是对应临近城市之间的旅行。然而，状态空间就不一样了。每个状态不仅必须包括当前所在的位置，还必须包括已经访问过的城市。因此初始状态可能是“in长春;visited{长春}，一个中间状态可能是”in上海；visited{长春，沈阳、上海}“，而目标测试应该是检测是否在长春并且已经访问过所有的20个城市。其他实际问题商业旅行建议系统使用了这种问题形式化的方法，同时要考虑很多附15解的搜索在对一些问题形式化之后，我们现在开始考虑如何对它们求解，这是通过在状态空间中的搜索完成的。下面讨论的搜索技术使用显式的搜索树，搜索树是由初始状态和后继函数共同生成的，同时也定义了状态空间。下图是一个简化的罗马尼亚道路图解的搜索在对一些问题形式化之后，我们现在开始考虑如何对它们求16OradeaZerind7175AradTimisoara118111Lugol7075MehadiaDobreta151140Sibiu80Rimnicu120146Craiova99Fagaras97138Pitesti101211Giurgiu90Bucharest85Neamt87lasi92Vastui142Urziceni98Hirsova86Eforic一个简化的罗马尼亚道路图OradeaZerind7175AradTimisoara117下图显示了为寻找从Arad到Bucharest的路径对搜索树进行的某些扩展AradSibiutimisoaraZerindAradFagarasOradeaRimnicuAradLugolAradOradea初始状态下图显示了为寻找从Arad到Bucharest的路径对搜索树18AradSibiutimisoaraZerindAradFagarasOradeaRimnicuAradLugolAradOradea扩展Arad之后AradSibiutimisoaraZerindAradFa19AradSibiutimisoaraZerindAradFagarasOradeaRimnicuAradLugolAradOradea扩展Sibiu之后AradSibiutimisoaraZerindAradFa20非形式化算法Tree-Search1.根据问题初始状态初始化搜索树；2.While(不满足结束条件时){2.1If(没有可扩展的结点)返回失败信息；2.2根据某种策略选择一个可扩展叶子结点；2.3If（当前结点满足目标状态）返回解的信息；Else将该结点（可扩展结点）加入到搜索树中；｝该算法如何进行优化？非形式化算法Tree-Search1.根据问题初始状态初始化21搜索树中节点的表示有多种方式，不过我们可以假设节点是一个包含五个要素的数据结构：状态：状态空间中与该方法相对应的格局；父节点：搜索树中生成该节点的节点；行动：由父节点产生该节点所采取的操作；路径耗散（成本）：从初始状态到该节点的路径耗散，一般记为g(n)，路径有父指针表示；深度：从根节点到该节点所经路径上的步数。节点与状态的区别？搜索树中节点的表示有多种方式，不过我们可以假设节点是一个包含2272456831父节点节点状态行动=Right深度=3路径耗散=3节点产生构造搜索树的数据结构，每个节点都具有父节点，状态和各种记录域，图中箭头是由子节点指向父节点的指针。72456831父节点节点状态行动=Right深度=3路径耗23度量问题求解的性能完备性：当问题有解时，这个算法是否能保证找到一个解？空间复杂度：执行搜索的过程中需要多少内存？时间复杂度：找到一个解需要花费多少长时间？最优性：该搜索策略是否能找到最优解？度量问题求解的性能完备性：当问题有解时，这个算法是否能保证找24时间和空间的复杂性度量往往要与问题难度的某种度量一起考虑，在理论计算机科学中，一个典型的度量是状态空间的大小。因为状态空间图被视为要输入到搜索程序的显示数据结构。在AI中，状态空间图是由初始状态和后继函数隐含地表示的，经常是无限的，它的复杂度根据下列三个值来表达：B，分支因子；d，最浅的目标节点的深度；m，状态空间中任何路径的最大长度。时间复杂度一般根据搜索过程中产生的节点数目来度量，而空间复杂度则根据在内存中存储的最大节点个数来度量。时间和空间的复杂性度量往往要与问题难度的某种度量一起考虑，在25无信息搜索无信息搜索算法是经典计算机科学(Horowitz和Sahni,1978)和运筹学（Dreyfus,1969)的一个中心话题，1988年Gallo和Pallottino给出了相关问题的综述文章。搜索问题回溯策略图搜索策略无信息图搜索：广度优先、代价一致搜索、深度优先、深度有限搜索、迭代深入深度优先搜索、双向搜索、无信息搜索策略的比较、避免重复状态。无信息搜索无信息搜索算法是经典计算机科学(Horowitz和26人类的思维过程，可以看作是一个搜索的过程。从小学到现在，你也许遇到过很多种智力游戏问题，比如说传教士和野人问题：有3个传教士和3个野人来到河边准备过河，河岸有一条船，每次至多可供2人乘坐。问传教士为安全起见，应如何规划摆渡方案，使得任何时候，在船上与河的两岸野人数目总是不超过传教士数目（但允许在河的某一侧只有野人而没有传教士）？如果要做这个智力游戏，在每一次渡河之后，都会有几种渡河方案供你选择，究竟哪种方案才有利于在满足题目所规定的约束条件下顺利过河呢？这就是搜索问题。搜索问题人类的思维过程，可以看作是一个搜索的过程。从小学到现在，27经过反复努力和试探，你终于找到了一种解决方法。在你高兴之余，你可能马上会想到，这个办法所用的步骤是否最少？也就是说，它是最优的吗？如果不是，如何才能找到最优的办法？你是学过计算机程序设计的学生，你考虑过在计算机上又如何实现这样的搜索？这些问题就是我们要学习的内容。经过反复努力和试探，你终于找到了一种解决方法。在你高兴28一般而言，很多问题求解过程可以转化为状态空间的搜索问题。比如，前面讲过的传教士与野人问题，当用在河左岸的传教士人数、野人人数和船的情况表示问题时，该问题的初始状态可以用三元组表示为（3，3，1），结束状态可以表示为（0，0，0），而中间状态可以表示为（2，2，0）、（3，2，1）、（3，0，0）…等，每个三元组对应了三维空间上的一个点。而问题的解，则是一个合法状态的序列，其中序列的第一个状态是问题的初始状态，而最后一个状态则是问题的结束状态，介于它们之间的是中间状态。除了第一个状态外，该序列中任何状态都可以通过一条规则由与它相邻的前一个状态转换得到。下页的图给出了一个搜索问题的示意图。含义是如何在一个比较大的问题空间中，只通过搜索比较小的范围，就找到问题的解。寻找这样的序列过程称为搜索。一般而言，很多问题求解过程可以转化为状态空间的搜索问题29人工智能ppt课件搜索问题30搜索方法从搜索方式上来讲，搜索可以划分为两大类，即盲目搜索和启发式搜索。

所谓盲目搜索，就是未利用问题的知识，采用固定的方式生成状态的方法。显然这种方法的搜索效率是低下的，但方法具有通用性。当一时难以找到求解问题的有效知识时，是一种不得不采用的方法。

所谓启发式搜索，与盲目搜索正好相反，它利用问题的知识，缩小问题的搜索范围，选择那些最有可能在（最优）解路径上的状态优先搜索，以尽快地找到问题的（最优）解。由于利用了问题的有关知识，一般来说，搜索效率会有所提高。但如何找到对求解问题有帮助的知识，以及如何利用这些知识，是问题的关键所在。

搜索方法从搜索方式上来讲，搜索可以划分为两大类，即盲目搜索和31到目前为止，在人工智能领域中已提出许多具体的搜索方法，概括起来有：

（1）求任一解路的搜索策略

回溯法（Backtracking）

爬山法（HillClimbing）

宽度优先法（Breadth-first）

深度优先法（Depth-first）

限定范围搜索法（BeamSearch）好的优先法（Best-first）

（2）求最佳解路的搜索策略

大英博物馆法（BritishMuseum）

分枝界限法（BranchandBound）

动态规划法（DynamicProgramming）

最佳图搜索法（A﹡）

（3）求与或关系解图的搜索法

一般与或图搜索法（AO﹡）

极小极大法（Minimax）

α－β剪枝法（Alpha-betaPruning）

启发式剪枝法（HeuristicPruning）

今后对其中几个基本搜索策略作进一步的讨论。

到目前为止，在人工智能领域中已提出许多具体的搜索方法，概括起32无信息的搜索策略这部分无信息搜索（也称为盲目搜索）主要包括广度优先搜索、代价一致搜索、深度优先搜索、深度有限搜索和迭代深度优先搜索和双向搜索几种。以下我们分别进行讲述和对比。广度优先搜索：它是一种简单的搜索策略，首先扩展根节点，接下来扩展根节点的所有后继，然后再扩展它们的后继，依此类推。一般来讲，在下一层的任何节点扩展之前搜索树上当前层的所有节点都已经扩展完。1959年Moore最早使用广度优先搜索形式化并解决迷宫问题。广度优先搜索可以调用函数TREE-SEARCH来实现，该函数以一个空的边缘为参数，而边缘是一个先进先出(FIFO)队列，保证先访问的节点先扩展。这意味着浅层的节点会在深层节点之前被扩展。无信息的搜索策略这部分无信息搜索（也称为盲目搜索）主要包括广33一个简单二叉树的搜索过程ABFCGEDABFCGEDABFCGEDABFCGED在每一个阶段，下一个要扩展的节点由箭头指示出来。一个简单二叉树的搜索过程ABFCGEDABFCGEDABFC34广度优先搜索算法的评价从完备性和最优性来看我们很容易知道广度优先搜索是完备的——如果最浅的目标节点处于一个有限的深度d，广度优先搜索在扩展完比它浅的所有节点（假设分支因子b是有限的）后最终能找到这个目标节点。但最浅的目标不一定是最优的目标节点：从技术上讲，如果路径耗散是节点深度的非递减函数，广度优先算法才是最优的。广度优先搜索算法的评价从完备性和最优性来看从技术上讲，如果路35从时间和空间复杂性来看我们考虑一个假想的状态空间，状态空间中每个状态都有b个后继。这样搜索树的根节点生成第一层的b个子节点，每个子节点又生成b个子节点，在第二层共有b2个节点，这些节点中的每一个又生成b个子节点，如此类推，假设解的深度为d，在最坏情况下，我们将扩展d层除了最后一个节点外的所有节点（因为目标节点本身尚未被扩展），那么在d+1层会产生bd+1-b个节点，

这时已经生成的节点数是多少？b+b2+b3+…+bd+(bd+1-b)=O(bd+1)每个生成的节点都必须保存在内存中，因为它既是边缘节点的一部分又是边缘节点的祖先，因此该算法的时间复杂度和空间复杂度相等（再加上一个根节点）。从时间和空间复杂性来看b+b2+b3+…+bd+(bd+1-36广度优先搜索时间与空间复杂度分析深度节点数时间数内存211000.11秒1Mbit下图是分支因子b=10的时候广度优先搜索到不同的解深度d所需要的时间和空间开销，并假定每秒生成10000个节点，并且存储一个节点需要1k字节。4111,10011秒106M610719分钟10G810931小时1T(KG)101011129天101T12101335年10P(KT)1410153523年1E(KP)广度优先搜索时间与空间复杂度分析深度节点数37从上图我们可以得到两个结论：第一个结论，在广度优先搜索算法中内存的需求是比执行时间消耗更大的问题。第二个结论，时间需求仍是个主要因素。一般来讲，除最小的实例外指数级复杂度的搜索问题不能用无信息的方法解决。从上图我们可以得到两个结论：38代价一致搜索当所有单步消耗相等时，广度优先搜索是最优的，因为它们总是扩展深度最浅的未扩展节点。但代价一致搜索扩展的是路径消耗最低的节点n。

在什么条件下广度优先搜索与代价一致搜索相同？代价一致搜索时对一条路径的步数并不关心，而只是关心所经步骤总的耗散。因此若扩展到一个具有能返回同一状态的零耗散行动的节点时会陷入无限循环，造成不完备性。若每一步的耗散都大于等于某个最小的正常数时，能够保证其完备性与最优性。沿着路径的耗散总是增加的，因此第一个被扩展的目标节点就是最优解（记住，算法只对被选中扩展的节点进行目标测试）。代价一致搜索当所有单步消耗相等时，广度优先搜索是最优的，因为39代价一致算法的度量代价一致搜索由路径的耗散引导而不是深度，因此它的复杂度不能简单地使用b和d来刻画。我们使用C*表示最优解的耗散值，并且假定每个行动的耗散至少为。那么算法的时间和空间复杂度为，要比bd大得多。为什么？什么条件下一广度优先算法复杂度一样？我们学过代价一致的搜索吗？代价一致算法的度量代价一致搜索由路径的耗散引导而不是深度，因40深度优先搜索深度优先搜索总是扩展搜索树的当前边缘中最深的节点，搜索直接推进到搜索树的最深层，那里的节点没有后继节点。当那些节点被扩展完之后，它们被从边缘中去掉，然后搜索算法“向上回到”下一个还有未扩展后继节点的稍浅的节点。

在搜索算法Tree-Search中采用什么策略能够使搜索过程按照深度优先进行？深度优先搜索深度优先搜索总是扩展搜索树的当前边缘中最深的节点41ABFCGEDHIJKLMNOABFCGEDHIJKLMNOOABFCGEDHIJKLMNABFCGEDHIJKLMNOABFCGEDHIJKLMNOABFCGEDHIJKLMNOABFCGEDHIJKLMNOABFCGEDHIJKLMNO42ABFCGEDHIJKLMNOABFCGEDHIJKLMNOABFCGEDHIJKLMNOABFCGEDHIJKLMNOABFCGEDHIJKLMNOABFCGEDHIJKLMNOABFCGEDHIJKLMNOABFCGEDHIJKLMNO43深度优先搜索对内存的需求很少，它只需要存储一条从根节点到叶节点的路径，以及该路径上每个节点的所有未被扩展的兄弟节点即可。一旦一个节点被扩展，当它的所有后代都被扩展和这个节点从内存中删除。因此，对上面的搜索图，若分支因子为b，最大深度为m的状态空间，深度优先搜索只需要存储bm+1个节点。与广度优先相同假设下，并且假设与目标节点在同一深度的节点没有后继节点，我们看到在深度d=12时深度优先搜索只需要118k字节而不是10P字节，节省了大约百亿倍的空间。深度优先搜索的缺点是它有可能错误地选择一条分支并且沿着一条很长（甚至是无限的）路径一直走下去，而如果做出不同的选择则可能引导对树根节点附近的解进行搜索。深度优先搜索对内存的需求很少，它只需要存储一条从根节点到叶节441初始化。取图中任意结点s(G={s})作为初始结点将其赋值到OPEN表，CLOSED表置空。2循环执行以下语句直至找到解或OPEN表为空2.1n=first(OPEN);2.2IFGOAL(n)return(SUCCESS)；算法结束；2.3REMOVE(n,OPEN)，ADD(n,CLOSE);2.4EXPAND(n)->{mi};G=ADD(mi,G);2.5ADD(mj,OPEN),并标记mj到n的指针；把不在OPEN或CLOSE中的结点放在OPEN表的最前面，使浓度大的结点可优先扩展。深度优先搜索算法的框架1初始化。取图中任意结点s(G={s})作为初始结点将其赋45深度有限搜索前面我们看到，深度优先搜索虽然占用的内存比较小，但这种算法不是完备的也不是最优的。为此，我们可以通过对深度优先搜索提供一个预先设定的的深度限制l来解决，就是说深度为l的节点被当作没有后继的节点对待，这种办法称为深度有限搜索。对深度限制解决了无穷路径问题。但问题是如果我们选择的l<d，那么它又引入了一种不完备性问题。同样如果我们选择的l>d的话，搜索也不是最优的，深度优先可以看作深度有限的一种特殊情况。那么如何来优化这种方法呢？深度有限搜索可以通过对一般的树搜索算法或者递归深度优先搜索算法进行简单的修改来实现。即对深度限制l不断进行迭代更新。深度有限搜索前面我们看到，深度优先搜索虽然占用的内存比较小，46迭代深入搜索迭代深入搜索（或迭代深入深度优先搜索）是一个用来寻找最合适的深度限制的通用策略，它经常与深度优先搜索结合使用。做法是不断地增大深度限制----首先为0，接着为1，然后是2，依此类推----直到找到目标节点。但深度限制达到d，即最浅的目标节点的深度时，就找到目标节点，下面的图给出了算法的搜索过程，该算法结合了深度优先和广度优先搜索的优点，它的空间和深度优先搜索需求一样小，为O(bd)。它和广度优先搜索一样当分支因子有限时是完备的，当路径耗散是节点深度的非递减函数时是最优的。迭代深入搜索迭代深入搜索（或迭代深入深度优先搜索）是一个用来47AL=0AABCL=1ABCABCABCABFCGEDL=2ABFCGEDABFCGEDAL=0AABCL=1ABCABCABCABFCGEDL=248ABFCGEDABFCGEDABFCGEDABFCGEDABFCGEDABFCGEDABFCGEDABFCGEDABFCGEDAB49ABFCGEDHIJKLMNOL=3ABFCGEDHIJKLMNOABFCGEDHIJKLMNOABFCGEDIJKLMNOHABFCGEDJKLMNOHIIABFCGEDJKLMNOHABFCGEDHIJKLMNOL=3ABFCGEDHIJKL50IABFCGEDKLMNOHJIABFCGEDKLMNOHJIABFCGEDKLMNOHJIABFCGEDKLMNOHJIABFCGEDKLMNOHJIABFCGEDKLMNOHJIABFCGEDKLMNOHJIABFCGEDKLMNOHJ51迭代深入搜索也许看起来比较浪费，因为有些状态被多次生成。但实际上代价不是很大。原因在于一棵每层的分支因子都相同（或相近）的搜索树中，底层节点（深度d)只被生成一次，倒数第二层的节点生成两次。依此类推，一直到根节点的子节点，它被生成d次。因此生成的总节点数为(d+1)b0+db+(d-1)b2+…+2bd-1+bd，时间复杂度是O(bd)。与广度优先生成的节点数相比，它没有生成d+1层的节点而广度优先可能会生成一些d+1层的节点，因此它比广度优先搜索要快。比如b=10,d=5，迭代深入搜索生成50+400+3000+20000+100000=123450个节点，而广度优先搜索生成10+100+1000+10000+100000+999990=1111110个节点。迭代深入搜索也许看起来比较浪费，因为有些状态被多次生成。但实52迭代深入搜索的性质完备吗?是时间复杂性?

(d+1)b0+db1+(d-1)b2+…+bd=O(bd)空间复杂性?

O(bd)最优性?是,ifstepcost=1迭代深入搜索的性质完备吗?是53双向搜索双向搜索的思想是同时进行两个方向的搜索，一个从初始状态向目标状态进行，另一个从目标状态向初始状态搜，动机的产生的节点是bd/2+bd/2要比bd小得多，即两个小圆的面积之和比起点为中心达到目标的大圆面积大得多。双向搜索最吸引人的地方是时间复杂度的降低，但实际上如何从目标向初始状态搜并不容易。双向搜索双向搜索的思想是同时进行两个方向的搜索，一个从初始状54几种算法的比较标准广度优先代价一致深度优先深度限制迭代深入完备性是是否否是时间

O(bd+1)O(b[C*/])O(bm)O(bl)O(bd)空间

O(bd+1)O(b[C*/])O(bm)O(bl)O(bd)最优性是是否否是几种算法的比较标准广度优先代价一致55回溯策略回溯策略属于盲目搜索的一种。所谓回溯策略，简单地说是这样一种策略：首先将规则给出一个固定的排序，在搜索时，对当前状态（搜索开始时，当前状态是初始状态）依次检测每一条规则，在当前状态未使用过的规则中找到第一条可触发规则，被应用于当前状态，得到的新状态重新设置为当前状态，并重复以上搜索。如果当前状态无规则可用，或者所有规则已经被试探过仍未找到问题的解，则将当前状态的前一个状态（即直接生成该状态的状态）设置为当前状态。重复以上搜索，直到找到问题的解，或者试探了所有可能后仍找不到问题的解为止。回溯策略回溯策略属于盲目搜索的一种。所谓回溯策略，简单地说是56回溯策略可以有多种实现的方法，其中用递归法实现也许是最简单的方法了，本书中给出的就是这种算法。

对于初次接触递归程序设计或者对递归程序设计不熟悉的同学，对这段算法也许不容易理解。在这里对递归程序设计的思想做一个通俗易懂的介绍。对递归程序设计熟悉的同学可以略过。

以C语言为例，我们在写一个函数时，一般是用其他已经有的函数（系统提供的库函数或者自己已经定义好的自定义函数）来定义该函数。而递归程序设计则是在定义一个函数时“自己调用自己”（直接的，或者间接的），比如定义abc这个函数，如果写成这样的形式：

回溯策略可以有多种实现的方法，其中用递归法实现也许是最简单的57intabc(intn)

{

……

abc(m);

……

}

则abc是一个递归调用，因为我们在定义abc这个函数时，同时也用到了abc这个函数，这就是所谓的"自己调用自己"。

intabc(intn)

{

……

abc(m);

……58

其实我们早就"遇到"过递归了。在大家小的时候，都听过那个"从前有座山……"的故事吧？

"从前有座山，山里有个庙，庙里有个和尚正在讲故事，讲的什么故事呢？讲的是从前有座山，山里有个庙，庙里有个和尚正在讲故事，讲的什么故事呢？讲的是从前有座山，山里有个庙，庙里有个和尚正在讲故事，讲的什么故事呢？讲的是……"

这就是一个典型的递归。不过这个递归永远也不会结束，是一种"死递归"。但是我们大家谁也没有"永远"将这个故事听下去。因为当满足一定的条件时，比如讲故事的人口干舌燥不想讲了，故事也就结束了。这虽然是一个一点也不动听的故事，但它确实是一个故事。这里的"口干舌燥"就是递归的一个结束条件，正是由于有了这个条件，才使得递归结束。

其实我们早就"遇到"过递归了。在大家小的时候，都听过那个"59考察这个故事，有两个特点，一是有一个简单的结束条件，如这里的“口干舌燥”；二是每一次递归调用，都使得问题--在这里就是故事--距离结束近了一些。比如第二次讲“从前有座山”时，就比第一次讲“从前有座山”时距离故事结束近。正是这两点，构成了递归程序设计的两个要点。考察这个故事，有两个特点，一是有一个简单的结束条件，如这里的60下面举一个简单的C＋＋程序例子，在这个例子中，利用递归求解一个链表的长度。structLIST//定义一个简单的链表结构{Tdtat;structLIST*pNext;};intListLenght(LIST*pList)

//递归定义函数ListLenght

//函数的功能是求解给定链表的长度

{

if(pList==NULL)return0;

//递归的结束条件，一个空的链表长度定义为0

elsereturnListLenght(pList->pNext)+1;

//递归调用

//将求链表pList的长度问题，变换为求解pList->pNext的长度问题

//pList的长度等于pList->pNext的长度+1

}下面举一个简单的C＋＋程序例子，在这个例子中，利用递归求解一61递归过程BACKTRACK（DATA）

①IFTERM（DATA），RETURNNIL；TERM取真即找到目标，则过程返回空表NIL。

②IFDEADEND（DATA），RETURNFAIL；DEADEND取真，即该状态不合法，则过程返回FAIL，必须回溯。

③RULES：＝APPRULES（DATA）；APPRULES计算DATA的可应用规则集，依某种原则（任意排列或按启发式准则）排列后赋给RULES。

④LOOP：IFNULL（RULES），RETURNFAIL；NULL取真，即规则用完未找到目标，过程返回FAIL，必须回溯。

⑤R：＝FIRST（RULES）；取头条可应用规则。

⑥RULES：＝TAIL（RULES）；删去头条规则，减少可应用规则表的长度。

⑦RDATA：＝GEN（R，DATA）；调用规则R作用于当前状态，生成新状态。

⑧PATH：＝BACKTRACK（RDATA）；对新状态递归调用本过程。

⑨IFPATH＝FAIL，GOLOOP；当PATH＝FAIL时，递归调用失败，则转移调用另一规则进行测试。

⑩RETURNCONS（R，PATH）；过程返回解路径规则表（或局部解路径子表）。递归过程BACKTRACK（DATA）

①IFTERM（D62下面对这个算法作几点说明。首先解释一下其中的变量、常量、谓词、函数等符号的意义。变量符号DATA、RULE