人工智能与未来 课件 4.3 搜索算法

Algorithm第4章

算法2035主讲：王红梅4.14.24.34.4算法那些事算法概述搜索算法机器学习目录CONTENTS4.5神经网络与深度学习扩展：循环神经网络4.6讨论：现实生活中你用过那些搜索？你是否了解这些搜索背后的算法呢？图书馆查书

小智今天计划外出一趟，习惯性的用地图导航一下，和之前不一样的是，这次导航小智多了个想法，由于开始学习算法了，小智就琢磨地图是怎么在众多路径中找到最短路径的？又是怎么实现最快达到的呢？其实地图导航的基本算法是Dijkstra算法和A*（AStar）搜索算法，分别用来解决小智如何找到最短路径和如何实现快速达到的问题。

4.3.1基于图的搜索1.图的构建

你每天是不是往返于学校的宿舍、餐厅、教学楼、图书馆、实验楼和运动场等场地之间，各个场地之间的连线表示它们之间有路，这样就构成了无向图。A：代表宿舍，用B代表餐厅，用C代表图书馆，用D代表教学楼，E代表实验楼，F代表运动场；各个场所的距离用连线上的数字表示（也称为权值）。注意：这里线的长短并不代表距离的远近，数字才代表距离的远近。

4.3.1基于图的搜索2.图的搜索

图的搜索指的就是从图的某个顶点开始，到达其它顶点的方法和过程，如图中，从A点出发，分别达到B、C、D、E、F顶点的过程。根据搜索的顺序不同，图的搜索算法可分为广度优先搜索和深度优先搜索这两种。实际上这两种方法即可以进行图的搜索，也可以进行树的搜索。4.3.2广度优先搜索*广度优先搜索（Breadth-FirstSearch,BFS）是一种用于遍历或搜索树或图的算法。该算法从根节点开始，逐层遍历树或图的分支，直到找到目标节点或无法再前进为止。（每一层有点像海浪的一波）4.3.2广度优先搜索*6个顶点组成的图如（a），现在从A点开始进行搜索，设想一下，组成各个点之间的线可以伸缩，我们拎着A点，其它顶点位置根据和A的远近自然下垂，效果如图（b）所示。当然，你也发现了，只是重新调整一下各个顶点的位置，它们的结构并没有改变。4.3.2广度优先搜索*搜索的步骤如下，蓝色是当前访问节点，灰色是已经访问节点：4.3.3深度优先搜索*深度优先搜索和广度优先搜索一样，都是对图进行搜索的算法。不同的是深度优先搜索会沿着一条路径不断往下搜索直到不能再继续为止，然后再折返，开始搜索下一条路径。4.3.3深度优先搜索*同样，为了方便理解，我们对原始图（a）以A为起点，根据能探索的深度来进行调整形状，同样只是调整位置，并没有改变结构，4.3.3深度优先搜索*深度优先搜索详细步骤：4.3.3深度优先搜索*深度优先搜索详细步骤：4.3.4最短路径算法Dijkstra最短路径算法，属于广度优先搜索的一种。该算法是求从一个顶点到其余各顶点的最短路径算法，解决的是有权图中最短路径问题。Dijkstra算法的策略实际上采用贪心算法策略，贪心算法的基本思想是每一步都选择当前状态下的最优选择，希望通过局部最优解的累积最终得到全局最优解‌。4.3.4最短路径算法策略(贪心算法的一种）：每次选择一个点，这个点满足两个条件：1、未被访问过；2、到源点距离最短这个点就是一个全局最优解！后续这个点到源点的距离是不需要修改的！！通过局部最优解获得全局最优解。求a到其他点的最短路径。每次选距离a最近的点，然后更新。第1次第2次第3次第4次第5次b2（a，b）c5（a，c）d∞e∞f∞最短路径∞表示没有直接相连的点。最短路径就是那些点最短距离eabcdf21541134314.3.4最短路径算法求a到其他点的最短路径。每次选距离a最近的点，然后更新。第1次第2次第3次第4次第5次b2（a，b）c5（a，c）d∞e∞f∞最短路径2（a，b）∞表示没有直接相连的点。最短路径就是那些点最短距离eabcdf21541134314.3.4最短路径算法求a到其他点的最短路径。每次选距离a最近的点，然后更新。第1次第2次第3次第4次第5次b2（a,b）c5（a,c）3（a,b,c）d∞5（a,b,d）e∞∞f∞∞最短路径2（a,b）∞表示没有直接相连的点。最短路径就是那些点最短距离eabcdf21541134314.3.4最短路径算法求a到其他点的最短路径。每次选距离a最近的点，然后更新。第1次第2次第3次第4次第5次b2（a,b）c5（a,c）3（a,b,c）d∞5（a,b,d）e∞∞f∞∞最短路径2（a,b）3（a,b,c）∞表示没有直接相连的点。最短路径就是那些点最短距离eabcdf21541134314.3.4最短路径算法求a到其他点的最短路径。每次选距离a最近的点，然后更新。第1次第2次第3次第4次第5次b2（a,b）c5（a,c）3（a,b,c）d∞5（a,b,d）5（a,b,d）e∞∞7（a,b,c,e）f∞∞4（a,b,c,f）最短路径2（a,b）3（a,b,c）4（a,b,c,f）∞表示没有直接相连的点。最短路径就是那些点最短距离eabcdf2154113431由于,6（a,b,c,d）是，大于5（a,b,d），用短的距离4.3.4最短路径算法求a到其他点的最短路径。每次选距离a最近的点，然后更新。第1次第2次第3次第4次第5次b2（a,b）c5（a,c）3（a,b,c）d∞5（a,b,d）5（a,b,d）e∞∞7（a,b,c,e）f∞∞4（a,b,c,f）最短路径2（a,b）3（a,b,c）4（a,b,c,f）∞表示没有直接相连的点。最短路径就是那些点最短距离eabcdf21541134314.3.4最短路径算法求a到其他点的最短路径。每次选距离a最近的点，然后更新。第1次第2次第3次第4次第5次b2（a,b）c5（a,c）3（a,b,c）d∞5（a,b,d）5（a,b,d）5（a,b,d）e∞∞7（a,b,c,e）7（a,b,c,e）f∞∞4（a,b,c,f）最短路径2（a,b）3（a,b,c）4（a,b,c,f）5（a,b,d）∞表示没有直接相连的点。最短路径就是那些点最短距离eabcdf2154113431f没有去向的路径，数据不更新4.3.4最短路径算法求a到其他点的最短路径。每次选距离a最近的点，然后更新。第1次第2次第3次第4次第5次b2（a,b）c5（a,c）3（a,b,c）d∞5（a,b,d）5（a,b,d）5（a,b,d）e∞∞7（a,b,c,e）7（a,b,c,e）f∞∞4（a,b,c,f）最短路径2（a,b）3（a,b,c）4（a,b,c,f）5（a,b,d）∞表示没有直接相连的点。最短路径就是那些点最短距离eabcdf21541134314.3.4最短路径算法求a到其他点的最短路径。每次选距离a最近的点，然后更新。第1次第2次第3次第4次第5次b2（a,b）c5（a,c）3（a,b,c）d∞5（a,b,d）5（a,b,d）5（a,b,d）e∞∞7（a,b,c,e）7（a,b,c,e）6（a,b,d,e）f∞∞4（a,b,c,f）最短路径2（a,b）3（a,b,c）4（a,b,c,f）5（a,b,d）eabcdf21541134314.3.4最短路径算法求a到其他点的最短路径。每次选距离a最近的点，然后更新。第1次第2次第3次第4次第5次b2（a,b）c5（a,c）3（a,b,c）d∞5（a,b,d）5（a,b,d）5（a,b,d）e∞∞7（a,b,c,e）7（a,b,c,e）6（a,b,d,e）f∞∞4（a,b,c,f）最短路径2（a,b）3（a,b,c）4（a,b,c,f）5（a,b,d）6（a,b,d,e）eabcdf21541134314.3.4最短路径算法求a到其他点的最短路径。每次选距离a最近的点，然后更新。第1次第2次第3次第4次第5次b2（a,b）c5（a,c）3（a,b,c）d∞5（a,b,d）5（a,b,d）5（a,b,d）e∞∞7（a,b,c,e）7（a,b,c,e）6（a,b,d,e）f∞∞4（a,b,c,f）最短路径2（a,b）3（a,b,c）4（a,b,c,f）5（a,b,d）6（a,b,d,e）eabcdf21541134314.3.4最短路径算法求a到其他点的最短路径。每次选距离a最近的点，然后更新。第1次第2次第3次第4次第5次b2（a,b）c5（a,c）3（a,b,c）d∞5（a,b,d）5（a,b,d）5（a,b,d）e∞∞7（a,b,c,e）7（a,b,c,e）6（a,b,d,e）f∞∞4（a,b,c,f）最短路径2（a,b）3（a,b,c）4（a,b,c,f）5（a,b,d）6（a,b,d,e）eabcdf211134.3.4最短路径算法讨论和分享：科学家故事：最短路径算法发明人Dijkstra的故事4.3.5A*搜索算法Dijkstra算法求最短路径的时候，会从离起点近的顶点开始，按顺序求出起点到各个顶点的最短路径，也就是说，一些离终点较远的顶点的最短路径也会被计算出来，但这样做，有时候是无用而且浪费时间的；你试想一下，如果你在郑州，你的目的地是北京，你从郑州搜索到上海或广州的路径没有太大价值。4.3.5A*搜索算法我们会发现广度优先搜索，当数据量很大的时候，它的搜索性能就低下，如何进行优化呢？在实际的应用过程中，基于启发式搜索的A*搜索就是常用的一种方法。A*搜索就是在状态空间中的搜索对每一个搜索的位置进行评估，得到最好的位置，再从这个位置进行搜索直到目标。这样可以省略大量无畏的搜索路径，提高了效率。4.3.5A*搜索算法AB寻找一条从起点A到终点B的路径，只能上下左右的移动，而且不能穿越障碍物。红色的方块是代表障碍物4.3.5A*搜索算法1111AB如果按照广度优先搜索的方法，它是朝4个方向进行搜索。搜索过的地方用灰色来标注。4.3.5A*搜索算法22121122122AB按广度优先搜索，会从A点朝4个方向进行搜索。并且会标记这4探索的方向为边界，就是图中绿色的部分。以这些边界为检索点重复进行。搜索过的地方用灰色来标注。4.3.5A*搜索算法323212112212323AB按广度优先搜索，会从A点朝4个方向进行搜索。并且会标记这4探索的方向为边界，就是图中绿色的部分。以这些边界为检索点重复进行。搜索过的地方用灰色来标注。4.3.5A*搜索算法3234212112123234AB按广度优先搜索，会从A点朝4个方向进行搜索。并且会标记这4探索的方向为边界，就是图中绿色的部分。以这些边界为检索点重复进行。搜索过的地方用灰色来标注。4.3.5A*搜索算法3234521211221232345AB按广度优先搜索，会从A点朝4个方向进行搜索。并且会标记这4探索的方向为边界，就是图中绿色的部分。以这些边界为检索点重复进行。搜索过的地方用灰色来标注。4.3.5A*搜索算法32345621261122126323456AB按广度优先搜索，会从A点朝4个方向进行搜索。并且会标记这4探索的方向为边界，就是图中绿色的部分。以这些边界为检索点重复进行。搜索过的地方用灰色来标注。4.3.5A*搜索算法323456721267112212673234567AB按广度优先搜索，会从A点朝4个方向进行搜索。并且会标记这4探索的方向为边界，就是图中绿色的部分。以这些边界为检索点重复进行。搜索过的地方用灰色来标注。4.3.5A*搜索算法32345678212678112821267832345678AB按广度优先搜索，会从A点朝4个方向进行搜索。并且会标记这4探索的方向为边界，就是图中绿色的部分。以这些边界为检索点重复进行。搜索过的地方用灰色来标注。4.3.5A*搜索算法32345678212678911289212678932345678AB按广度优先搜索，会从A点朝4个方向进行搜索。并且会标记这4探索的方向为边界，就是图中绿色的部分。以这些边界为检索点重复进行。搜索过的地方用灰色来标注。4.3.5A*搜索算法AB最短路径就是上面一次探索过的路径。橘黄色方块。可以看到广度搜索算法是可以帮我们找到最短路径的。4.3.5A*搜索算法AB不过有点傻。为什么说呢？因为它是没有方向性的。在最坏的情况下可能需要找遍整个地图才能找到最短路径，那怎么有更好的方法呢？那就是我们接下来要说的A*算法。4.3.5A*搜索算法↑←→↓ABA*搜索不会去探索所有的边界，而是去选择当前“代价”最低的边界进行探索。也就是选择一个有方向性的边界进行探索。在四个方向的边界中，而

才是“代价”最低的边界。→4.3.5A*搜索算法路径代价=当前代价

（F-cost)+预估代价（G-cost)目前实际走的步数当前方块到终点方块大概需要的步数作用是指导算法进行优化搜索4.3.5A*搜索算法路径代价=当前代价

（F-cost)+预估代价（G-cost)欧氏距离（欧几里得距离），就是两组之间的直线距离，公式：(x1-x2)2+(y1-y2)2曼哈顿距离，就是两点在竖直和水平方向上的距离总和公式为：∣x1-x2∣+∣y1-y2∣预估代价在预估距离时，常用方法4.3.5A*搜索算法1+61+61+41+6BA在四个方向的边界中，计算路径代价F+G（当前代价+预估代价）。4.3.5A*搜索算法1+61+61+41+6AB选择最低代价。4.3.5A*搜索算法1+62+51+61+42+31+62+5BA从最低代价的边界出发，计算各个方向的路径代价F+G（当前代价+预