人工智能导论课件第4章第1-2节

1、人工智能导论Introduction to artificial intelligence人工智能导论Introduction to artifici第4章 搜索算法第4章 搜索算法【导读案例】AI能替代码农编程吗？讨论：【导读案例】AI能替代码农编程吗？讨论：1关于搜索算法2盲目算法3知情搜索4受到自然启发的搜索1关于搜索算法2盲目算法3知情搜索4受到自然启发的搜索第1节第1节4.1 关于搜索算法搜索是大多数人日常生活中的一部分。我们恐怕都有过找不到钥匙、找不到电视遥控器的经历，然后翻箱倒柜一番折腾。有时候，搜索可能更多的是在大脑中进行的。你可能会突然不记得自己到访过的地方的名字、不记得熟人

2、的名字，或者不记得曾经谙熟于心的歌词。4.1 关于搜索算法搜索是大多数人日常生活中的一部分。我们4.1 关于搜索算法搜索及其执行也是人工智能技术的重要基础，是人工智能中经常遇到的最重要的问题之一。许多算法专门通过列表进行搜索和排序。当然，如果数据按照逻辑顺序组织，那么搜索就会比较方便一些。想象一下，如果姓名和电话号码随机排列，那么搜索相对较大城市的电话簿会有多麻烦。因此，搜索和信息组织在智能系统的设计中发挥了重要作用。例如人们认为，性能更好的国际象棋博弈程序比同类型的程序更加智能。所谓搜索算法，就是利用计算机的高性能来有目的地穷举一个问题的部分或所有的可能情况，从而求出问题的解的一种方法。搜索

3、过程实际上是根据初始条件和扩展规则构造一棵解答树并寻找符合目标状态的节点的过程。4.1 关于搜索算法搜索及其执行也是人工智能技术的重要基础4.1 关于搜索算法搜索算法根据初始条件和扩展规则构造一颗“解答树”并寻找符合目标状态的节点。从最终的算法实现上来看，所有的搜索算法都可以划分成两个部分控制结构（扩展节点的方式）和产生系统（扩展节点），而所有的算法优化和改进主要都是通过修改其控制结构来完成的。其实，在这样的思考过程中，我们已经不知不 觉地将一个具体的问题抽象成了一个图论的模型树，即搜索算法的使用第一步在于搜索树的建立。4.1 关于搜索算法搜索算法根据初始条件和扩展规则构造一颗4.1 关于搜索

4、算法由图4-2可以知道，搜索树的初始状态对应着根结点，目标状态对应着目标结点。排在前的结点叫父结点，其后的结点叫子结点，同一层中的结点是兄弟结点，由父结点产生子结点叫扩展。完成搜索的过程就是找到一条从根结点到目标结点的路径，找出一个最优的解，这种搜索算法的实现类似于图或树的遍历。4.1 关于搜索算法由图4-2可以知道，搜索树的初始状态对1状态空间图2回溯算法、贪婪算法3旅行销售员问题4深度优先、广度优先搜索第2节5迭代加深搜索1状态空间图2回溯算法、贪婪算法3旅行销售员问题4深度优先、4.2 盲目搜索我们来学习基本的搜索算法，即“盲目搜索”，或者称为“无信息搜索”，又叫非启发式搜索。所谓无信息

5、搜索，意味着该搜索策略没有超出问题定义提供的状态之外的附加信息，所能做的就是生成后继节点并且区分一个目标状态或一个非目标状态。所有的搜索策略是由节点扩展的顺序加以区分。这些算法不依赖任何问题领域的特定知识，一般只适用于求解比较简单的问题，且通常需要占用大量的空间和时间。例如，假设你正在迷宫中找出路，在盲目搜索中，你可能总是选择最左边的路线，而不考虑任何其他可替代的选择。4.2 盲目搜索我们来学习基本的搜索算法，即“盲目搜索”，4.2 盲目搜索盲目搜索通常是按预定的搜索策略进行搜索，而不会考虑到问题本身的特性。常用的盲目搜索有广度优先搜索（Breadth First Search, BFS）和深

6、度优先搜索（Depth First search, DFS）两种。4.2 盲目搜索盲目搜索通常是按预定的搜索策略进行搜索，而4.2.1 状态空间图状态空间图（statc-space graph）是一个有助于形式化搜索过程的数学结构，是对一个问题的表示，通过问题表示，人们可以探索和分析通往解的可能的可替代路径。特定问题的解将对应状态空间图中的一条路径。有时候，我们要搜索一个问题的任意解；而有时候，我们希望得到一个最短（最优）的解。在计算机科学领域里，有一个著名的假币问题。有12枚硬币，己知其中一枚是假的或是伪造的，但是还不知道假币是比其他真币更轻还是更重。普通的秤可以用于确定任何两组硬币的质量，

7、即一组硬币比另一组硬币更轻或更重。为了解决这个问题，你应该创建一个程序，通过称量三组硬币的组合，来识别假币。4.2.1 状态空间图状态空间图（statc-space 4.2.1 状态空间图下面，我们就来解决一个相对简单的问题实例，假设只涉及到6枚硬币；与上述的原始问题一样，它也需要比较三组硬币，由于在这种情况下，任何一组的硬币枚数相对较少，我们称之为最小假币问题。我们使用符号Ci1Ci2Cir : Cj1Cj2Cjr来指示r枚硬币，比较Ci1Ci2Cir与另r枚硬币Cj1Cj2Cjr的质量大小。结果是，要么这两组硬币同样重，要么不一样重。我们不需要进一步知道左边盘子的硬币是否比右边盘子的硬币更

8、重或是更轻（如果要解决这个问题的12枚硬币的版本，就需要知道其他知识）。最后，我们采用记号 Ck1Ck2Ckm 来指示具有m枚硬币的子集是所知道的包含了假币的最小硬币集合。图4-3给出了这个最小假币问题的一个解。4.2.1 状态空间图下面，我们就来解决一个相对简单的问题4.2.1 状态空间图如图4-3所示，状态空间树由节点和分支组成。一个椭圆是一个节点，代表问题的一个状态。节点之间的弧表示将状态空间树移动到新节点的算符（或所应用的算符）。请参考图4-3中标有（*）的节点。这个节点 C1C2C3C4 表示假币可能是C1、C2、C3或C4中的任何一个。我们决定对C1和C2以及C5、C6之间的质量大

9、小（应用算符）进行比较。如果结果是这两个集合中的硬币质量相等，那么就知道假币必然是C3或C4中的一个；如果这两个集合中的硬币质量不相等，那么可以确定C1或C2是假币。为什么呢？状态空间树中有两种特殊类型的节点。第一个是表示问题起始状态的起始节点。4.2.1 状态空间图如图4-3所示，状态空间树由节点和分4.2.1 状态空间图在图4-3中，起始节点是 C1C2C3C4C5C6，这表明起始状态时，假币可以是6枚硬币中的任何一个。另一种特殊类型的节点对应于问题的终点或最终状态。图4-3中的状态空间树有6个终端节点，每个标记为 Ci (i=1, , 6)，其中i的值指定了哪枚是假币。问题的状态空间树包

10、含了问题可能出现的所有状态以及这些状态之间所有可能的转换。事实上，由于回路经常出现，这样的结构通常称为状态空间图。问题的解通常需要在这个结构中搜索（无论它是树还是图），这个结构始于起始节点，终于终点或最终状态。有时候，我们关心的是找到一个解（不论代价）；但有时候，我们可能希望找到最低代价的解。4.2.1 状态空间图在图4-3中，起始节点是 C1C24.2.1 状态空间图图4-3 最小假币问题的解4.2.1 状态空间图4.2.1 状态空间图说到解的代价，我们指的是到达目标状态所需的算符的数量，而不是实际找到此解所需的工作量。相比计算机科学，解的代价等同于运行时间，而不是软件开发时间。到目前为止，

11、我们不加区别地使用了节点和状态这两个术语。但是，这是两个不同的概念。通常情况下，状态空间图可以包含代表相同问题状态的多个节点（见图4-4）。回顾最小假币问题可知，通过对两个不同集合的硬币进行称重，可以到达表示相同状态的不同节点。4.2.1 状态空间图说到解的代价，我们指的是到达目标状态4.2.1 状态空间图图4-4 状态空间图中的不同节点可以表示相同的状态4.2.1 状态空间图4.2.1 状态空间图在求解过程中，可以有意忽略系统的某些细节，这样就可以允许在合理的层面与系统进行交互，这就是抽象。例如，如果你想玩棒球，那么抽象就可以更好地让你练习如何打弧线球，而不是让你花6年时间成为研究物体如何移

12、动的力学方面的博士。4.2.1 状态空间图在求解过程中，可以有意忽略系统的某些4.2.2 回溯算法回溯算法是所有搜索算法中最为基本的一种算法，它采用一种“走不通就掉头”思想作为其控制结构，相当于采用了先根遍历的方法来构造解答树，可用于找解或所有解以及最优解。例如，在一个MM的棋盘上某一点上有一个马，要求寻找一条从这一点出发不重复的跳完棋盘上所有的点的路线。回溯将搜索分成若干步骤，在每个步骤中按照规定的方式做出选择。如果问题的约束条件得到了满足，那么搜索将进行到下一步；如果没有选项可以得到有用的部分解，那么搜索将回溯到前一个步骤，撤销前一个步骤的选择，继续下一个可能的选择。4.2.2 回溯算法回

13、溯算法是所有搜索算法中最为基本的一种4.2.2 回溯算法回溯算法对空间的消耗较少，当其与分支定界法一起使用时，对于所求解在解答树中层次较深的问题有较好的效果。但应避免在后继节点可能与前继节点相同的问题中使用，以免产生循环。4.2.2 回溯算法回溯算法对空间的消耗较少，当其与分支定4.2.3 贪婪算法贪婪算法也是先将一个问题分成几个步骤进行操作。贪婪算法总是包含了一个已优化的目标函数（例如，最大化或最小化）。典型的目标函数可以是行驶的距离、消耗的成本或流逝的时间。4.2.3 贪婪算法贪婪算法也是先将一个问题分成几个步骤进4.2.3 贪婪算法图4-5代表了中国几个城市的地理位置。假设销售人员从成都

14、开始，想找到去哈尔滨的一条最短路径，这条路径只经过成都（V1）、北京（V2）、哈尔滨（V3）、杭州（V4）和西安（V5）。这5个城市之间的距离以千米表示。 图4-5 5个城市，假设了城市之间的空中距离，这些城市彼此之间直接相连4.2.3 贪婪算法图4-5代表了中国几个城市的地理位置。4.2.3 贪婪算法在步骤1中，贪婪方法从成都行进到西安，因为这两个城市的距离只有606km，西安是最近的城市。（l）在步骤1中，采用V1到5的路径，因为西安是离成都最近的城市。（2）只有是先前已经访问过的顶点，我们才可以考虑经过该顶点的路径。在步骤2中，下一个生成的路径直接从V1到V2，它的代价（距离）是1518

15、km。这条直接的路径比通过V3的路径便宜，代价为606km+914km=1520km。4.2.3 贪婪算法在步骤1中，贪婪方法从成都行进到西安，4.2.3 贪婪算法（3）V1到3便宜的路径是使用从V1到中间节点（Vi）以及从Vi到V3的最便宜的路径构成的。此处，I等于V2；V1到V3代价最小的路径经过了V2，其代价为1518km+1061km=2579km。然而，V1到V4的直接路径代价较低（1539hn）。我们直接去了V4（杭州）。4.2.3 贪婪算法（3）V1到3便宜的路径是使用从V14.2.3 贪婪算法（4）步骤4：我们正在搜索从V1开始到任何地方的下一条代价最小路径。我们己经得到了V1

16、到V5的代价最小路径，其代价为606km。第二条代价最小路径为V1到V2的直接路径，代价为1518km。V1到4的直接路径（1539km）比经过V5的路径（606km+1l50km=1756km）以及经过V2的路径（1518km+1134km=2652km），其代价最低。因此，下一条代价最小路径是那条经过V3的路径（2579km）。4.2.3 贪婪算法（4）步骤4：我们正在搜索从V1开始到4.2.3 贪婪算法这里有几种可能性：V1到V5（代价=606km），然后V5到V2（代价=914km），即从V1到V2，经过V5的代价是1520km。然后，你需要从V2到V3（代价为1061km）。从V1到

17、V3，经过V5和V2的路径，其总代价是1520km+1061km=2581km。V1到V2的代价为15181m，V2到V3的代价为1061km，这条路径的总代价为2579km。V1到V4的代价为1539km，V4到V3的代价为1822km，这条路径的总代价为3361km。4.2.3 贪婪算法这里有几种可能性：4.2.3 贪婪算法我们采用从V1到V3的路径，这条路径首先经过V2，总代价为2579km。这个例子采用的特定算法是Dijkstra的最短路径算法，这个算法是贪婪算法的一个例子。使用贪婪算法求解问题效率很高，但有一些问题不能使用这种范式求解，例如旅行销售员问题。4.2.3 贪婪算法我们采用

18、从V1到V3的路径，这条路径首4.2.4 旅行销售员问题在旅行销售员问题的加权图（即边具有代价的图）中，给定n个顶点，你必须找到始于某个顶点Vi，有且只有一次经过图中的每个顶点，然后返回Vi的最短路径。就用前面5个城市的例子。假设销售员住在西安，因此必须按照某种次序依次访问成都、北京、杭州和哈尔滨，然后回到西安。在寻求代价最小的路径时，旅行销售员问题基于贪婪算法的解总是访问下一个最近的城市。4.2.4 旅行销售员问题在旅行销售员问题的加权图（即边具4.2.4 旅行销售员问题贪婪算法访问成都、北京、哈尔滨、杭州，然后终于回到西安。这个路径的代价是606km + 1518km + 1061km +

19、 1822km + 1050km = 6057km。如果销售人员访问依次北京、哈尔滨、杭州、成都，然后返回西安，那么总累计代价为914km + 1061km + 1822km + 1539km + 606km = 5942km。显然，贪婪算法未能找到最佳路径。4.2.4 旅行销售员问题贪婪算法访问成都、北京、哈尔滨、4.2.5 深度优先搜索盲目搜索是不使用领域知识的不知情搜索算法。这些方法假定不知道状态空间的任何信息。3种主要算法是：深度优先搜索（DFS）、广度优先搜索（BFS）和迭代加深（DFS-ID）的深度优先搜索。这些算法都具有如下两个性质：（1）它们不使用启发式估计。如果使用启发式估计

20、，那么搜索将沿着最有希望得到解决方案的路径前进。（2）它们的目标是找出给定问题的某个解。4.2.5 深度优先搜索盲目搜索是不使用领域知识的不知情搜4.2.5 深度优先搜索深度优先搜索（DFS），顾名思义，就是试图尽可能快地深入树中。每当搜索方法可以做出选择时，它选择最左（或最右）的分支（通常选择最左分支）。可以将图4-6所示的树作为DFS的一个例子。图4-6 树的深度优先搜索遍历4.2.5 深度优先搜索深度优先搜索（DFS），顾名思义，4.2.5 深度优先搜索将按照A、B、D、E、C、F、G的顺序访问节点树的遍历算法将多次“访问”某个节点，例如，在图4-6中，依次访问A、B、D、B、E、B、A

21、、C、F、C、G。4.2.5 深度优先搜索将按照A、B、D、E、C、F、G的4.2.5 深度优先搜索深度优先搜索的基本思想是：从初始节点S0开始进行节点扩展，考察S0扩展的最后1个子节点是否为目标节点，若不是目标节点，则对该节点进行扩展；然后再对其扩展节点中的最后1个子节点进行考察，若又不是目标节点，则对其进行扩展，一直如此向下扩展。当发现节点本身不能扩展时，对其1个兄弟节点进行扩展；如果所有的兄弟节点都不能够扩展时，则寻找到它们的父节点，对父节点的兄弟节点进行扩展；依次类推，直到发现目标状态Sg为止。因此，深度优先搜索法存在搜索和回溯交替出现的现象。4.2.5 深度优先搜索深度优先搜索的基本

22、思想是：从初始节4.2.5 深度优先搜索DFS采用不同的策略来达到目标：在寻找可替代路径之前，它追求寻找单一的路径来实现目标，搜索一旦进入某个分支，就将沿着该分支一直向下搜索。如果目标节点恰好在此分支上，则可较快地得到问题解。但若目标节点不在该分支上，且该分支又是一个无穷分支，就不可能得到解。所以，DFS是不完备搜索。DFS内存需求合理，但是它可能会因偏离开始位置无限远而错过了相对靠近搜索起始位置的解。4.2.5 深度优先搜索DFS采用不同的策略来达到目标：在4.2.6 广度优先搜索广度优先搜索（BFS，又称宽度优先搜索）是第二种盲目搜索方法。使用BFS，从树的顶部到树的底部，按照从左到右的方

23、式（或从右到左，不过一般来说从左到右），可以逐层访问节点。要先访问层次i的所有节点，然后才能访问在i+1层的节点。图4-7显示了BFS的遍历过程。按照以下顺序访问节点：A、B、C、D、E、F、G。图4-7 树的广度优先遍历4.2.6 广度优先搜索广度优先搜索（BFS，又称宽度优先4.2.6 广度优先搜索广度优先搜索的基本思想是：从初始节点S0开始进行节点扩展，考察S0的第1个子节点是否为目标节点，若不是目标节点，则对该节点进行扩展；再考察S0的第2个子节点是否为目标节点，若不是目标节点，则对其进行扩展；对S0的所有子节点全部考察并扩展以后，再分别对S0的所有子节点的子节点进行考察并扩展，如此向

24、下搜索，直到发现目标状态Sg为止。因此，广度优先搜索在对第n层的节点没有全部考察并扩展之前，不对第n+1层的节点进行考察和扩展。4.2.6 广度优先搜索广度优先搜索的基本思想是：从初始节4.2.6 广度优先搜索在继续前进之前，BFS在离开始位置的指定距离处仔细查看所有替代选项。BFS的优点是，如果一个问题存在解，那么BFS总是可以得到解，而且得到的解是路径最短的，所以它是完备的搜索。但是，如果在每个节点的可替代选项很多，那么BFS可能会因需要消耗太多的内存而变得不切实际。BFS的盲目性较大，当目标节点离初始节点较远时，会产生许多无用节点，搜索效率低。4.2.6 广度优先搜索在继续前进之前，BFS在离开始位置4.2.7 迭代加深搜索深