搜索
最短路问题及相关算法介绍吕长虹华东师范大学数学系Email:chlu@math.ecnu.edu.cnQuestionone：每天开车去上班，应该走那条使得达到公司的费用最低、时间最少呢，如何选择最优的路径呢？Questiontwo：在城市规划自己电网架设中，怎么设计才能使其耗费的资金最少？其实都涉及到一个相同的问题：最短路问题！最短路问路径不仅仅是一般地理意义上的距离最短，还可以延伸到其他度量，如时间、费用、线路容量等，相应的最短路问题就转化诶最快路径问题、最低费用问题。最短路径问题也是资源分配，线路设计及分析等优化问题的基础。图论中的最短路问题(shortestrouteproblem)是组合数学和图论中核心问题之一，是许多更深层次算法的基础。图的定义：图是一种由“顶点”组成的抽象网络，网络中的各顶点可以通过“边”实现彼此的连接，表示两顶点有关联。图一般用G来表示，其顶点集为V，边集为E，简述为G=(V,E)。右图就是图论中一个节点的图结构，一共有10个顶点，15条边。Petersen图最短路问题就是在指定的网络中两个节点间寻找一条距离最小的路。网络就是用节点和边联结构成的图，如铁路网、公路网等。下图就是我们将一个实际区域结构，图结构化的结果。两种常见最短路问题：1、单源最短路问题：：求某一个到其余个点的最短路问题？----dijkstra算法2、多源最短路问题：求任意两点之间最短路问题？----Floyd算法Dijkstra算法更是被称为统治世界的十大算法之一。最短路算法一个经典应用：导航我们在百度地图上寻找驾车路径时，显然就是要寻找一条物理距离最短或者行驶时间最短的路线。那我们能否通过算法设计一个属于我们的导航呢？Dijkstra算法就可以帮助我们做到这一点！问题简述现有在无向图G=(V,E)，V为各顶点的集合，E边集合，W为每条路径的权值，满足权值大于零。需要求得从某个起始点v,到其余各点的最短路径。Dijkstra算法算法描述Dijkstra算法描述把图中顶点集合V分成两组第一组为已求出最短路径的顶点集合（用S表示，初始时S中只有一个源点，以后每求得一条到其余顶点的最短路径,就将加入到集合S中，直到全部顶点都加入到S中，算法就结束了）第二组为其余未确定最短路径的顶点集合（用U表示），按最短路径长度的递增次序依次把第二组的顶点加入S中。在加入的过程中，总保持从源点v到S中各顶点的最短路径长度不大于从源点v到U中任何顶点的最短路径长度。此外，每个顶点对应一个距离，S中的顶点的距离就是从v到此顶点的最短路径长度，U中的顶点的距离，是从v到此顶点只包括S中的顶点为中间顶点的当前最短路径长度。Dijkstra算法步骤从U中选取一个距离v最小的顶点k，把k，加入S中（该选定的距离就是v到k的最短路径长度）。二重复步骤二和三直到所有顶点都包含在S中。四以k为新考虑的中间点，修改U中各顶点的距离；若从源点v到顶点u的距离（经过顶点k）比原来距离（不经过顶点k）短，则修改顶点u的距离值，修改后的距离值的顶点k的距离加上边上的权。三初始时，S只包含源点，即S＝{v}，v的距离为0。U包含除v外的其他顶点，即:U={其余顶点}，若v与U中顶点u有边，则u,v正常有权值，若u不是v的出边邻接点，则u,v权值为∞。一算法的描述上看去相当复杂，我们给出下面例子来具体说明整个算法的运行流程！首先我们要有如下概念：假设P：v→km是从顶点v到km的一条最短路径，那对这条路径上任意其他一点ki，都有P上关于v→ki的子路径为v到点ki的最短路径。即最短路径的子路径仍然是最短路径，最短路算法本质上上基于这种思想展开的。经典例子Example：右图G，顶点集合V={V1,V2,V3,V4,V5,V6}，6个顶点；边集E={V1V2,V1V3,V1V6,V2V3,V2V4,V3V4,V3V6,V4V5,V5V6}，9条边。W=0,7,9,∞,∞,147,0,10,15,∞,∞9,10,0,11,∞,2∞,15,11,0,6,∞∞,∞,∞,6,0,914,∞,2,∞,9,0,W=(wij)6×6为6阶方正，wij为ViVj边上权值，若无边相连，则为无穷我们取源点为V1，即求V1到其余个点的最短距离。STEP1：开始阶段S={V1}，U={V2,V3,V4,V5,V6}，W=(wij)6×6为权值矩阵。向量D来记录每一步之后V1与其余各点之间的最短距离。初始阶段D=(0,7,9,∞,∞,14)。STEP2：将与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=min{S13,D13}=min{17,9}=9,不变。D14=min{S14,D14}=min{22,∞}=22,变小。此时D=(0,7,9,22,∞,14)STEP3：将与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=min{S14,D14}=min{20,22}=20,变小。D16=min{S16,D16}=min{11,14}=11,变小。此时D=(0,7,9,20,∞,11)STEP4：将U中与V1距离最小的点V6放入S中，S={V1,V2,V3,V6}，U={V4,V5}，此时我们确定V1到V6之间的最短距离为11。计算V1与U中各点距离【必须最短路经过V6】，再与向量D中比较取较小值作为新的D中取值。S15=W65+D1=11+9=20D15=min{S15,D15}=min{20,∞}=20,变小。此时D=(0,7,9,20,20,11)STEP5：此时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到其余各个点的最短距离向量。优点缺点优点优点缺点缺点效率低，需要遍历所有点（特别是有时候不需要最优解）、运算中占用空间大缺点算法简明易懂、并且一定能得到最优解优点Dijkstra算法可能不是最优先使用的方法，因为算法的运算速度效率，往往要比精确度更加重要实际运用这样利用Dijkstra算法设计一个属于我们自己的导航系统啦。但似乎在实际运行时效果并不理想！虽然算法本身就是最短路径，但路面交通变化复杂，由于路面施工导致道路封锁，同时还存在路堵、车祸等现象，导致算法输出的最优路径，实际上并不是我们想要的最优路径。路面道路封锁、路堵、车祸等现象，本质上可以理解为这条道路被封堵住了，即有一个障碍物出现在此处，阻碍我们继续前进了！这时候我们Dijkstra算法就失效了！有同学会问：去掉这条堵住的线段不就可以了？这样仍然可以用Dijkstra算法求解。事实上这是一种可行的思路，但如果这样操作每天我的导航系统就要花大量时间去进行线段删减、增加工作。系统维护成本增加！A*算法就是解决这类问题的一个有效算法。A*算法可以理解成Dijkstra算法+最佳优先搜索！最佳优先搜索简介这个算法的运算流程跟Dijkstra的流程类似，只不过它考察的是选取点到终点的距离，并且这个距离的权值是评估出来的，这也就是启发式的思想。举例说明，如果说目标的终点在北面，那么越靠近北面的点权值就越小，那么算法在搜索过程中，所加入点集的点就会倾向于北面，因此不用搜索全图东南西北，更多的是搜索北面的点，速度来说会优于Dijkstra算法很多。A*算法描述A*算法将两种算法结合起来，最为关键的就是它判断权值大小的函数f(n)。它定义f（n）=g(n)+h(n)。其中，g(n)为起始点到任意节点n的权值，在路径搜索中，也就是说到n点需要付出的代价，换句话说，之前所叙述的Dijkstra算法。h(n)表达的是从节点n到终点的估计权值，也就是前面所陈述的最佳优先搜索。从中可以看到，当h(n)=0的时候，这个算法就是Dijkstra算法，而当个g（n）=0的时候，这个算法就是最佳优先算法。h(n)的值占比越大，这个A*算法的启发度越高，也就越不精确，但运算很快。相对的g(n)的占比高时，这个算法更趋向于将全局的节点都加进点集进行对比，从而可以给出较优的解，但算法速度会变慢。算法过程1.设定三个集合closelist,openlist,parentnode，其中，closelist中记录已经搜寻过的点，openlist中记录等待搜寻的点，parentnode则是用来记录搜寻的路径，最后回推找到结果路径；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中或者无法通过，那么就不处理它；10.如果openlist没有终点或所在水平线两侧的相邻点，那么跳转到3步骤；如果有终点或所在水平线两侧的相邻点中的任何一个，则将其设为终点并结束完成当前任务规划。经典例子•我们需要从绿色格子搜寻路径到红色格子，我们假定横向、纵向移动的权值为10，对角线移动权值为14。格子的左上角是f(n),左下角为g(n),右下角为h(n)的值此处使用Manhattan方法估计h取值，计算从当前方格横向或纵向移动到达目标所经过的方格数，忽略对角移动，然后把总数乘以10。说明：对于障碍物存在的地方，我们认为无法通过，即不能经过任何和障碍有关的地方，甚至是单个点。所以对角线也无法走！初始搜索过程：1、起点A开始，openlist={A}；2、查看与起点A相邻的方格(忽略其中墙壁所占领的方格)，把其中可走的方格也加入到openlist中，此时openlist={A、A1，A2，A3，A4，A5，A6，A7，A8};3、设置这些新加入点的父亲为A；4、更新openlist和closelist，openlist={A1，A2，A3，A4，A5，A6，A7，A8}，closelist={A}；5、计算每个新加入openlist点的F,G,H值，并标注在相应位置；AA1A2A3A4A5A6A7A8下一步搜索的方格1、从openlist中选择F值最小的(方格)节点A1；2、更新openlist和closelist，openlist={A2，A3，A4，A5，A6，A7，A8}，closelist={A，A1}；3、检查所有与它相邻的方格，忽略其中在closelist中或是不可走的方格，如果方格不在openlsit中，则把它们加入到openlist[对于A1点来说并没有新的点要加入到openlist]；4、检查原先openlist中点A2，A3，A7，A8在通过A1到达的G值是否更小？显然没有，所以不做任何变化！AA1A2A3A4A5A6A7A8下一步搜索的方格1、从openlist中选择F值最小的(方格)节点A2；[A2和A8取值一样，随机选择一个都可以。]2、更新openlist和closelist，openlist={A3，A4，A