7 人工智能与专家系统(2014)

1、1 第五章第五章 问题求解策略问题求解策略 5.1 5.1 搜索的概念及基本原理搜索的概念及基本原理 5.2 5.2 图搜索策略图搜索策略 5.3 5.3 盲目搜索盲目搜索 5.4 5.4 启发式搜索启发式搜索 2 5.1 搜索的概念及基本原理 问题求解的基本方法有：搜索法、归约问题求解的基本方法有：搜索法、归约 法、归结法、推理法和产生式等。法、归结法、推理法和产生式等。 搜索技术是人工智能的核心技术之一。搜索技术是人工智能的核心技术之一。 对于无成熟方法可用的问题求解，对于无成熟方法可用的问题求解，只能只能 利用已有的知识利用已有的知识一步步地摸索求解，这种一步步地摸索求解，这种 问题求解

2、过程就是搜索。问题求解过程就是搜索。 3 现实世界中的大多数问题都是现实世界中的大多数问题都是非结构化问题非结构化问题，一般不存在，一般不存在 现成的求解方法来求解这样的问题，而只能利用已有的知现成的求解方法来求解这样的问题，而只能利用已有的知 识一步一步地识一步一步地摸索摸索着前进。着前进。 搜索搜索：是一种求解问题的方法，是寻找从问题初始事实到：是一种求解问题的方法，是寻找从问题初始事实到 最终答案的最终答案的推理路线推理路线的一种过程。的一种过程。 搜索包含两层含义搜索包含两层含义：一是根据问题实际情况，按照一定策：一是根据问题实际情况，按照一定策 略，从知识库中寻找可利用的知识，从而构

3、造出一条使问略，从知识库中寻找可利用的知识，从而构造出一条使问 题获得解决的题获得解决的推理路线推理路线；另一是找到的这条路线是时空；另一是找到的这条路线是时空复复 杂度最小的求解路线杂度最小的求解路线。 5.1 5.1 搜索的概念及基本原理搜索的概念及基本原理 4 l问题求解过程是搜索答案问题求解过程是搜索答案(目标目标)的过程的过程 / 所以所以 问题求解技术也叫搜索技术问题求解技术也叫搜索技术通过对状态空间通过对状态空间 的搜索而求解问题的技术的搜索而求解问题的技术 问题求解智能体是一种基于目标的智 能体 在寻找到达目标的过程中，当智能体 面对多个未知的选项时，首先检验各 个不同的导致已

4、知评价的状态的可能 行动序列，然后选择最佳序列这个 过程就是搜索 5 l问题可以形式化地定义为4个组成部分 智能体的初始状态(即搜索的开始) 后继函数智能体采取的可能行动的描述， 通常为 / 初始状态和后 继函数隐含地定义了问题的状态空间 / 状 态空间中的一条路径是通过行动序列连接起 来的一个状态序列 目标测试检查给定的状态是不是目标 路径耗散函数每条路径都有一个数值化的 耗散值，反映了性能度量/求解问题的代价 6 l问题的解就是初始状态到目标状态的路径 解的优劣由路径耗散函数量度(代价) 最优解就是路径耗散函数值最小的路径 l上述解题过程把解决一个问题的过程描述出来， 称之为解题知识的过程

5、性表示 过程性知识与陈述性知识相对 l搜索过程解题的特点没有直接的方法(公式)可 以求解，而是一步一步的探索 7 l数据基：代表了所要解决的问题，有初始状态，数据基：代表了所要解决的问题，有初始状态， 可能有目标状态也可能没有可能有目标状态也可能没有 l状态空间：在解题过程中的每一时刻，数据基状态空间：在解题过程中的每一时刻，数据基 都处于一定的状态，数据基所有可能状态的集都处于一定的状态，数据基所有可能状态的集 合称为状态空间合称为状态空间 l有向图：若把每个状态看成一个节点，则整个有向图：若把每个状态看成一个节点，则整个 状态空间是一个有向图状态空间是一个有向图 / 该图不一定全连通，该图

6、不一定全连通， 即从某些状态不一定能到达另外一些状态即从某些状态不一定能到达另外一些状态 8 l可解的：在每个连通部分，每个弧代表一个运 算符，将状态改变 / 如果从代表初始状态的节 点出发，有一条路径通向目标状态，则称此目 标状态所代表的问题在当前初始状态下是可解 的 l搜索空间：在解题过程中达到过的所有状态的 集合，称为搜索空间 不同于状态空间，搜索空间只是其中 一部分 状态空间和搜索空间都属于过程性知 识表示 9 搜索过程是否一定能找到解；搜索过程是否一定能找到解； 搜索过程是否终止运行或是否会陷入死循环；搜索过程是否终止运行或是否会陷入死循环； 当搜索过程找到一个解时，是否为最佳解；当

7、搜索过程找到一个解时，是否为最佳解； 搜索过程的时间与空间复杂性如何。搜索过程的时间与空间复杂性如何。 搜索的基本问题搜索的基本问题 10 搜索的主要过程搜索的主要过程 （1）从初始或目的状态出发，并将它作为当前状态；）从初始或目的状态出发，并将它作为当前状态； （2）扫描操作算子集，运用操作算子得到新的状态，）扫描操作算子集，运用操作算子得到新的状态， 并建立指向其父节点的指针；并建立指向其父节点的指针； （3）检查新状态是否满足结束状态，如果满足，则得）检查新状态是否满足结束状态，如果满足，则得 到解，给出解答路径；否则将新状态作为当前状态，到解，给出解答路径；否则将新状态作为当前状态，

8、返回第（返回第（2）步再进行搜索。）步再进行搜索。 11 搜索方向搜索方向 从初始状态出发的正向搜索，也称为数据驱动；从初始状态出发的正向搜索，也称为数据驱动； 从目的状态出发的逆向搜索，也称为目的驱动；从目的状态出发的逆向搜索，也称为目的驱动； 从初始状态出发作正向搜索，同时又从目的状态从初始状态出发作正向搜索，同时又从目的状态 出发作逆向搜索，直到两条路径在中间的某处汇出发作逆向搜索，直到两条路径在中间的某处汇 合为止，这称为双向搜索；合为止，这称为双向搜索； 在不具有对特定问题的任何有关信息的条件下，在不具有对特定问题的任何有关信息的条件下， 按固定的步骤进行搜索，这是盲目搜索。按固定的

9、步骤进行搜索，这是盲目搜索。 12 l有限搜索还是无限搜索？有限搜索还是无限搜索？ 若搜索空间有限，则任何一种穷举算法均能完若搜索空间有限，则任何一种穷举算法均能完 成任务。成任务。 l搜索空间是静态的还是动态生成的？搜索空间是静态的还是动态生成的？ 在人工智能中，搜索的对象在人工智能中，搜索的对象(常称状态常称状态)是在搜是在搜 索过程中逐步生成的，需将搜索对象的生成和索过程中逐步生成的，需将搜索对象的生成和 评估的代价计算在内。对于一般搜索，搜索空评估的代价计算在内。对于一般搜索，搜索空 间基本是静态的，或表或数组或数据库。间基本是静态的，或表或数组或数据库。 l已知目标还是未知目标？已知

10、目标还是未知目标？ l只要目标还是也要路径？路径是解题过程中应只要目标还是也要路径？路径是解题过程中应 用的操作序列。用的操作序列。 研究和选用搜索算法的原则研究和选用搜索算法的原则 13 l状态空间搜索还是问题空间搜索？状态空间搜索还是问题空间搜索？ 在解题过程中的每一时刻，所要解决的问题均在解题过程中的每一时刻，所要解决的问题均 处于一定的状态，搜索过程只是将一个状态变处于一定的状态，搜索过程只是将一个状态变 成另一个状态成另一个状态(如，一盘棋局变成另一盘棋局如，一盘棋局变成另一盘棋局)， 则称为状态空间搜索。则称为状态空间搜索。 若搜索的对象是问题，搜索的原则是把一个复若搜索的对象是问

11、题，搜索的原则是把一个复 杂的问题化为一组比较简单的子问题杂的问题化为一组比较简单的子问题(如把一个如把一个 复杂的下棋策略分为几个子策略复杂的下棋策略分为几个子策略)，则称为问题，则称为问题 空间搜索。空间搜索。 注：问题空间搜索常常比状态空间搜索有效，但注：问题空间搜索常常比状态空间搜索有效，但 算法要复杂些。算法要复杂些。 研究和选用搜索算法的原则研究和选用搜索算法的原则 14 l有约束还是无约束？有约束还是无约束？ 问题空间搜索时，若子问题间互相无约束关系，问题空间搜索时，若子问题间互相无约束关系， 则比较简单，否则需要回溯，即放弃已解决的则比较简单，否则需要回溯，即放弃已解决的 子问

12、题，走回头路，寻找新的解法。子问题，走回头路，寻找新的解法。 l数据驱动还是目标驱动？数据驱动还是目标驱动？ 数据驱动是向前搜索，目标驱动是向后搜索。数据驱动是向前搜索，目标驱动是向后搜索。 l单向搜索还是双向搜索？单向搜索还是双向搜索？ l盲目搜索还是启发式搜索？盲目搜索还是启发式搜索？ 按照预定的控制策略实行搜索，在搜索过程中按照预定的控制策略实行搜索，在搜索过程中 获取的中间信息不用来改进控制策略，称为盲获取的中间信息不用来改进控制策略，称为盲 目搜索，反之，称为启发式搜索。目搜索，反之，称为启发式搜索。 研究和选用搜索算法的原则研究和选用搜索算法的原则 15 状态空间表示法是用状态空间

13、表示法是用“状态状态”和和“算符算符”来表来表 示问题的一种方法。示问题的一种方法。 状态：状态是描述问题求解过程中任一时刻状态：状态是描述问题求解过程中任一时刻 状况的数据结构。状况的数据结构。 算符：引起状态的某些分量变化，从而使问算符：引起状态的某些分量变化，从而使问 题从一个状态变为另一个状态的操作称为算符题从一个状态变为另一个状态的操作称为算符 。 状态空间：问题的全部状态和一切算符所构状态空间：问题的全部状态和一切算符所构 成的集合成为状态空间。成的集合成为状态空间。 状态空间表示法：状态空间表示法： 16 一般搜索方法分类一般搜索方法分类 盲目搜索是按预定的控制策略进行，在搜盲目

14、搜索是按预定的控制策略进行，在搜 索的过程中所获得的信息不用来改进控制索的过程中所获得的信息不用来改进控制 策略的一种搜索。策略的一种搜索。 启发式搜索是在搜索中加入了与问题有关启发式搜索是在搜索中加入了与问题有关 的启发式信息，用来指导搜索朝着最有希的启发式信息，用来指导搜索朝着最有希 望的方向前进，加速问题的求解过程，并望的方向前进，加速问题的求解过程，并 找到最优解。找到最优解。 17 一般搜索方法分类一般搜索方法分类 盲目搜索盲目搜索 1) 无变量的盲目搜索无变量的盲目搜索 l 状态空间、问题空间的盲目搜索状态空间、问题空间的盲目搜索 l 深度优先、广度优先、代价优先、混合深度优先、广

15、度优先、代价优先、混合 l 向前、向后、双向向前、向后、双向 2) 有变量的盲目搜索有变量的盲目搜索 通代通代 启发式搜索启发式搜索 18 5.2 5.2 图搜索策略图搜索策略 l图搜索策略可以看成是一种在图中寻找图搜索策略可以看成是一种在图中寻找 路径的方法。初始结点和目标结点分别路径的方法。初始结点和目标结点分别 代表初始数据库和满足终止条件的数据代表初始数据库和满足终止条件的数据 库。求得把一个数据库变换为另一个数库。求得把一个数据库变换为另一个数 据库规则序列问题就等于求得图中的一据库规则序列问题就等于求得图中的一 条路径问题。条路径问题。 19 图图 搜搜 索索 过过 程程 框框 图

16、图 20 l一般图搜索算法中，提高搜索效率的关键一般图搜索算法中，提高搜索效率的关键 在于优化在于优化OPEN表中节点的排序方式，若表中节点的排序方式，若 每次排在表首的节点都在最终搜索到的解每次排在表首的节点都在最终搜索到的解 答路径上，则算法不会扩展任何多余的节答路径上，则算法不会扩展任何多余的节 点就可快速结束搜索。所以排序方式成为点就可快速结束搜索。所以排序方式成为 研究搜索算法的焦点，并由此形成了多种研究搜索算法的焦点，并由此形成了多种 搜索策略。搜索策略。 21 l盲目搜索又叫做无信息搜索，一般只适用于求解盲目搜索又叫做无信息搜索，一般只适用于求解 比较简单的问题。比较简单的问题。

17、 l宽度优先搜索和深度优先搜索，均属于盲目搜索宽度优先搜索和深度优先搜索，均属于盲目搜索 方法。方法。 l其共同缺点是节点排序的盲目性，由于不采用领其共同缺点是节点排序的盲目性，由于不采用领 域专门知识去指导排序，往往会搜索了大量无关域专门知识去指导排序，往往会搜索了大量无关 的状态节点后才碰到解答，所以称为盲目搜索。的状态节点后才碰到解答，所以称为盲目搜索。 5.3 5.3 盲目搜索盲目搜索 22 宽度优先搜索宽度优先搜索 l宽度优先搜索（宽度优先搜索（breadth-first search）的）的 定义：如果搜索是以接近起始节点的程度定义：如果搜索是以接近起始节点的程度 依次扩展节点的，

18、那么这种搜索就叫做宽依次扩展节点的，那么这种搜索就叫做宽 度优先搜索（度优先搜索（breadth-first search）。）。 l特点：这种搜索是逐层进行的；在对下一特点：这种搜索是逐层进行的；在对下一 层的任一节点进行搜索之前，必须搜索完层的任一节点进行搜索之前，必须搜索完 本层的所有节点。本层的所有节点。 23 宽度优先搜索示意图宽度优先搜索示意图 24 宽度优先搜索算法宽度优先搜索算法 （1） 把起始节点放到把起始节点放到OPEN表中（如果该起始节点为一表中（如果该起始节点为一 目标节点，则求得一个解答）。目标节点，则求得一个解答）。 （2） 如果如果OPEN是个空表，则没有解，失败

19、退出；否则是个空表，则没有解，失败退出；否则 继续。继续。 （3）把第一个节点（节点）把第一个节点（节点 n）从）从OPEN表移出，并把它表移出，并把它 放入放入CLOSED扩展节点表中。扩展节点表中。 （4）扩展节点）扩展节点n。若没有后继节点，则转向上述第（。若没有后继节点，则转向上述第（2） 步。步。 （5） 把把n 的所有后继节点放到的所有后继节点放到OPEN表的末端，并提供表的末端，并提供 从这些后继节点回到从这些后继节点回到n的指针。的指针。 （6） 如果如果n 的任一个后继节点是个目标节点，则找到的任一个后继节点是个目标节点，则找到 一个解答，成功退出；否则转向第（一个解答，成功

20、退出；否则转向第（2）步。）步。 25 宽宽 度度 优优 先先 算算 法法 框框 图图 26 宽度优先搜索方法分析宽度优先搜索方法分析 l宽度优先搜索方法能够保证在搜索树中找到一宽度优先搜索方法能够保证在搜索树中找到一 条通向目标节点的最短途径；这棵搜索树提供条通向目标节点的最短途径；这棵搜索树提供 了所有存在的路径（如果没有路径存在，那么了所有存在的路径（如果没有路径存在，那么 对有限图来说，我们对有限图来说，我们 就说该法就说该法 失败失败 退出；对于退出；对于 无限图来说，则永远不会终止）。无限图来说，则永远不会终止）。 l例：把宽度优先搜索应用于八数码难题时所生例：把宽度优先搜索应用于

21、八数码难题时所生 成的搜索树，这个问题就是要把初始棋局变为成的搜索树，这个问题就是要把初始棋局变为 如图所示的目标棋局问题。如图所示的目标棋局问题。 27 八数码难题的宽度八数码难题的宽度 优先搜索树优先搜索树 28 宽度优先搜索宽度优先搜索 l搜索树上的所有节点都标记它们所对应的搜索树上的所有节点都标记它们所对应的 状态描述，每个节点旁边的数字表示节点状态描述，每个节点旁边的数字表示节点 扩展的顺序（按顺时针方向移动空格）。扩展的顺序（按顺时针方向移动空格）。 图中最后一个节点是目标节点。图中最后一个节点是目标节点。 29 深度优先搜索深度优先搜索(depth-first search) 3

22、0 深度优先搜索深度优先搜索 l分析深度优先搜索示意图可看出，在深度优先分析深度优先搜索示意图可看出，在深度优先 搜索中，我们首先扩展最新产生的（即最深的）搜索中，我们首先扩展最新产生的（即最深的） 节点。深度相等的节点可以任意排列。节点。深度相等的节点可以任意排列。 l定义节点的深度如下：定义节点的深度如下： （1） 起始节点（即根节点）的深度为起始节点（即根节点）的深度为0。 （2） 任何其它节点的深度等于其父辈节点深度加任何其它节点的深度等于其父辈节点深度加 上上1。 31 l首先，扩展最深的节点的结果使得搜索沿着状首先，扩展最深的节点的结果使得搜索沿着状 态空间某条单一的路径从起始节点

23、向下进行下态空间某条单一的路径从起始节点向下进行下 去；只有当搜索到达一个没有后裔的状态时，去；只有当搜索到达一个没有后裔的状态时， 它才考虑另一条替代的路径。替代路径与前面它才考虑另一条替代的路径。替代路径与前面 已经试过的路径不同之处仅仅在于改变最后已经试过的路径不同之处仅仅在于改变最后n步，步， 而且保持而且保持n尽可能小。尽可能小。 32 深度界限深度界限 l对于许多问题，其状态空间搜索树的深度可能对于许多问题，其状态空间搜索树的深度可能 为无限深，或者可能至少要比某个可接受的解为无限深，或者可能至少要比某个可接受的解 答序列的已知深度上限还要深。为了避免考虑答序列的已知深度上限还要深

24、。为了避免考虑 太长的路径（防止搜索过程沿着无益的路径扩太长的路径（防止搜索过程沿着无益的路径扩 展下去），往往给出一个节点扩展的最大深展下去），往往给出一个节点扩展的最大深 度度深度界限。任何节点如果达到了深度界深度界限。任何节点如果达到了深度界 限，那么都将把它们作为没有后继节点处理。限，那么都将把它们作为没有后继节点处理。 值得说明的是，即使值得说明的是，即使 应用了深度界限的应用了深度界限的 规定，规定， 所求得的解答路径并不一定就是最短的路径。所求得的解答路径并不一定就是最短的路径。 33 含有深度界限的深度优先搜索算法含有深度界限的深度优先搜索算法 （1） 把起始节点放到未扩展节点

25、OPEN表中。如果 此节点为一目标节点，则得到一个解。 （2） 如果OPEN为一空表，则失败退出。 （3） 把第一个节点（节点n）从OPEN表移到 CLOSED表。 （4） 如果节点n的深度等于最大深度，则转向（2）。 （5） 扩展节点n ，产生其全部后裔，并把它们放入 OPEN表的前头。如果没有后裔，则转向（2）。 （6） 如果后继节点中有任一个为目标节点，则求得一 个解，成功退出；否则，转向（2）。 34 有有 界界 深深 度度 优优 先先 搜搜 索索 算算 法法 图图 35 按深度优先搜索生成的八数码按深度优先搜索生成的八数码 难题搜索树，深度界限为难题搜索树，深度界限为5。 36 把要

26、求解的问题的具体领域的知识加进搜索把要求解的问题的具体领域的知识加进搜索 算法中，控制搜索过程，以提高算法效率的搜索算法中，控制搜索过程，以提高算法效率的搜索 方法，称为启发式搜索。方法，称为启发式搜索。 注：注：1）这里搜索的对象）这里搜索的对象(常称状态常称状态)往往是边往往是边 搜索边生成，因此在考虑这种搜索的复杂性时，搜索边生成，因此在考虑这种搜索的复杂性时， 必须将搜索对象的生成和评估的代价计算在内。必须将搜索对象的生成和评估的代价计算在内。 5.4 启发式搜索启发式搜索 37 注：注：2)根据启发性信息根据启发性信息(特定领域的知识信息特定领域的知识信息)，在，在 生成搜索树时可考

27、虑种种可能的选择：生成搜索树时可考虑种种可能的选择： a)下一步展开哪个节点？下一步展开哪个节点？ b)是部分展开还是全部展开？是部分展开还是全部展开？ c)使用哪个规则使用哪个规则(算子算子)？ d)怎样决定舍弃还是保留新生成的节点？怎样决定舍弃还是保留新生成的节点？ e)怎样决定舍弃还是保留一棵子树？怎样决定舍弃还是保留一棵子树？ f)怎样决定停止或继续搜索？怎样决定停止或继续搜索？ g)如何定义启发函数如何定义启发函数(估值函数估值函数)？ h)如何决定搜索方向？如何决定搜索方向？ 启发式搜索启发式搜索 38 5.4 启发式搜索 启发性信息启发性信息 按其用途划分按其用途划分, , 启发

28、性信息可分为以下三类：启发性信息可分为以下三类： (1) (1) 用于扩展节点的选择用于扩展节点的选择, , 即用于决定应先扩即用于决定应先扩 展哪一个节点展哪一个节点, , 以免盲目扩展。以免盲目扩展。 (2) (2) 用于生成节点的选择用于生成节点的选择, ,即用于决定应生成即用于决定应生成 哪些后续节点哪些后续节点, ,以免盲目地生成过多无用节点。以免盲目地生成过多无用节点。 (3) (3) 用于删除节点的选择用于删除节点的选择, ,即用于决定应删除即用于决定应删除 哪些无用节点哪些无用节点, , 以免造成进一步的时空浪费。以免造成进一步的时空浪费。 39 启发信息与估价函数启发信息与估

29、价函数 l启发信息按运用的方式可分为：启发信息按运用的方式可分为： （1）陈述性启发信息）陈述性启发信息 （2）过程性启发信息）过程性启发信息 （3）控制性启发信息）控制性启发信息 40 估价函数估价函数 l一个比较灵活的方法是应用某些准则来重新一个比较灵活的方法是应用某些准则来重新 排列每一步排列每一步OPEN表中所有节点的顺序。然后，表中所有节点的顺序。然后， 搜索就可能沿某个被认为是最有希望的边缘区搜索就可能沿某个被认为是最有希望的边缘区 段向外扩展。应用这种排序过程，需要某些估段向外扩展。应用这种排序过程，需要某些估 算节点算节点“希望希望”的量度。用来估算节点希望程的量度。用来估算节

30、点希望程 度的量度，叫做估价函数（度的量度，叫做估价函数（evaluation function）。）。 41 a)对于每个在搜索过程中遇到的新状态，计算对于每个在搜索过程中遇到的新状态，计算 一个估计值，根据估计值的大小，确定下一步一个估计值，根据估计值的大小，确定下一步 将从哪一个状态开始继续前进。将从哪一个状态开始继续前进。 b)一般以估计值小者作为较优的状态，以此实一般以估计值小者作为较优的状态，以此实 现最佳优先搜索。现最佳优先搜索。 c)计算状态估计值的函数是确定的，但每个状计算状态估计值的函数是确定的，但每个状 态的估计值的大小与初始状态到该路径有关。态的估计值的大小与初始状态到

31、该路径有关。 有序搜索算法的基本思想有序搜索算法的基本思想 42 1) 用多个估计值函数来用多个估计值函数来“层层设卡层层设卡” 2) 对估计值函数的形式加以限制，以保证它对估计值函数的形式加以限制，以保证它 一定能找到解，甚至一定能找到最优解。一定能找到解，甚至一定能找到最优解。 有序搜索算法改进有序搜索算法改进 最短路径问题的求解 例、假设例、假设A A、B B、C C、D D、E E各个城市之间旅费如下图红各个城市之间旅费如下图红 色数字所示。某人想从城市色数字所示。某人想从城市A A出发出发游览各城市一遍游览各城市一遍， 而所用而所用旅费最少旅费最少，试编程输出结果。，试编程输出结果。

32、 问题分析问题分析 解这类问题时，若采用穷举法把所有可能的情况解这类问题时，若采用穷举法把所有可能的情况 全部列出，再找出其中旅费最少的那条路径；或者采全部列出，再找出其中旅费最少的那条路径；或者采 用递归（深搜）找出所有路径，再找出旅费最少的那用递归（深搜）找出所有路径，再找出旅费最少的那 条。这两种方法都是费时非常多的解法，如果城市数条。这两种方法都是费时非常多的解法，如果城市数 目多的话则更加突出。目多的话则更加突出。 实际上我们知道，递归（深搜）之类的算法一般实际上我们知道，递归（深搜）之类的算法一般 用于求所有解问题（例如求从用于求所有解问题（例如求从A A出发每个城市都要走出发每个

33、城市都要走 一遍一共有哪几种走法？），所以这些算法对于求最一遍一共有哪几种走法？），所以这些算法对于求最 短路径这类最优解问题显然是不合适的。短路径这类最优解问题显然是不合适的。 首先，对于这类图，应该先建立一个邻接矩阵，存放任意两首先，对于这类图，应该先建立一个邻接矩阵，存放任意两 点间的数据（如距离、费用、时间等），以便在程序中方便调用，点间的数据（如距离、费用、时间等），以便在程序中方便调用， 以下介绍几种常见的、更好的求最短路径问题的算法。以下介绍几种常见的、更好的求最短路径问题的算法。 最短路径问题的求解最短路径问题的求解 一、宽度优先搜索一、宽度优先搜索 宽搜也并不是解决这类问题的

34、优秀算法，这里简单介绍一下算法思路，为后宽搜也并不是解决这类问题的优秀算法，这里简单介绍一下算法思路，为后 面的优秀算法做个铺垫。具体如下：面的优秀算法做个铺垫。具体如下： 1 1、从、从A A点开始依次展开得到点开始依次展开得到ABAB、ACAC、ADAD、AEAE四个新结点（第二层结点），当四个新结点（第二层结点），当 然每个新结点要记录下其旅费；然每个新结点要记录下其旅费； 2 2、 再次由再次由ABAB展开得到展开得到ABCABC、ABDABD、ABEABE三个新结点（第三层结点），而由三个新结点（第三层结点），而由ACAC 结点可展开得到结点可展开得到ACBACB、ACDACD、AC

35、EACE三个新结点，自然由三个新结点，自然由ADAD可以展开得到可以展开得到ADBADB、ADCADC、 ADEADE，由，由AEAE可以展开得到可以展开得到AEBAEB、AECAEC、AEDAED等结点，对每个结点也须记录下其旅费；等结点，对每个结点也须记录下其旅费； 3 3、 再把第三层结点全部展开，得到所有的第四层结点：再把第三层结点全部展开，得到所有的第四层结点：ABCDABCD、ABCEABCE、ABDCABDC、 ABDEABDE、ABECABEC、ABEDABED、AEDBAEDB、AEDCAEDC，每个结点也需记录下其旅费；，每个结点也需记录下其旅费； 4 4、 再把第四层结点

36、全部展开，得到所有的第五层结点：再把第四层结点全部展开，得到所有的第五层结点：ABCDEABCDE、 ABCEDABCED、AEDBCAEDBC、AEDCBAEDCB，每个结点也需记录下其旅费；，每个结点也需记录下其旅费； 5 5、 所有可能的结点均已展开，而第五层结点中旅费最少的就是题目的解。所有可能的结点均已展开，而第五层结点中旅费最少的就是题目的解。 由上可见，这种算法也是把所有的可能路径都列出来，再从中找出旅费最少由上可见，这种算法也是把所有的可能路径都列出来，再从中找出旅费最少 的那条，显而易见也是一种很费时的算法。的那条，显而易见也是一种很费时的算法。 最短路径问题的求解最短路径问

37、题的求解 二、二、 启发式搜索启发式搜索 在宽度优先搜索算法的基础上，每次并不是把所有可展开的在宽度优先搜索算法的基础上，每次并不是把所有可展开的 结点展开，而是对所有没有展开的结点，利用一个自己确定的估结点展开，而是对所有没有展开的结点，利用一个自己确定的估 价函数对所有没展开的结点进行估价，从而找出最应该被展开的价函数对所有没展开的结点进行估价，从而找出最应该被展开的 结点（也就是说我们要找的答案最有可能是从该结点展开），而结点（也就是说我们要找的答案最有可能是从该结点展开），而 把该结点展开，直到找到目标结点为止。把该结点展开，直到找到目标结点为止。 这种算法最关键的问题就是如何确定估价

38、函数，估价函数越这种算法最关键的问题就是如何确定估价函数，估价函数越 准，则能越快找到答案。这种算法实现起来并不难，只不过难在准，则能越快找到答案。这种算法实现起来并不难，只不过难在 找准估价函数，大家可以自已找相关资料学习和思考。找准估价函数，大家可以自已找相关资料学习和思考。 最短路径问题的求解 三、等代价搜索法三、等代价搜索法 等代价搜索法也是在宽度优先搜索的基础上进行部分优化的一种算法，它与等代价搜索法也是在宽度优先搜索的基础上进行部分优化的一种算法，它与 启发式搜索的相似之处都是每次只展开某一个结点（不是展开所有结点），不同启发式搜索的相似之处都是每次只展开某一个结点（不是展开所有结

39、点），不同 之处在于：它不需要去另找专门的估价函数，而是以该结点到之处在于：它不需要去另找专门的估价函数，而是以该结点到A A点的距离作为估点的距离作为估 价值，也就是说，等代价搜索法是启发式搜索的一种简化版本。它的大体思路是：价值，也就是说，等代价搜索法是启发式搜索的一种简化版本。它的大体思路是： 1 1、 从从A A点开始依次展开得到点开始依次展开得到ABAB（7 7）、）、ACAC（3 3）、）、ADAD（1010）、）、AEAE（1515）四个）四个 新结点，把第一层结点新结点，把第一层结点A A标记为已展开，并且每个新结点要记录下其旅费（括号标记为已展开，并且每个新结点要记录下其旅费

40、（括号 中的数字）；中的数字）； 2 2、 把未展开过的把未展开过的ABAB、ACAC、ADAD、AEAE四个结点中距离最小的一个展开，即展开四个结点中距离最小的一个展开，即展开 ACAC（3 3）结点，得到）结点，得到ACBACB（8 8）、）、ACDACD（1616）、）、ACEACE（1313）三个结点，并把结点）三个结点，并把结点ACAC标标 记为已展开；记为已展开； 3 3、 再从未展开的所有结点中找出距离最小的一个展开，即展开再从未展开的所有结点中找出距离最小的一个展开，即展开ABAB（7 7）结）结 点，得到点，得到ABCABC（1212）、）、ABDABD（2020）、）、ABEABE（1919）三个结点，并把结点）三个结点，并把结点ABAB标记为已展标记为已展 开；开； 4 4、 再次从未展开的所有结点中找出距离最小的一个展开，即展开再次