1、A1 最短路问题及相关算法介绍吕长虹吕长虹华东师范大学数学系华东师范大学数学系Email:A2vQuestion one：v每天开车去上班，应该走那条使得达到公司的费用最每天开车去上班，应该走那条使得达到公司的费用最低、时间最少呢，如何选择最优的路径呢？低、时间最少呢，如何选择最优的路径呢？A3vQuestion two：v在城市规划自己电网架设中，怎么设计才能使其耗费在城市规划自己电网架设中，怎么设计才能使其耗费的资金最少？的资金最少？A4v 其实都涉及到一个相同的问题：最短路问题！其实都涉及到一个相同的问题：最短路问题！A5v最短路问路径不仅仅是一般地理意义上的距离最短，还可以最短路问路径
2、不仅仅是一般地理意义上的距离最短，还可以延伸到其他度量，如时间、费用、线路容量等，相应的最短延伸到其他度量，如时间、费用、线路容量等，相应的最短路问题就转化诶最快路径问题、最低费用问题。路问题就转化诶最快路径问题、最低费用问题。v最短路径问题也是资源分配，线路设计及分析等优化问题的最短路径问题也是资源分配，线路设计及分析等优化问题的基础。基础。A6 图论中的最短路问题图论中的最短路问题(shortest route problem)(shortest route problem)是组合是组合数学和图论中核心问题之一，是许多更深层次算法的数学和图论中核心问题之一，是许多更深层次算法的基础。基础。
3、A7v图的定义：图的定义：v图是一种由图是一种由“顶点顶点”组成的抽象网络，网络中的各顶点可以组成的抽象网络，网络中的各顶点可以通过通过“边边”实现彼此的连接，表示两顶点有关联。实现彼此的连接，表示两顶点有关联。图一般用图一般用G来表示，其顶点集为来表示，其顶点集为V，边集为，边集为E，简述为，简述为G=(V,E)。右图就是图论中一个节点的图结构，一共右图就是图论中一个节点的图结构，一共有有10个顶点，个顶点，15条边。条边。Petersen图A8v最短路问题就是在指定的网络中两个节点间寻找一条距离最最短路问题就是在指定的网络中两个节点间寻找一条距离最小的路。小的路。v网络就是用节点和边联结构
4、成的网络就是用节点和边联结构成的图图，如铁路网、公路网等。，如铁路网、公路网等。下图就是我们将一个实际区域结构，图结构化的结果。下图就是我们将一个实际区域结构，图结构化的结果。A9v两种常见最短路问题：两种常见最短路问题：v1、单源最短路问题：求某一个到其余个点的最短路问题？、单源最短路问题：求某一个到其余个点的最短路问题？v-dijkstra算法算法v2、多源最短路问题：求任意两点之间最短路问题？、多源最短路问题：求任意两点之间最短路问题？v-Floyd算法算法A10vDijkstra算法更是被称为统治世界的十大算法之一。算法更是被称为统治世界的十大算法之一。A11v最短路算法一个经典应用：
5、导航最短路算法一个经典应用：导航v我们在百度地图上寻找驾车路径时，显然就是要寻找一条物我们在百度地图上寻找驾车路径时，显然就是要寻找一条物理距离最短或者行驶时间最短的路线。理距离最短或者行驶时间最短的路线。v那我们能否通过算法设计一个属于我们的导航呢？那我们能否通过算法设计一个属于我们的导航呢？vDijkstra算法就可以帮助我们做到这一点！算法就可以帮助我们做到这一点！A12问题简述问题简述 现有在无向图现有在无向图 G=(V,E)，V为各顶点的集合，为各顶点的集合，E边集合，边集合，W为每条路径的权值，满足为每条路径的权值，满足权值大于零。需要求得从某权值大于零。需要求得从某个起始点个起始
6、点v,到其余各点的最到其余各点的最短路径。短路径。A13Dijkstra算法算法算法描述算法描述A14Dijkstra算法描述把图中顶点集合V分成两组 第一组为已求出最短路径的顶点集合已求出最短路径的顶点集合（用S表示，初始时S中只有一个源点，以后每求得一条到其余顶点的最短路径,就将加入到集合S中，直到全部顶点都加入到S中，算法就结束了）第二组为其余未确定最短路径的顶点集合未确定最短路径的顶点集合（用U表示），按最短路径长度的递增次序依次把第二组的顶点加入S中。在加入的过程中，总保持从源点v到S中各顶点的最短路径长度不大于从源点v到U中任何顶点的最短路径长度。此外，每个顶点对应一个距离，每个顶
7、点对应一个距离，S中的顶点的距离中的顶点的距离就是从就是从v到此顶点的最短路径长度，到此顶点的最短路径长度，U中的顶点的距中的顶点的距离，是从离，是从v到此顶点只包括到此顶点只包括S中的顶点为中间顶点的中的顶点为中间顶点的当前最短路径长度。当前最短路径长度。A15Dijkstra算法算法步骤步骤从U中选取一个距离v最小的顶点k，把k，加入S中（该选定的距离就是v到k的最短路径长度）。二二重复步骤二和三直到所有顶点都包含在S中。四四以k为新考虑的中间点，修改U中各顶点的距离；若从源点v到顶点u的距离（经过顶点k）比原来距离（不经过顶点k）短，则修改顶点u的距离值，修改后的距离值的顶点k的距离加上
8、边上的权。三三初始时，S只包含源点，即Sv，v的距离为0。U包含除v外的其他顶点，即:U=其余顶点，若v与U中顶点u有边，则正常有权值，若u不是v的出边邻接点，则权值为。一一A16v算法的描述上看去相当复杂，我们给出下面例子来具体说明整个算法的运行流程！A17v首先我们要有如下概念：v假设P：vkm是从顶点v到km的一条最短路径，那对这条路径上任意其他一点ki，都有 P上关于v ki的子路径为v到点ki的最短路径。v即最短路径的子路径仍然是最短路径，最短路算法本质上上基于这种思想展开的。A18经典例子经典例子A19 我们取源点为V1，即求V1到其余个点的最短距离。A20STEP1：开始阶段S=
9、V1，U=V2,V3,V4,V5,V6，W=(wij)66 为权值矩阵。向量D来记录每一步之后V1与其余各点之间的最短距离。初始阶段D=(0,7,9,14)。A21STEP2：将与V1距离最小的点V2放入S中，S=V1,V2，U=V3,V4,V5,V6，此时我们确定V1到V2之间的最短距离为7。计算V1与U中各点距离【必须最短路经过V2】，再与向量D中比较取较小值作为新的D中取值。S13=W23+D12=10+7=17S14=W24+D12=15+7=22D13=minS13,D13=min17,9=9,不变。D14=minS14,D14=min22,=22,变小。此时 D=(0,7,9,22
10、,14)A22STEP3：将与V1距离最小的点V3放入S中，S=V1,V2,V3，U=V4,V5,V6，此时我们确定V1到V3之间的最短距离为9。计算V1与U中各点距离【必须最短路经过V3】，再与向量D中比较取较小值作为新的D中取值。S14=W34+D13=11+9=20S16=W36+D13=2+9=11D14=minS14,D14=min20,22=20,变小。D16=minS16,D16=min11,14=11,变小。此时 D=(0,7,9,20,11)A23STEP4：将U中与V1距离最小的点V6放入S中，S=V1,V2,V3,V6，U=V4,V5，此时我们确定V1到V6之间的最短距离
11、为11。计算V1与U中各点距离【必须最短路经过V6】，再与向量D中比较取较小值作为新的D中取值。S15=W65+D1=11+9=20D15=minS15,D15=min20,=20,变小。此时 D=(0,7,9,20,20,11)A24STEP5：此时U中与V1距离最小的点为V4和V5放入S中，S=V1,V2,V3,V4,V5,V6，U=，此时我们确定V1到V4之间的最短距离为20，V1到V5之间的最短距离也为20。所有的点都在S中，算法终止！此时 D=(0,7,9,20,20,11)，就是V1到其余各个点的最短距离向量。A25 优点优点缺点缺点优点优点优点优点缺点缺点缺点效率低，需要遍历所有
12、点（特别是有时候不需要最优解）、运算中占用空间大缺点缺点算法简明易懂、并且一定能得到最优解优点优点Dijkstra算法可能不是最优先使用的方法，因为算法的运算速度效率，往往要比精确度更加重要实际运用实际运用A26这样利用这样利用Dijkstra算法设计一个属于我们自己的导航系统啦。算法设计一个属于我们自己的导航系统啦。但似乎在实际运行时效果并不理想！但似乎在实际运行时效果并不理想！A27v虽然算法本身就是最短路径，但路面交通变化复杂，由于路虽然算法本身就是最短路径，但路面交通变化复杂，由于路面施工导致道路封锁，同时还存在路堵、车祸等现象，导致面施工导致道路封锁，同时还存在路堵、车祸等现象，导致
13、算法输出的最优路径，实际上并不是我们想要的最优路径。算法输出的最优路径，实际上并不是我们想要的最优路径。A28路面道路封锁、路堵、车祸等现象，本质上可以理解为这条道路面道路封锁、路堵、车祸等现象，本质上可以理解为这条道路被封堵住了，即有一个障碍物出现在此处，阻碍我们继续前路被封堵住了，即有一个障碍物出现在此处，阻碍我们继续前进了！进了！A29v这时候我们这时候我们Dijkstra算法就失效了！算法就失效了！v有同学会问：去掉这条堵住的线段不就可以了？这样仍然可有同学会问：去掉这条堵住的线段不就可以了？这样仍然可以用以用Dijkstra算法求解。算法求解。v事实上这是一种可行的思路，但如果这样操
14、作每天我的导航事实上这是一种可行的思路，但如果这样操作每天我的导航系统就要花大量时间去进行线段删减、增加工作。系统维护系统就要花大量时间去进行线段删减、增加工作。系统维护成本增加！成本增加！A30vA*算法就是解决这类问题的一个有效算法。算法就是解决这类问题的一个有效算法。vA*算法可以理解成算法可以理解成Dijkstra算法算法+最佳优先搜索！最佳优先搜索！A31最佳优先搜索简介最佳优先搜索简介 这个算法的运算流程跟这个算法的运算流程跟Dijkstra的流程类似，的流程类似，只不过它考察只不过它考察的是的是选取选取点到终点的距离，并且这点到终点的距离，并且这个距离的权值是评估出来的个距离的权
15、值是评估出来的，这也，这也就就是是启发式启发式的思想的思想。举例说明，如。举例说明，如果说目标的终点在北面，那么越靠果说目标的终点在北面，那么越靠近北面的点权值就越小，那么算法近北面的点权值就越小，那么算法在搜索过程中，所加入点集的点就在搜索过程中，所加入点集的点就会倾向于北面，因此不用搜索全图会倾向于北面，因此不用搜索全图东南西北，更多的是搜索北面的点，东南西北，更多的是搜索北面的点，速度来说会优于速度来说会优于Dijkstra算法很多。算法很多。A32A*算法描述算法描述 A*算法将两种算法结合起来，最为关键算法将两种算法结合起来，最为关键的就是它判断权值大小的函数的就是它判断权值大小的函
16、数f(n)。它定义它定义f（n）=g(n)+h(n)。其中，。其中，g(n)为起始为起始点到任意节点点到任意节点n的权值的权值，在路径搜索中，也就，在路径搜索中，也就是说到是说到n点需要付出的代价，换句话说，之前点需要付出的代价，换句话说，之前所叙述的所叙述的Dijkstra算法。算法。h(n)表达的是从节点表达的是从节点n到终点的估计权值，也就是前面所陈述的最到终点的估计权值，也就是前面所陈述的最佳优先佳优先搜索搜索。从中可以看到，当从中可以看到，当h(n)=0的时候，这个算的时候，这个算法就是法就是Dijkstra算法，而当个算法，而当个g（n）=0的时候，的时候，这个算法就是最佳优先算法
17、。这个算法就是最佳优先算法。h(n)的值占比越的值占比越大，这个大，这个A*算法的启发度越高，也就越不精算法的启发度越高，也就越不精确，但运算很快。相对的确，但运算很快。相对的g(n)的占比高时，这的占比高时，这个算法更趋向于将全局的节点都加进点集进个算法更趋向于将全局的节点都加进点集进行对比，从而可以给出较优的解，但算法速行对比，从而可以给出较优的解，但算法速度会变慢。度会变慢。A33算法过程算法过程1.设定三个集合close list,open list,parent node，其中，close list中记录已经搜寻过的点，open list中记录等待搜寻的点，parent node 则
18、是用来记录搜寻的路径，最后回推找到结果路径；2.将起始点放入openlist，此时closelist与parentnode为空集；3.在openlist中选一个f(n)值最小的点作为当前的节点；4.将其从openlist中移除，添加到closelist中；5.如果当前节点为终点，那么搜索结束；6.搜索当前节点的相邻节点；7.如果相邻节点不在openlist中，就将它添加到openlist中，并将当前点设为parentnode；8.如果当前节点已经在openlist中，那么重新计算g值，如果g值小于当前节点的g值，那么更新这个值并且更新parentnode；9.如果当前节点在closelist中
19、或者无法通过，那么就不处理它；10.如果openlist没有终点或所在水平线两侧的相邻点，那么跳转到3步骤；如果有终点或所在水平线两侧的相邻点中的任何一个，则将其设为终点并结束完成当前任务规划。A34经典例子经典例子 我们需要从绿色格子搜寻路径到红色格子，我们假定横向、纵向移动的权值为10，对角线移动权值为14。格子的左上角是f(n),左下角为g(n),右下角为h(n)的值此处使用 Manhattan 方法估计h取值，计算从当前方格横向或纵向移动到达目标所经过的方格数，忽略对角移动，然后把总数乘以 10。说明：对于障碍物存在的地方，我们认为无法通过，即不能经过任何和障碍有关的地方，甚至是单个点
20、。所以对角线也无法走！A35初始搜索过程：1、起点 A 开始，open list=A；2、查看与起点 A 相邻的方格(忽略其中墙壁所占领的方格)，把其中可走的方格也加入到 open list 中，此时open list=A、A1，A2，A3，A4，A5，A6，A7，A8;3、设置这些新加入点的父亲为A；4、更新open list和close list，open list=A1，A2，A3，A4，A5，A6，A7，A8，close list=A；5、计算每个新加入open list点的F,G,H值，并标注在相应位置；AA1A2A3A4A5A6A7A8A36下一步搜索的方格1、从 open lis
21、t 中选择 F 值最小的(方格)节点A1；2、更新open list和close list，open list=A2，A3，A4，A5，A6，A7，A8，close list=A，A1；3、检查所有与它相邻的方格，忽略其中在 close list 中或是不可走的方格，如果方格不在open lsit 中，则把它们加入到 open list对于A1点来说并没有新的点要加入到open list；4、检查原先open list中点A2，A3，A7，A8在通过A1到达的G值是否更小？显然没有，所以不做任何变化！AA1A2A3A4A5A6A7A8A37下一步搜索的方格1、从 open list 中选择 F
22、 值最小的(方格)节点A2；A2和A8取值一样，随机选择一个都可以。2、更新open list和close list，open list=A3，A4，A5，A6，A7，A8，close list=A，A1，A2；3、检查所有与它相邻的方格，忽略其中在 close list 中或是不可走的方格，如果方格不在open lsit 中，则把它们加入到 open list，open list=A3，A4，A5，A6，A7，A8，A9，A10；4、新加入点A9，A10的父亲节点设为A2，并计算相应F,G,H值；5、检查原先在open list中的点A1，A3通过A2到达的G值是否更小？显然没有，所以对这两
23、个点不做任何变化！AA1A2A3A4A5A6A7A8A10A9A38最后搜索的方格不断重复这个过程，直到把终点也加入到了 open list 中。最终结束时如右图所示，这样我们就获得了绕过障碍物到达目的地的最短路。A39v这样我们的智能导航系统就设计完毕啦！这样我们的智能导航系统就设计完毕啦！A40v此时我们设计的导航系统已经可以投入生产使用啦！此时我们设计的导航系统已经可以投入生产使用啦！v跟进一步，假如我的障碍物也会移动怎么办？跟进一步，假如我的障碍物也会移动怎么办？A41v A*算法能够解决有固定障碍物的路径规划问题，并且能很快算法能够解决有固定障碍物的路径规划问题，并且能很快地给出解，
24、但是当障碍物是移动的时候，我们又应该如何对地给出解，但是当障碍物是移动的时候，我们又应该如何对算法进行改从而给出解呢？算法进行改从而给出解呢？v一个典型问题：一个典型问题：AGV小车线路规划！小车线路规划！A42智能码头：AGVAGV中文名：自动导引小车中文名：自动导引小车是自动化码头水平运输系统中用于搬运集装箱的搬运设备。是自动化码头水平运输系统中用于搬运集装箱的搬运设备。其主要职责：就是在规定的时间窗口范围内完成堆场和岸桥之其主要职责：就是在规定的时间窗口范围内完成堆场和岸桥之间实现集装箱的传送。间实现集装箱的传送。A43智能码头：AGVA44智能码头：AGV整个码头同一时刻运行的整个码头
25、同一时刻运行的AGV数量很多时候不只一辆，可能会数量很多时候不只一辆，可能会有很多辆。那我们如何能在满足每辆有很多辆。那我们如何能在满足每辆AGV时间窗口限制的前提时间窗口限制的前提完成作业呢？完成作业呢？A45智能码头：AGV在在A*算法中我们求解的约束是障碍物固定的情况，而在算法中我们求解的约束是障碍物固定的情况，而在AGV线线路规划中，我们求解的约束是障碍物不固定的情况，障碍物是路规划中，我们求解的约束是障碍物不固定的情况，障碍物是会移动，但在每个时刻处于哪个位子我们是可以确定的。会移动，但在每个时刻处于哪个位子我们是可以确定的。A46智能码头：AGV问题转化：假设我们现在只考虑设计一台
26、问题转化：假设我们现在只考虑设计一台AGV的运行轨迹，其的运行轨迹，其他他AGV的运行轨迹是已知的，已知运行轨迹的的运行轨迹是已知的，已知运行轨迹的AGV可以理解为可以理解为随时间变化移动的障碍物。随时间变化移动的障碍物。A47问题简化虽然在实际过程中，虽然在实际过程中，AGV小车在哪个位子转弯是任意的，但我们做出小车在哪个位子转弯是任意的，但我们做出如下几方面简化假设：如下几方面简化假设：1、AGV小车只能在一些固定点位子转弯；小车只能在一些固定点位子转弯；2、可行驶的道路数确定，即确定有、可行驶的道路数确定，即确定有6车道；车道；3、我们只考虑两辆、我们只考虑两辆AGV的情况，一辆运行轨道
27、已知，求另一辆最优的情况，一辆运行轨道已知，求另一辆最优轨迹。轨迹。这样我们就将问题抽象成如下网络结构问题：这样我们就将问题抽象成如下网络结构问题：A48问题简化：S1T1是我们已知的一条是我们已知的一条AGV1的运行线路的起点的运行线路的起点和终点，和终点，ST为我们需要为我们需要规划的规划的AVG2线路的起点线路的起点和终点。和终点。A491时刻2时刻3时刻4时刻5时刻红线为红线为AGV1的行驶线路，绿色为的行驶线路，绿色为在不同时刻在不同时刻AGV1所在线路，我们所在线路，我们在为在为AGV2规划线路时不需要与红规划线路时不需要与红色线完全不交叉，只需要在相应色线完全不交叉，只需要在相应的时刻不与绿色线交叉便可！的时刻不与绿色线交叉便可！A50课后问题：对于上述简化的障碍物移动问题，能否设计出一个最短线路算法？对于上述简化的障碍物移动问题，能否设计出一个最短线路算法？A51
