ospf协议很多人都知道,很多人也会配置而且很熟练,但是很少有人懂得其背后的思想是什么,Dijkstra算法是求解单源最短路径的绝妙算法之一,我打心眼里头喜欢这个算法,真想把之一去掉。Dijkstra算法是一种贪心算法,贪心算法的本质就是最值的和还是最值,也就是说人们相信我只要在点滴当中尽自己最大的努力,那么最后的结果就是最好的,可能你会说不一定,但是你敢说如果有一个环节你没有尽最大的努力,最后的结果会更好吗?你不能,我也不能,因为现实总是很残酷,事后诸葛亮只能出现在理想状态,事情已经发生,那么你就不能说更好的结果需要什么条件,正所谓“证明一件事是错的很容易,但是证明一件事正确根本不可能!”,因此贪心算法的证明非常复杂,可是Dijkstra算法确实是正确的,为什么?不是因为它不是纯粹的贪心算法,正是因为它的条件里面存在的信息很少,我们可以利用另一把利器来证明之,这把利器就是“数学归纳法”。
数学归纳法是一种艺术,玩过多米诺骨牌的都知道,要使得任意数量的所有牌全部翻掉需要两个条件而且只需要两个条件,一个就是任意两张牌间隔足够近,另一个条件就是你必须推到第一张牌,就是这么简单。于是如果你往这个游戏靠拢你会发现,牌的倒掉和牌的数量以及牌上的内容没有任何关系,那么任何可以归结到这个游戏的数学模型都可以用这个原理进行求解,多米诺骨牌游戏的数学模型就是数学归纳法,数学归纳法进行的证明需要两点,第一就是初始条件(推到第一张牌),第二就是假设n成立证明n+1成立(两张牌间隔足够近),贪心算法是一个步骤问题,如果我们可以证明贪心算法的第一部很显然正确并且在归纳假设的情况下证明归纳假设的系一个步骤也正确的话,那么贪心算法的局部最优解结合成的全局解一定是全局最优解,这是一定的。
Dijkstra算法是一个贪心算法,那么我们可以通过数学归纳法证明其正确性,关键就是如何建立数学模型。Dijkstra算法的步骤是显然的,是简单的,我们只需要证明这个算法产生的路径就是最短的就可以了,于是模型就有了,很多书上都用open-set作为“外面”的点,将close-set作为加入到“里面”的点,那么我们就证明每通过Dijkstra算法加入到close-set的点到原点的距离就是到原点距离的最短距离,这样我们就证明了算法本身的正确性,因此开始用数学归纳法证明吧,当close-set中除了原点只有一个点的时候,这个点p离原点s的距离一定是最短的,因为如果s先到x再到p的距离比s直接到p还短,那么s到x会更短,算法就不会选中p而会选中x,与假设矛盾,这里已经证明了初始条件,下面开始归纳假设,设close-set中有k个点时,所有close-set中的k个点根据算法算出的距离都是最短的距离,那么我们考虑加入第k+1个点加入时的情形,只要能证明k+1个点按照算法加入进close-set从而算出的距离也是最短距离的话,那么问题得证,这个问题也是很好证明的,同样用反证法,假设不是靠算法加入的,那么路径中一定除了终点p之外还有一个点在open-set中,如果这样的话,根本就不可选中终点p而会选中那个经过的点,也是矛盾的,由此问题得证。在上面额证明中,所有在close-set中和p相连的点都会参与最后的最短距离竞争,因此就在它们当中选一条路径最为结果就是问题的答案,而这正是算法的行为。
这里可以看到有时候贪心算法可以用数学归纳法来证明,但是有的时候不能,不能的原因就在于约束条件太多,要么就是因为初始条件无法被证明但是归纳假设却正确,其实千万不要过度怀疑贪心算法,我们人做事的时候不是也都是在用贪心算法吗?如果有谁在做事之前来个全局证明或者必须证明其严密性的话,那么这个人最终会因为理智过度要么被社会淘汰,要么成为划时代的思想家。贪心算法来自于一个事实,那就是爆炸,爆炸波的包络面总是呈球面向外扩撒,球面刚接触到一个点的时候,这个点到爆炸源的距离肯定最短,这不是废话吗?这个点到爆炸源的连线不是一条线段吗?很多的时候是一条线段,但是考虑到爆炸不是在一个密度相同的没有障碍物的地方,而是在一个建筑物里面,该建筑物内部有复杂的小隔间,而且各个隔间相通,隔间之间是坚固的钢板隔开,爆炸无法摧毁这些隔板,那么爆炸波的包络面虽然是球面,但是实际路线却不是线段,而是沿着各个隔间之间的通道走的,这个时候首先被波及的点沿着爆炸波的路线回到爆炸点,路线肯定是最短的,这是事实啊,好事怎么也波及不到我们,坏事总是用最快的是速度到来。
有时候觉得人做事很多时候挺像计算机的,用了很多的算法,按经验步骤进行,不求甚解,而我们从小学开始学的那些数学,比如解方程,函数求导之类的却是纯思维的东西,这些一般来用发掘新的算法,人的算法还来自于经验,但是到底哪个更重要呢?
分享到:
相关推荐
毕业设计:最短路径算法实现,Dijkstra算法,双向Dijkstra算法,CH算法,SILC算法 毕业设计:最短路径算法实现,Dijkstra算法,双向Dijkstra算法,CH算法,SILC算法 毕业设计:最短路径算法实现,Dijkstra算法,双向...
代码 基于最短路dijkstra算法离散优化问题代码代码 基于最短路dijkstra算法离散优化问题代码代码 基于最短路dijkstra算法离散优化问题代码代码 基于最短路dijkstra算法离散优化问题代码代码 基于最短路dijkstra算法...
Dijkstra算法算是贪⼼思想实现的,⾸先把起点到所有点的距离存下来找个最短的,然后松弛⼀次再找出最短的,所谓的松弛操作就是,遍历⼀遍看通过刚刚找到的距离最短的点作为中转站会不会更近,如果更近了就更新距离,...
dijkstra算法C++实现的程序代码
Dijkstra算法应用举例 Dijkstra算法应用举例Dijkstra算法应用举例 Dijkstra算法应用举例
求解单源最短路径的Dijkstra算法模板,数学建模竞赛必备。
本程序使用C语言实现了Dijkstra算法。程序中,定义好邻接矩阵,可以计算出任一节点到其他所有节点的最短路径,并打印路径与长度。其中对最短路径的存储是依据所得到的生成树,可以减少内存空间占用。
Dijkstra算法的应用, Dijkstra算法的应用 Dijkstra算法的应用 Dijkstra算法的应用 Dijkstra算法的应用 Dijkstra算法的应用 Dijkstra算法的应用
Dijkstra算法,Dijkstra算法详细讲解,Dijkstra算法详细讲解
最短路径Dijkstra算法-最短路Dijkstra算法.rar 最短路径Dijkstra算法
【蚁群算法】 改进蚁群算法 Dijkstra算法 遗传算法 人工势场法实现二维 三维空间路径规划 本程序为蚁群算法+Dijkstra算法+MAKLINK图理论实现的二维空间路径规划 算法实现: 1)基于MAKLINK图理论生成地图,并对可行...
能够实现 Dijkstra算法,内涵代码,运行即可实现
Dijkstra算法求解格栅地图路径matlab代码
文章研究了一种多核架构下基于OpenMP的Dijkstra并行算法,以Dijkstra算法为基础设计并行程序。对传统Dijkstra算法进行分析,明确优化方向,再利用OpenMP开发工具对并行程序进行优化调试。结果表明,文中算法易于操作...
Dijkstra算法的Matlab程序,用于求各点之间的最短路距离。该程序解决了一个有九个点的无向图中求任意两点之间最短路距离的例子。程序中的每一步都有详细说明。
Dijkstra算法演示flash 一看就会Dijkstra算法~~
基于Dijkstra算法的路径规划算法,matlab代码
C语言版Dijkstra算法,有注释。 只是简单的Dijkstra算法的实现。
Dijkstra算法最简单的实现方法是用一个链表或者数组来存储所有顶点的集合Q,所以搜索Q中最小元素的运算(Extract-Min(Q))只需要线性搜索Q中的所有元素。这样的话算法的运行时间是O(n2)。