精华内容
下载资源
问答
  • 常用的算法基本思想

    千次阅读 2018-12-19 15:34:02
    算法基本思想 (一)穷举算法思想 从所有可能情况中搜索正确答案 对于一种可能情况,计算其结果。 判断结果是否满足,如不能满足者执行第一步来搜索下一个可能的情况;如满足则表示选找到一个正确答案。 ​ 实例...

    算法的基本思想

    (一)穷举算法思想

    从所有可能情况中搜索正确答案

    1. 对于一种可能情况,计算其结果。
    2. 判断结果是否满足,如不能满足者执行第一步来搜索下一个可能的情况;如满足则表示选找到一个正确答案。

    ​ 实例:鸡兔同笼问题

    (二)递推算法思想

    递推算法是一种理性思维模式的代表,其根据已有的数据和关系,逐步推到而得到结果。对推算法的执行过程:

    1. 根据已知结果和关系,求解中间结果。

    2. 判定是否但到要求,若没有继续执行第一步,若有则表示找到一个正确结果
      递推算法往往需要知道答案和问题之间的实际逻辑关系。再许多数学问题中往往都有着明确的计算公式可以遵循,因此可以采用递推算法来实现。

      实例:斐波那契数列:兔子产仔问题

    (三)递归算法思想

    递归算法即在程序中不反复调用自身达到解决问题的方法,是一个方法在其方法体内调用自身方法调用方式。在递归中主方法又是被调方法。执行递归将反复调用其自身。每调用一层就进入新的一层。
    递归调用分为两种情况:

    • 直接递归,即在方法中调用方法本身
    • 间接递归,即间接地调用一个方法
      编写递归方法时,必须使用if语句强制在未执行递归前返回。

    ​ 实例:阶乘问题

    (四)分治算法思想

    分治算法就是把一个复杂问题分为规模较小的,计算简单的小问题,然后综合小问题得到最后答案的思想。分治算法执行过程如下:

    1. 对于一个规模为N的问题,若给问题比较容易解决,则直接解决;否则执行下面的步骤。

    2. 将该问题分解为M个规模较小的问题,这些问题相互独立,并且与原问题相互独立。

    3. 递归这些小问题

    4. 然后,将各个小问题合并得到完问题的解

      实例:一个袋子里有三十个硬币,其中有一枚假币,并且假币和真币一某一样,肉眼很难分辨,目前只知道假币比真币轻一点,请问如何区分假币?

      算法分析

    5. 首先为每个硬币编号,然后然后将所有硬币等分为两份,放在天平两边。

    6. 再将较轻的那一份等分为两份重复上述方法

    7. 直到剩下两个硬币,较轻的一个就是假币

      算法实现

       public int FalseCoin(int coin[],int low,int high)
       {
           int i,sum1,sum2,sum3;
           int re = 0;
           sum1 = sum2 = sum3 = 0;
           if(low+1==high)
           {
               if(coin[low]<coin[high])
               {
                   re = low + 1;
                   return re;
               }
               else 
               {
                   re = high +1;
                   return re;
               }
           }
           if((high-low+1)%2==0)   //n是偶数
           {
               for(i=low;i<=low+(high-low)/2;i++)
               {
                   sum1= sum1+coin[i];
               }
               for(i=low+low+(high-low)/2;i<=high;i++)
               {
                   sum2= sum2+coin[i];
               }
               if(sum1>sum2)
               {
                   re=FalseCoin(coin,low+(high-low)/2,high);
                   return re;
               }
               else if(sum1<sum2)
               {
                   re=FalseCoin(coin,low,low+(high-low)/2);
                   return re;
               }
           }
           else
           {
               for(i=low;i<=low+(high-low)/2-1;i++)
               {
                   sum1= sum1+coin[i];
               }
               for(i=low+low+(high-low)/2+1;i<=high;i++)
               {
                   sum2= sum2+coin[i];
               }
               sum3=coin[low+(high-low)/2];
               if(sum1>sum2)
               {
                   re=FalseCoin(coin,low+(high-low)/2+1,high);
                   return re;
               }
               else if(sum1<sum2)
               {       
                   re=FalseCoin(coin,low,low+(high-low)/2-1);
                   return re;
               }
               else
               {
                   re=low+(high-low)/2+1;
                   return re;
               }
           }
           return re;
       }
    

    (五)概率算法思想

    ​ 概率算法依照概率统计的思路来求解问题,往往不能得到问题的精确解,但却在数值计算领域得到了广泛的应用。因为很多数学问题,往往没有或者很难计算解析解,这时便需要通过数值计算来求解近似值。

    概率算法执行的基本过程如下:
    (1)将问题转化为相应的几何图形S, S 的面积是容易计算的,问题的结果往往对应几何图形中某一部分S1 的面积。
    (2)然后,向几何图形中随机撒点。
    (3)统计几何图形S 和 S1 中的点数。根 据 S 的面积和S1 面积的关系以及各图形中的点数来计算得到结果。
    (4) 判断上述结果是否在需要的精度之内,如果未达到精度则执行步骤(2)。如果达到精度,则输出近似结果。
    概率算法大致分为如下4 种形式。

    • 数值概率算法。
    • 蒙 特 卡 罗 (MonteCarlo)算法。
    • 拉 斯 维 加 斯 (Las Vegas)算法。
    • 舍 伍 德 (Sherwood)算法

    ​ 实例【蒙特卡罗PI概率算法问题】
    在边长为1的正方形内,以1为半径画一个1/4圆。落入院内的概率为PI/4?
    算法思想:在某面积范围内撒点足够多,落在固定区域的点的概率就会将近结果。
    关键:均匀撒点、区域判断

    double MontePI(int n){
    double PI;
    double x,y;
    int i,sum;
    sum=0;
    srand(time(NULL));
    for(i=1;i<n;i++){
        x=(double)rand()/RAND_MAX;//在0-1之间产生一个随机数x
         y=(double)rand()/RAND_MAX;//在0-1之间产生一个随机数y
        if((x*x+y*y)<=1){//判断点是否在圆内
            sum++;//计数
        }
    }
        PI=4.0*sum/n;//计算PI
        return PI;
    }
    
    int main()
    {
       int n=500000;
       double PI;
    
      printf("蒙特卡罗概率PI=%f\n", MontePI(n));
        return 0;
    }
    

    (六)回溯算法思想

    概念

    ​ 回溯算法实际上一个类似枚举的搜索尝试过程,主要是在搜索尝试过程中寻找问题的解,当发现已不满足求解条件时,就“回溯”返回,尝试别的路径。

    回溯法是一种选优搜索法,按选优条件向前搜索,以达到目标。但当探索到某一步时,发现原先选择并不优或达不到目标,就退回一步重新选择,这种走不通就退回再走的技术为回溯法,而满足回溯条件的某个状态的点称为“回溯点”。
    

    ​ 许多复杂的,规模较大的问题都可以使用回溯法,有“通用解题方法”的美称。

    基本思想

    在包含问题的所有解的解空间树中,按照深度优先搜索的策略,从根结点出发深度探索解空间树。当探索到某一结点时,要先判断该结点是否包含问题的解,如果包含,就从该结点出发继续探索下去,如果该结点不包含问题的解,则逐层向其祖先结点回溯。(其实回溯法就是对隐式图的深度优先搜索算法)。
    

    ​ 若用回溯法求问题的所有解时,要回溯到根,且根结点的所有可行的子树都要已被搜索遍才结束。

    ​ 而若使用回溯法求任一个解时,只要搜索到问题的一个解就可以结束。

    用回溯法解题的一般步骤

    ​ (1)针对所给问题,确定问题的解空间:

    ​ 首先应明确定义问题的解空间,问题的解空间应至少包含问题的一个(最优)解。

    ​ (2)确定结点的扩展搜索规则

    ​ (3)以深度优先方式搜索解空间,并在搜索过程中用剪枝函数避免无效搜索。

    (七)动态规划算法思想

    ​ 动态规划过程是:每次决策依赖于当前状态,又随即引起状态的转移。一个决策序列就是在变化的状态中产生出来的,所以,这种多阶段最优化决策解决问题的过程就称为动态规划。

    ​ 基本思想与分治法类似,也是将待求解的问题分解为若干个子问题(阶段),按顺序求解子阶段,前一子问题的解,为后一子问题的求解提供了有用的信息。在求解任一子问题时,列出各种可能的局部解,通过决策保留那些有可能达到最优的局部解,丢弃其他局部解。依次解决各子问题,最后一个子问题就是初始问题的解。

     由于动态规划解决的问题多数有重叠子问题这个特点,为减少重复计算,对每一个子问题只解一次,将其不同阶段的不同状态保存在一个二维数组中。
    

    ​ 与分治法最大的差别是:适合于用动态规划法求解的问题,经分解后得到的子问题往往不是互相独立的(即下一个子阶段的求解是建立在上一个子阶段的解的基础上,进行进一步的求解)。

    实现步骤

    ​ (1)划分阶段:按照问题的时间或空间特征,把问题分为若干个阶段。在划分阶段时,注意划分后的阶段一定要是有序的或者是可排序的,否则问题就无法求解。

    ​ (2)确定状态和状态变量:将问题发展到各个阶段时所处于的各种客观情况用不同的状态表示出来。当然,状态的选择要满足无后效性。

    ​ (3)确定决策并写出状态转移方程:因为决策和状态转移有着天然的联系,状态转移就是根据上一阶段的状态和决策来导出本阶段的状态。所以如果确定了决策,状态转移方程也就可写出。但事实上常常是反过来做,根据相邻两个阶段的状态之间的关系来确定决策方法和状态转移方程。

    ​ (4)寻找边界条件:给出的状态转移方程是一个递推式,需要一个递推的终止条件或边界条件。

    ​ 一般,只要解决问题的阶段、状态和状态转移决策确定了,就可以写出状态转移方程(包括边界条件)。

    (八)分支限界算法思想

    基本描述

    ​ 类似于回溯法,也是一种在问题的解空间树T上搜索问题解的算法。但在一般情况下,分支限界法与回溯法的求解目标不同。回溯法的求解目标是找出T中满足约束条件的所有解,而分支限界法的求解目标则是找出满足约束条件的一个解,或是在满足约束条件的解中找出使某一目标函数值达到极大或极小的解,即在某种意义下的最优解。

    1. 分支搜索算法

    ​ 所谓“分支”就是采用广度优先的策略,依次搜索E-结点的所有分支,也就是所有相邻结点,抛弃不满足约束条件的结点,其余结点加入活结点表。然后从表中选择一个结点作为下一个E-结点,继续搜索。

    ​ 选择下一个E-结点的方式不同,则会有几种不同的分支搜索方式。

    1)FIFO搜索

    2)LIFO搜索

    3)优先队列式搜索

    1. 分支限界搜索算法

    分支限界法的一般过程

    ​ 由于求解目标不同,导致分支限界法与回溯法在解空间树T上的搜索方式也不相同。回溯法以深度优先的方式搜索解空间树T,而分支限界法则以广度优先或以最小耗费优先的方式搜索解空间树T。

    ​ 分支限界法的搜索策略是:在扩展结点处,先生成其所有的儿子结点(分支),然后再从当前的活结点表中选择下一个扩展对点。为了有效地选择下一扩展结点,以加速搜索的进程,在每一活结点处,计算一个函数值(限界),并根据这些已计算出的函数值,从当前活结点表中选择一个最有利的结点作为扩展结点,使搜索朝着解空间树上有最优解的分支推进,以便尽快地找出一个最优解。

    ​ 分支限界法常以广度优先或以最小耗费(最大效益)优先的方式搜索问题的解空间树。问题的解空间树是表示问题解空间的一棵有序树,常见的有子集树和排列树。在搜索问题的解空间树时,分支限界法与回溯法对当前扩展结点所使用的扩展方式不同。在分支限界法中,每一个活结点只有一次机会成为扩展结点。活结点一旦成为扩展结点,就一次性产生其所有儿子结点。在这些儿子结点中,那些导致不可行解或导致非最优解的儿子结点被舍弃,其余儿子结点被子加入活结点表中。此后,从活结点表中取下一结点成为当前扩展结点,并重复上述结点扩展过程。这个过程一直持续到找到所求的解或活结点表为空时为止。

    1. 回溯法和分支限界法的一些区别

    回溯法和分支限界法的一些区别:

    方法对解空间树的搜索方式 存储结点的常用数据结构 结点存储特性常用应用

    回溯法深度优先搜索堆栈活结点的所有可行子结点被遍历后才被从栈中弹出找出满足约束条件的所有解
    
    分支限界法广度优先或最小消耗优先搜索队列、优先队列每个结点只有一次成为活结点的机会找出满足约束条件的一个解或特定意义下的最优解
    

    (九)贪心算法

    基本概念

    ​ 所谓贪心算法是指,在对问题求解时,总是做出在当前看来是最好的选择。也就是说,不从整体最优上加以考虑,他所做出的仅是在某种意义上的局部最优解。

    ​ 贪心算法没有固定的算法框架,算法设计的关键是贪心策略的选择。必须注意的是,贪心算法不是对所有问题都能得到整体最优解,选择的贪心策略必须具备无后效性,即某个状态以后的过程不会影响以前的状态,只与当前状态有关。

    ​ 所以对所采用的贪心策略一定要仔细分析其是否满足无后效性。

    贪心算法的基本思路

    ​ 1.建立数学模型来描述问题。

    ​ 2.把求解的问题分成若干个子问题。

    ​ 3.对每一子问题求解,得到子问题的局部最优解。

    ​ 4.把子问题的解局部最优解合成原来解问题的一个解。

    贪心算法适用的问题

    ​ 贪心策略适用的前提是:局部最优策略能导致产生全局最优解。

    ​ 实际上,贪心算法适用的情况很少。一般,对一个问题分析是否适用于贪心算法,可以先选择该问题下的几个实际数据进行分析,就可做出判断。

    贪心算法的实现框架

    ​ 从问题的某一初始解出发;

    ​ while (能朝给定总目标前进一步)

    ​ {

    ​ 利用可行的决策,求出可行解的一个解元素;

    ​ }

    ​ 由所有解元素组合成问题的一个可行解;

    贪心策略的选择

    ​ 因为用贪心算法只能通过解局部最优解的策略来达到全局最优解,因此,一定要注意判断问题是否适合采用贪心算法策略,找到的解是否一定是问题的最优解。

    例题分析

    ​ 下面是一个可以试用贪心算法解的题目,贪心解的确不错,可惜不是最优解。

    ​ [背包问题]有一个背包,背包容量是M=150。有7个物品,物品可以分割成任意大小。

    ​ 要求尽可能让装入背包中的物品总价值最大,但不能超过总容量。

    ​ 物品 A B C D E F G

    ​ 重量 35 30 60 50 40 10 25

    ​ 价值 10 40 30 50 35 40 30

    ​ 分析:

    ​ 目标函数: ∑pi最大

    ​ 约束条件是装入的物品总重量不超过背包容量:∑wi<=M( M=150)

    ​ (1)根据贪心的策略,每次挑选价值最大的物品装入背包,得到的结果是否最优?

    ​ (2)每次挑选所占重量最小的物品装入是否能得到最优解?

    ​ (3)每次选取单位重量价值最大的物品,成为解本题的策略。

    ​ 值得注意的是,贪心算法并不是完全不可以使用,贪心策略一旦经过证明成立后,它就是一种高效的算法。

    ​ 贪心算法还是很常见的算法之一,这是由于它简单易行,构造贪心策略不是很困难。

    ​ 可惜的是,它需要证明后才能真正运用到题目的算法中。

    ​ 一般来说,贪心算法的证明围绕着:整个问题的最优解一定由在贪心策略中存在的子问题的最优解得来的。

    ​ 对于例题中的3种贪心策略,都是无法成立(无法被证明)的,解释如下:

    ​ (1)贪心策略:选取价值最大者。反例:

    ​ W=30

    ​ 物品:A B C

    ​ 重量:28 12 12

    ​ 价值:30 20 20

    ​ 根据策略,首先选取物品A,接下来就无法再选取了,可是,选取B、C则更好。

    ​ (2)贪心策略:选取重量最小。它的反例与第一种策略的反例差不多。

    ​ (3)贪心策略:选取单位重量价值最大的物品。反例:

    ​ W=30

    ​ 物品:A B C

    ​ 重量:28 20 10

    ​ 价值:28 20 10

    ​ 根据策略,三种物品单位重量价值一样,程序无法依据现有策略作出判断,如果选择A,则答案错误。

    展开全文
  • 大话数据结构 第七章 图(二) 最小生成树、最短路径、拓扑排序、关键路径算法最小生成树定义Prim算法Kruskal算法最短路径Dijkstra算法Floyd算法拓扑排序AOV网拓扑序列拓扑排序算法关键路径AOE网关键路径算法 ...

    最小生成树

    定义

    • 所谓的最小成本,就是n个顶点,用n-1条边把一个连通图连接起来,并且使得权值的和最小
    • 最小生成树:构造连通网的最小代价生成树

    Prim算法

    • 中心思想是以某顶点为起点,逐步找各顶点上最小权值的边来构建最小生成树
    • 假设N=(V,{E})是连通网,TE是N上最小生成树中边的集合。算法从U={u0},TE={}开始。重复执行下述操作:
    • 在所有u∈U,v∈V-U的边(u,v)∈E中找一条代价最小的边(u0,v0)并入集合TE,同时v0并入U,直至U=V为止。此时TE中必有n-1条边,则T=(V,{TE})为N的最小生成树
    • 主要针对稠密图(边数较多时)
    • 算法的时间复杂度为O(n^2)

    Kruskal算法

    • 中心思想是以边为目标去构建,因为权值是在边上,直接去找最小权值得边来构建最小生成树,构建时要考虑是否形成了环路
    • 假设N=(V,{E})是连通网,则令最小生成树的初始状态为只有n个顶点而无边的非连通图T={V, {} },图中每个顶点自成一个连通分量。在E中选择代价最小的边,若该边依附的顶点落在T中不同的连通分量上,则将此边加入到T中,否则舍去此边而选择下一条代价最小的边。以此类推,直至T中所有顶点都在同一连通分量上为止。
    • 主要针对稀疏图
    • 算法的时间复杂度为O(e log e)

    最短路径

    • 对于网图来说,最短路径,是指两顶点之间经过的边上权值之和最小的路径

    Dijkstra算法

    • 是一个按路径长度递增的次序产生最短路径的算法
    • 不是一下子求出了源点到终点的最短路径,而是一步步求出它们之间顶点的最短路径,过程中都是基于已经求出的最短路径的基础上, 求得更远顶点的最短路径
    • 用于解决从某个源点到其余各顶点的最短路径问题,算法复杂度为O(n^2)
    • 若要用于任一顶点到其余所有顶点的最短路径,复杂度为O(n^3)

    Floyd算法

    • 定义两个数组D和P,其中D代表顶点到顶点的最短路径权值和的矩阵,P代表对应顶点的最小路径的前驱矩阵
    • D^0[v][w] = min{D^(-1)[v][w], D^(-1)[v][0] + D^(-1)[0][w]}
    • D0以D^(-1)为基础,D1以D0为基础……直至最后一个顶点Dn
    • 代码间接,时间复杂度为O(n^3)

    拓扑排序

    • 主要是为了解决一个工程能否顺序进行的问题

    AOV网

    • 在一个表示工程的有向图中,用顶点表示活动,用弧表示活动之间的有限关系,这样的有向图为顶点表示活动的网,我们称为AOV网

    拓扑序列

    • 设G=(V, E)是一个具有n个顶点的有向图,V中的序列v1,v2,…vn,满足若从顶点vi到vj有一条路径,则在顶点序列中顶点vi必在vj之前。则我们称这样的顶点序列为一个拓扑序列

    拓扑排序算法

    • 基本思路是:从AOV网中选择一个入度为0的顶点输出,然后删去此顶点,并删除以此顶点为尾的弧,继续重复此步骤,直到输出全部顶点或者AOV网中不存在入度为0的顶点为止
    • 顶点表结点结构:in(入度的数字),data,firstedge
    • 使用了栈结构(LIFO)
    • 将入度为0的顶点入栈的时间复杂为O(n),入度减1的操作共执行了e次,整个算法的复杂度为O(n+e)

    关键路径

    • 主要为了解决工程完成需要的最短时间问题

    AOE网

    • 在一个表示工程的带权有向图中,用顶点表示事件,用有向边表示活动,用边上的权值表示活动的持续时间,这种有向图的边表示活动的网,称之为AOE网
    • 把路径上各个活动所持续的时间之和称为路径长度,从源点到汇点具有最大长度的路径称为关键路径,在关键路径上的活动称为关键活动

    关键路径算法

    • 只需要找到所有活动的最早开始时间和最晚开始时间,并且比较它们,如果相等就意味着此活动是关键活动,活动间的路径为关键路径
    • 时间复杂度为O(n+e)
    展开全文
  • 图——基本的图算法(四)关键路径

    万次阅读 多人点赞 2018-10-26 17:34:07
    图——基本的图算法(四)关键路径 1. 基本概念 (1)AOV网(Activity On Vertex Network) AOV网是一个表示工程的有向图中,其中的顶点用来表示活动,弧则用来表示活动之间的优先关系。举个简单的例子,假定起床后...

    图——基本的图算法(四)关键路径

    1. 基本概念

    (1)AOV网(Activity On Vertex Network)
    AOV网是一个表示工程的有向图中,其中的顶点用来表示活动,弧则用来表示活动之间的优先关系。举个简单的例子,假定起床后可以边煮水,边刷牙洗脸,但洗脸要在刷牙后,煮好水,刷好牙洗好脸以后,就可以喝水了,这个活动的AOV图如下(其中的每个顶点都表示一个活动,而顶点之间的弧表示了活动之间的执行先后顺序):
    在这里插入图片描述

    (2)AOE网( Activity On Edge Network)
    AOE网是一个表示工程的带权有向图,其中的顶点用来表示某个事件,弧用来表示活动,弧上的权值用来表示活动持续的时间。例如上述例子的AOE网如下:
    在这里插入图片描述

    (3)AOE网和AOV网的区别
    AOV网:其顶点用来表示活动。AOE网是用来表示活动之间的制约关系。
    AOE网:顶点表示事件,边表示活动,边上的权值用来表示活动持续的时间。AOV网是用来分析工程至少需要花多少时间完成,或是为了缩短时间需要加快哪些活动等问题。

    (4)源点、汇点、路径长度
    在AOE网中,
    始点源点:入度为0的顶点,它表示一个工程的开始;
    终点汇点:出度为0的顶点,它表示一个工程的结束;
    路径长度:路径上各个活动所持续的时间之和。

    (5)关键路径、关键活动
    在AOE网中,从源点到汇点具有最大长度的路径称为关键路径,在关键路径上的活动称为关键活动

    2. 关键路径算法

    2.1 基本思想

    (1)要找出一个AOE网中的关键路径,就要先找出网里的关键活动,这些关键活动间的路径就是关键路径。

    (2)判断一个活动是不是关键活动,方法是要先找到所有活动的最早开始时间和最晚开始时间,并且对它们进行比较,如果二者相等(意味着这个活动在该工程中没有时间松动),说明这个活动是关键活动。

    (3)对于活动<Vi, Vj>,它最早的开始时间等于事件Vi最早的发生时间earlist[Vi](事件v的最早发生时间用earlist[v])。假设E[Vi]表示所有到达顶点Vi的弧的集合,len<Vi, Vj>表示活动<Vi, Vj>的持续时间,那么:
    在这里插入图片描述
    注意,这里假设顶点下标从0开始,所以Vi==0,则表示它是源点,因此最早的开始时间为0;当某个顶点不是源点,那么只有在它前面的事件都发生完后,才能轮到这个事件,所以用了max。

    (4)对于活动<Vi, Vj>,它最晚的开始时间等于事件Vj最晚的发生时间减去这个活动的持续事件,即latest[Vj]-len<Vi, Vj>(事件v的最晚的发生时间用latest[v])。假设S[Vj]表示所有从顶点Vj出发的弧的集合,len<Vj, Vk>表示活动<Vj, Vk>的持续时间,那么:
    在这里插入图片描述

    2.2 算法实现

    (1)数据结构

    typedef struct EdgeListNode{ //边表结点
        int adjId;
        int weight;
        EdgeListNode* next;
    };
    
    typedef struct VertexListNode{ //顶点表结点
        int in; //入度
        int data;
        EdgeListNode* firstadj; //指向其边表
    };
    
    typedef struct GraphAdjList{ //图结构
        int vertexnumber; //顶点个数
        int edgenumber;
        VertexListNode vertextlist[Maximum];
    };
    
    

    (2)具体实现
    1)由基本思路可以知道,要求一个AOE网的关键路径,步骤如下:
    A. 首先初始化每个顶点的最早开始为0,然后对AOE网进行拓扑排序,在排序的过程中获取每个顶点的最早开始时间;
    B. 获取拓扑排序后,初始化每个顶点的最晚开始时间为汇点的最早开始时间,并从AOE网的汇点开始,从后往前,对每个顶点找到求其最晚开始时间;
    C. 遍历图中的每条边(方法是遍历图中每个顶点的边表),求其最早开始时间和最晚开始时间,如果二者相等,则这是个关键活动,将其加入关键路径中。

    2)代码

    #include<iostream>
    #include<stdio.h>
    #include<string.h>
    #include<map>
    #include<vector>
    #include<sstream>
    #include<list>
    #include<stdlib.h>
    #include<queue>
    using namespace std;
    
    #define Maximum 1000
    
    typedef struct EdgeListNode{
        int adjId;
        int weight;
        EdgeListNode* next;
    };
    
    typedef struct VertexListNode{
        int in;
        int data;
        EdgeListNode* firstadj;
    };
    
    typedef struct GraphAdjList{
        int vertexnumber;
        int edgenumber;
        VertexListNode vertextlist[Maximum];
    };
    
    //拓扑排序,返回拓扑排序结果,earlist存储每个顶点的最早开始时间
    vector<int> ToplogicalSort(GraphAdjList g, int *earlist) {
        vector<int>v; //存储拓扑排序结果
        queue<int>q; //存储入度为0的顶点
        EdgeListNode *temp;
        int i, j, k, ans;
    
        ans = 0;
        v.clear();
        while(!q.empty()) {
            q.pop();
        }
    
    	//找出所有入度为0的顶点
        for(i=1; i<=g.vertexnumber; i++) {
            if(g.vertextlist[i].in == 0) {
                q.push(i);
            }
        }
    
        while(!q.empty()) {
            i = q.front();
            v.push_back(i);
            q.pop();
            ans++;
            temp = g.vertextlist[i].firstadj;
            while(temp != NULL) {
                k = earlist[i] + temp->weight;
                if(k > earlist[temp->adjId]) {
                    earlist[temp->adjId] = k;
                }
                j = --g.vertextlist[temp->adjId].in;
                if(j == 0) {
                    q.push(temp->adjId);
                }
                temp = temp->next;
            }
        }
    
        if(ans < g.vertexnumber) {
            v.clear();
        }
        return v;
    }
    
    //求关键路径,返回存储关键路径顶点的vector
    vector<int> CriticalPath(GraphAdjList g) {
        vector<int>ans;
        vector<int>path;
        int i, j, k, *earlist, *latest;
        EdgeListNode *temp;
    
    	//earlist存储每个顶点的最早开始时间
    	//latest存储每个顶点的最晚开始时间
        earlist = (int*)malloc(sizeof(int) * (g.vertexnumber+1));
        latest = (int*)malloc(sizeof(int) * (g.vertexnumber+1));
        path.clear();
        for(i=1; i<=g.vertexnumber; i++) {
            earlist[i] = 0;
        }
    
        ans = ToplogicalSort(g, earlist);
        for(i=1; i<=g.vertexnumber; i++) {
            latest[i] = earlist[ans[g.vertexnumber-1]];
        }
        for(i=g.vertexnumber; i>0; i--) {
            temp = g.vertextlist[i].firstadj;
            while(temp!=NULL) {
                if(latest[temp->adjId] - temp->weight < latest[i]) {
                    latest[i] = latest[temp->adjId] - temp->weight;
                }
                temp = temp->next;
            }
        }
    
    	//遍历每条边
        for(i=1; i<=g.vertexnumber; i++) {
            temp = g.vertextlist[i].firstadj;
            while(temp != NULL) {
                j = earlist[i];
                k = latest[temp->adjId] - temp->weight;
                if(j == k) { //是关键活动
           			//把该活动的两个顶点加入path
                    path.push_back(i);
                    path.push_back(temp->adjId);
                }
                temp = temp->next;
            }
        }
        return path;
    }
    

    (3)测试
    在这里插入图片描述

    int main() {
        GraphAdjList g;
        EdgeListNode *e;
        int i, j, k;
    
        g.vertexnumber = 5;
        g.edgenumber = 7;
    
    
        for(i=1; i<=g.vertexnumber; i++) {
            g.vertextlist[i].data = i;
            g.vertextlist[i].firstadj = NULL;
        }
    
        g.vertextlist[1].in = 0;
        g.vertextlist[2].in = 1;
        g.vertextlist[3].in = 2;
        g.vertextlist[4].in = 2;
        g.vertextlist[5].in = 1;
    
        e = (EdgeListNode*)malloc(sizeof(EdgeListNode));
        e->adjId = 2; e->weight = 2; e->next = g.vertextlist[1].firstadj; g.vertextlist[1].firstadj = e;
    
        e = (EdgeListNode*)malloc(sizeof(EdgeListNode));
        e->adjId = 4; e->weight = 1; e->next = g.vertextlist[1].firstadj; g.vertextlist[1].firstadj = e;
    
        e = (EdgeListNode*)malloc(sizeof(EdgeListNode));
        e->adjId = 5; e->weight = 1; e->next = g.vertextlist[1].firstadj; g.vertextlist[1].firstadj = e;
    
        e = (EdgeListNode*)malloc(sizeof(EdgeListNode));
        e->adjId = 3; e->weight = 3; e->next = g.vertextlist[2].firstadj; g.vertextlist[2].firstadj = e;
    
        e = (EdgeListNode*)malloc(sizeof(EdgeListNode));
        e->adjId = 4; e->weight = 5; e->next = g.vertextlist[2].firstadj; g.vertextlist[2].firstadj = e;
    
        e = (EdgeListNode*)malloc(sizeof(EdgeListNode));
        e->adjId = 3; e->weight = 8; e->next = g.vertextlist[4].firstadj; g.vertextlist[4].firstadj = e;
    
        e = (EdgeListNode*)malloc(sizeof(EdgeListNode));
        e->adjId = 3; e->weight = 1; e->next = g.vertextlist[5].firstadj; g.vertextlist[5].firstadj = e;
    
        vector<int>ans;
        ans = CriticalPath(g);
    
        for(i=0; i<ans.size(); i+=2) {
            cout<<ans[i]<<"->"<<ans[i+1]<<endl;
        }
        cout<<endl;
    
        return 0;
    }
    
    展开全文
  • 最短路径算法

    千次阅读 2014-11-22 20:00:59
    问题描述: 最短路径问题是图论研究中的一个经典算法问题, 旨在寻找图(由结点和路径组成的)中两结点之间的最短路径

    问题描述:

    最短路径问题是图论研究中的一个经典算法问题, 旨在寻找图(由结点和路径组成的)中两结点之间的最短路径。

    所谓单源最短路径问题是指:已知图G=(V,E),我们希望找出从某给定的源结点S∈V到V中的每个结点的最短路径。
    首先,我们可以发现有这样一个事实:如果P是G中从vs到vj的最短路,vi是P中的一个点,那么,从vs沿P到vi的路是从vs到vi的最短路。
    最常用的路径算法有:Dijkstra算法、A*算法、SPFA算法、Bellman-Ford算法、Floyd-Warshall算法、Johnson算法
    以上是参考百度百科,以下分别论述闭包最短通路长度、Dijkstra算法和Floyd算法。

    1.闭包最短通路长度

            定理:设G是带有相对于顶点顺序的邻接矩阵A的图。从的长度为r的不同通路的数目等于的第(i,j)项,其中r为正整数。
    其证明参考离散数学第六版,9.4.6。要理解这个过程也不难,可以从矩阵乘法原理去理解,从公式上理解就是(i,j)=(i,k)*(k,j),如果是通路,它自然不为0了,相当于计数了。从这个定理可以看出,我们在计算时,如果(i,j)的值由0变成非0,此时就是两顶点之间通路长度,即需要至少分几段才能连接两点。最典型的应用是换乘次数最少的路径。

    2.Dijkstra算法

             Dijkstra(迪杰斯特拉)算法是典型的单源最短路径算法,用于计算一个节点到其他所有节点的最短路径。主要特点是以起始点为中心向外层层扩展,直到扩展到终点为止。Dijkstra算法是很有代表性的最短路径算法,在很多专业课程中都作为基本内容有详细的介绍,如数据结构,图论,运筹学等等。注意该算法要求图中不存在负权边。
            算法思想:设G=(V,E)是一个带权有向图,把图中顶点集合V分成两组,第一组为已求出最短路径的顶点集合(用S表示,初始时S中只有一个源点,以后每求得一条最短路径 , 就将加入到集合S中,直到全部顶点都加入到S中,算法就结束了),第二组为其余未确定最短路径的顶点集合(用U表示),按最短路径长度的递增次序依次把第二组的顶点加入S中。在加入的过程中,总保持从源点v到S中各顶点的最短路径长度不大于从源点v到U中任何顶点的最短路径长度。此外,每个顶点对应一个距离,S中的顶点的距离就是从v到此顶点的最短路径长度,U中的顶点的距离,是从v到此顶点只包括S中的顶点为中间顶点的当前最短路径长度。
            算法步骤:
            a.初始时,S只包含源点,即S={v},v的距离为0。U包含除v外的其他顶点,即:U={其余顶点},若v与U中顶点u有边,则w<u,v>正常有权值,若u不是v的出边邻接点,则w<u,v>权值为∞。同时设每个顶点的最优值在L(u)中,L(vi)=无穷,L(起始点)=0;
           b.从U中选取一个距离v最小的顶点k,把k,加入S中(该选定的距离就是v到k的最短路径长度)。
           c.以k为新考虑的中间点,修改U中各顶点的距离;若从源点v到顶点u的距离(经过顶点k)比原来距离(不经过顶点k)短,则修改顶点u的距离值,修改后的距离值的顶点k的距离加上边上的权。即L(v)=min(L(v),L(u)+w(u,v))
           d.重复步骤b和c直到所有顶点都包含在S中。


           理解起来也不是很难,就是从起始点开始,向周边找到最短距离,并记录到每个点,然后找到最短的路重新向周边找且记录。不过对于已经选择的最优点就不要重新计算了。
           为什么这么做,就能找出最优解呢,这里可以先看我的另一篇博文《动态规划-钢条切割》。里面提到,如果一个路径是最优到,那路径中的每一个点到终点也是最优的。同样,我们反过来走也是一样的。但这里和那里面又有点不一样,那里面是,一层一层地求最优解,即相隔1,2,3....点这样求,但实际上这没有广泛的适合性,当网络连接相当复杂时,你无法知道一点到另外一点的最优值,即使是相邻,如果你真的已经求出来了,恭喜你,你明白Dijkstra算法的精髓了。
            正因为我们时常不能很严格地将图分为一层一层的,所以要找到每一个点的最优解时,理解起来比较困难。那么我们怎么找到一个点的最优解呢,怎么样在不知道其它点的最优值时,求出这个点的最优解呢?其实我们人生也是如此,我们想每个选择都最优,其实很难做到。其实,只要大致方向上是对的,踏踏实实里往前走,时刻调整人生的方向,就能走上人生巅峰,迎娶白富美。这里有三个关键,一是大致方向上是对的,不能南辕北辙,二是踏踏实实,三是时刻调整。对,做到这三点很难做到吧,这个算法就教你怎么做到的。
            首先,在起始点找到局部最优解(当然每个相邻点都要计算,你不尝试你怎么知道谁好谁坏呢?所以人生贵在敢于尝试,而且永远都不会忘记这种感觉,因为后面还要用到的),然后定位在那个点,这不难吧。图中标号为2就是,然后以这个点又找到局部最优解,点3。我们就会惊讶发现,原来从点2出发后,转了一圈发现点3又是最优的,说明点2的最优解的探索过程完了,7就是点2的最优解。既然找到了点2的最优解,自然以后就不管它喽,这就是算法中的集合S和U的作用。是吧,在外面转了一图,发现还是点3好,跟谈恋爱一样,虽说初恋不一定很优秀,但是最想念的哈。那我们继续从点3出发找最优解,发现点6是最优的,不过点6已经不是以前的点6了,因为它改了。既然点3不是最优的,说明点3的命运到头了,因为它不能继续保持领先地位,自然要让给下一位,同时点3也完成了自己最优解的使命了。
             这样,一步步地就把每个点的最优解求出来了,同时也不需要计算出每个点的所有情况再作比较,只需要证明它周边有比它更优秀的,来说明它不是所要找的最优路径中的点。同时也发现,它再怎么继续转悠,也不可能找到比它现在还小的数。有人就要问,这不是还没更新么,等之前的点更新之后,再反过来找此点,说不定能找到更小的。这看起来挺有道理的,其实不然,在局部的最优解中,其它的点即使是更新了最优值,同样要比此值要小,为什么呢,无论怎么更新,它始终要从它到初始点的最路径,加上某个值才使它进一步小,话说回来,它顶多是从别的点折返回来,就如点6还得从1-3,3-6给折回去,这样一来,怎么可能有1-2直接最优呢。所以呢,当转悠了一圈后,发现周边还有比我们强的,说明我们自己已经是最优的了,不需要去再去折腾了。这个时候,要么把棒子交给下一个人,要自己继续学习,使自己比以前的自己更强大才行,这就是我们平时说的,当才华不能支撑起野心时,是时候安静下来好好学习了。
             这里,还说一句,为什么这个算法不适合有负数的权值的呢?很简单,因为它依靠的是最优子序列所推测出来的,所以当存在负数时,这就不适用了。不然好不容易把了个最优的,发现下一个权值是负数,这说明上一个找的不是最优的,这不矛盾吗,是不是哈。
            那路径怎么确定呢?L(v)=min(L(v),L(u)+w(u,v)),每一次求每个顶点的最优值,都会产生一个u,即最优点的前一个点,如果这个顶点的值如果后面一直不变,那么它的前驱始终为u,但有改变,则它也改变,所以只要跟踪每一个点的前驱,按图索骥,就可以找到最优路径。
             说到这里,大家应该明白为什么要搞集合S和U了吧,下面就是C程序代码:
    //path的每个值初始化为-1,后面打印时用的
    int dijkstra(int **w,int *path,int n,int begin,int end)
    {
    	begin-=1;end-=1;
    	int i;
    	bool *S=new bool[n];//S,L与文章中的意义一样,这里没有U,因为U是S的余集
    	int *L=new int[n];
    	for(i=0;i<n;i++)//除了起始点为0,其它点的最优值初始为无穷大
    	{
    		L[i]=MAXLEN;
    		path[i]=-1;//初始化path
    	}
    	L[begin]=0;
    	memset(S,0,n*sizeof(S[0]));
    
    	int u=begin,iu;
    	int tmp;
    	while(!S[end])
    	{
    		S[u]=true;
    		for(i=0;i<n;i++)
    			if(!S[i]&&L[u]+w[u][i]<L[i])//u与v的局部最优解,如果有,则替换,!S[i]代表U中的元素
    			{
    				L[i]=L[u]+w[u][i];
    				path[i]=u;//记录前驱
    			}
    
    		tmp=MAXLEN;
    		iu=u;
    		for(i=0;i<n;i++)
    			if(!S[i]&&L[i]!=MAXLEN&&L[i]<tmp)//找出U中元素中最小最优值,即局部最优值
    			{
    				iu=i;//记录是哪个点为局部最优值,然后存入S中
    				tmp=L[i];
    			}
    		u=iu;	
    	}
    	return L[end];
    }
    
    void printPath(int *path,int n,int begin,int end)
    {
    	begin-=1;end-=1;
    	int u=end;
    	while(-1!=path[u])//逆序打印,path的每个值初始化为-1,-1代表起始点
    	{
    		cout<<u+1<<"<=";
    		u=path[u];
    	}
    	cout<<begin+1<<endl;
    }


    3.Floyd算法

           正如大多数教材中所讲到的,求单源点无负边最短路径用Dijkstra,而求所有点最短路径用Floyd。确实,我们将用到Floyd算法,但是,并不是说所有情况下Floyd都是最佳选择。     对于没有学过Floyd的人来说,在掌握了Dijkstra之后遇到All-Pairs最短路径问题的第一反应可能会是:计算所有点的单源点最短路径,不就可以得到所有点的最短路径了吗。简单得描述一下算法就是执行n次Dijkstra算法。 
            Floyd可以说是Warshall算法的扩展了,三个for循环便可以解决一个复杂的问题,应该说是十分经典的。从它的三层循环可以看出,它的复杂度是n3,除了在第二层for中加点判断可以略微提高效率,几乎没有其他办法再减少它的复杂度。 
            比较两种算法,不难得出以下的结论:对于稀疏的图,采用n次Dijkstra比较出色,对于茂密的图,可以使用Floyd算法。另外,Floyd可以处理带负边的图。  

        下面对Floyd算法进行介绍: 
            Floyd算法的基本思想:     可以将问题分解,先找出最短的距离,然后在考虑如何找出对应的行进路线。如何找出最短路径呢,这里还是用到动态规划的知识,对于任何一个城市而言,i到j的最短距离不外乎存在经过i与j之间的k和不经过k两种可能,所以可以令k=1,2,3,...,n(n是城市的数目),在检查d(ij)与d(ik)+d(kj)的值;在此d(ik)与d(kj)分别是目前为止所知道的i到k与k到j的最短距离,因此d(ik)+d(kj)就是i到j经过k的最短距离。所以,若有d(ij)>d(ik)+d(kj),就表示从i出发经过k再到j的距离要比原来的i到j距离短,自然把i到j的d(ij)重写为d(ik)+d(kj),每当一个k查完了,d(ij)就是目前的i到j的最短距离。重复这一过程,最后当查完所有的k时,d(ij)里面存放的就是i到j之间的最短距离了。这样我们就可以用3个for循环就可以完成了。
    for ( int i = 0; i < 节点个数; ++i )
    {
        for ( int j = 0; j < 节点个数; ++j )
        {
            for ( int k = 0; k < 节点个数; ++k )
            {
                if ( Dis[i][k] + Dis[k][j] < Dis[i][j] )
                {
                    // 找到更短路径
                    Dis[i][j] = Dis[i][k] + Dis[k][j];
                }
            }
        }
    }
        但是这里我们要注意循环的嵌套顺序,如果把检查所有节点X放在最内层,那么结果将是不正确的,为什么呢?因为这样便过早的把i到j的最短路径确定下来了,而当后面存在更短的路径时,已经不再会更新了。具体来讲,这就是固定两端i,j,还是固定中间k的选择问题。这两个有什么区别呢。如果是固定两端,当k遍历完时,ij之间的最短距离就算完了,这对吗?很显然此时每个结点的最优值都还不确定呢,那结果就不一定对的,特别是算的越早的越不准。但如果我们把k固定,固定变化i,j,那么每一次都会把所有点经过k的点的最短距离算出来,当k算完,所有点的结果就算完了。这就是所有点对一个点的最小距离算完后,每个点都刷新一次,而前一种,每个点的刷新次数不一样,这公平吗?哈哈!
        接下来就要看一看如何找出最短路径所行经的城市了,这里要用到另一个矩阵P,它的定义是这样的:p(ij)的值如果为p,就表示i到j的最短行经为i->p...->j,也就是说p是i到j的最短行径中的j之前的第一个城市。P矩阵的初值为p(ij)=j。有了这个矩阵之后,要找最短路径就轻而易举了。对于i到j而言找出p(ij),令为q,就知道了路径i->q->...->j;再去找p(qj),再去找p(qj),如果值为r,i到q的最短路径为q->r...->j;所以一再反复,到了某个p(tj)的值为j时,就表示t到j的最短路径为t->j,就会的到答案了,i到j的最短行径为i->q->r...->t->j。
         但是,如何动态的回填P矩阵的值呢?回想一下,当d(ij)>d(ik)+d(kj)时,就要让i到j的最短路径改为走i->...->k->...->j这一条路,但是d(kj)的值是已知的,换句话说,就是k->...->j这条路是已知的,所以k->...->j这条路上j的上一个城市(即p(kj))也是已知的,当然,因为要改走i->...->k->...->j这一条路,j的上一个城市正好是p(kj)。所以一旦发现d(ij)>d(ik)+d(kj),就把p(kj)存入p(ij)。
         可以这么想当d(ij)>d(ik)+d(kj)时,也就是说i->...->k->...->j,那么k应该在什么位置呢?我们知道path(i,j)一定由原先的值变化而来的,而且是由上一个path变化而来的,如果每一次变化都会造成i->k->...->j或i->...->k->j,这样的话,我们就可以递推得到我们所想要路径。那么如何才能这样,而不是i->...->k->...->j中间的任何一个呢?path(i,j)=path(?,?)呢?是path(i,k),还是path(k,j)?我们可以这么想,如果发生了d(ij)>d(ik)+d(kj)这么一个东西,抛开是不是最短的路径,但i,j,k之定通路,不仅是通路,而且,每次变化的路径是有一定的继承性的,因为它至少是经过第k点的最优路径。当k+1时,如果值没发生变化,则变化的是k~j而不是i~j,如果发生了变化了,说明上一个不是最佳的,需要调整。所以每次变化的一定是i->k->...->j或i->...->k->j。下面有一个例子说明:

          现在分析2~1之间的最短路径。k=1,2时,2到1之间的路径依然是无穷,因为是它们本身的节点,但此时别其它点已经计算到1,2暂时的最佳路径,比如3~1。当k=3时,2~3的路径计算出来,同时3~1的之前就计算出来了,所以些Path(2,1)=3。当k=4的时候,3~1的最佳路径发生变化,但与2~1的最佳无关,除非能够计算出来2~4~1的路径更短。如果你仔细思考的话,会发现如果path(i,j)只变化一次的话,那它的路径就是i~k~j,至于k~j是多少,那个是后续的事,如果变化了多次,它依然是i~k~j,因为些算法只计算2个长度的路径,所以每次的k一定会挨着i。会不会发生i~k,和k~j同时发生呢,会!但如果i~k发生了变化,那么k~j原先就会失效,得重新寻找更新了,所以从不变的角度来讲,i~k这个过程始终不会发生变化,这样我们可以通过寻找i~k~j,k~v~j,....找到我们所需要的路径。所以只需要将path(i,j)=path(i,k)这样赋值就可以了,如果是path(i,j)=path(k,j),这就和刚才分析是反过来了,同时初值做一次翻转。
          上面解决了,那么path如何赋初值呢?那就看k=1是啥情况喽,很明显,Path(i,1)=1,因为i~1~1嘛,所以有path(i,j)=j。这样我们就得到其C语言程序了,如下:
    #define MAXLEN 10000
    void initPath(int **path,int n)//初始化path
    {
    	for(int i=0;i<n;i++)
    		for(int j=0;j<n;j++)
    			path[i][j]=j;
    }
    
    void floyd(int **d,int **path,int n)
    {
    	int tmp;
    	for(int k=0;k<n;k++)
    		for(int i=0;i<n;i++)
    			for(int j=0;j<n;j++)
    			{
    				tmp=d[i][k]+d[k][j];
    				if(tmp<d[i][j])
    				{
    					d[i][j]=tmp;
    					path[i][j]=path[i][k];//记录i~k之间的路径
    				}
    
    			}
    }
    
    void printPath(int **d,int **path,int n,int begin,int end)
    {
    	begin-=1;end-=1;
    	if(MAXLEN==d[begin][end])//这里如果不是通路,就会出现这情况
    		cout<<"There is no path from "<<begin<<" to "<<end<<endl;
    	else
    		cout<<"The distance of the shortest path from "<<begin+1<<" to "<<end+1
    		<<" is "<<d[begin][end]<<" !"<<endl;
    	cout<<begin+1<<"->";//打印原点
    	int v=path[begin][end];//获得第一个路径顶点下标
    	while(v!=end)//如果路径顶点下标不是终点
    	{
    		cout<<v+1<<"->";//打印路径顶点
    		v=path[v][end];//获得下一个路径顶点下标
    	}
    	cout<<end+1<<endl;//打印终点
    }

    以上皆用到

    #define MAXLEN 10000

    4.参考资料:

    http://developer.51cto.com/art/201403/433874.htm
    http://www.cnblogs.com/biyeymyhjob/archive/2012/07/31/2615833.html
    http://www.cnblogs.com/twjcnblog/archive/2011/09/07/2170306.html
    展开全文
  • 关键路径的概念和算法

    千次阅读 2018-10-02 17:22:43
    AOE网:在一个表示工程的带权有向图中,用顶点表示事件,用有向边表示活动,边上的权值表示活动的持续时间,称这样的有向图叫做边表示活动的网,简称AOE网。AOE网中没有入边的顶点称为始点(或源点),...关键路径...
  • Astar A*算法 最短路径算法

    千次阅读 2018-12-10 20:23:31
    还能保证找到的是一条最短路径,它是一种常见的启发式搜索算法,类似于Dijkstra算法一样的最短路径查找算法,很多游戏应用中的路径搜索基本都是采用这种算法或者是A*算法的变种。 下面我们来了解...
  • 最短路径算法对比

    2018-10-22 13:11:10
    目录 ...五、最短路径算法对比分析 一、只有5行的算法---Floyd-Warshall  已知一些点,和这些点间的路径,求任意两个点之间的最短路径,这个问题也被称为“多源最短路径问题”。  最直接想...
  • 算法8-10:最短路径算法之拓扑排序

    千次阅读 2014-06-26 21:04:56
    算法基本思想就是按照拓扑排序的顺序依次将每个顶点加入到最短路径树中,每次加入时将该顶点延伸出的所有顶点进行“放松”操作。这种算法的复杂度是E+V。 代码 这种算法的代码比Dijkstra还要...
  • Floyd算法是解决任意两点间的最短路径的一种算法,可以正确处理带权有向图或...Floyd算法基本思想: 1. 利用二维数组dist[i][j]记录当前vi到vj的最短路径长度,数组dist的初值等于图的带权邻接矩阵; 2. 集合S记录当前
  • 看过算法导论的童鞋都晓得,最短路径最重要的一个函数就是Relax()了,这是基于贪心算法的最短路径算法的基础。 见上面的示意图,设原点为s,每个vertex的值为每个vertex距离原点s的当前最短距离,在图(a)中,
  • 最短路径算法详细介绍

    千次阅读 2015-03-10 16:17:26
    据 Drew 所知最短路经算法现在重要的应用有计算机网络路由算法,机器人探路,交通路线... 静态路径最短路径算法是外界环境不变,计算最短路径。主要有Dijkstra算法,A*(A Star)算法。   动态路径最短路是外界
  • 迪杰斯特拉算法算法思想: 设有两个顶点集合S和T,集合S存放途中已经找到最短路径的顶点,集合T存放的是途中剩余顶点。初始状态是,集合S只包含源点V0,然后不断从集合T中 选取到顶点V0的路径长度最短的顶点Vu并入...
  • 求解两点间最短路径算法

    千次阅读 2020-07-19 23:42:40
    最短路径算法1.Dijkstra算法2.Bellman-Ford算法3.SPFA算法4.Floyd算法几种最短路径算法的对比Dijkstra算法、Bellman-Ford算法和SPFA算法的对比Dijkstra算法和Floyd算法的对比 最短路径算法 单源最短路算法:已知...
  • 算法思想

    千次阅读 2013-01-12 10:33:31
    Taken from "Introduction to The Design and Analysis of Algorithms" by Anany Levitin ...节选自《算法设计与分析基础》潘彦 译 蛮力法 就像宝剑不是撬棍一样,科学也很少使用蛮力。 ——Edward
  • 本文主要介绍了拓扑排序、关键路径、AOE、AOV的基本概念,拓扑排序和关键路径算法思想,以及它们的实现。
  • Floyd算法基本思想是:设集合S的初始状态为空,然后依次向集合S中加入顶点 0,1,...,n-1,每次加入一个顶点,用二维数组d保存各条最短路径的长度,其中d[i][j]存放的是顶点i到顶点j的最短路径的长度。...
  • 算法思想总结

    千次阅读 2016-07-15 08:06:38
    一、基本概念  在计算机科学中,分治法是一种很重要的算法。字面上的解释是“分而治之”,就是把一个复杂的问题分成两个或更多的相同或相似的子问题,再把子问题分成更小的子问题……直到最后子问题可以简单的直接...
  • 路径识别算法

    千次阅读 2020-10-16 16:45:42
    随着各省市高速公路的不断建设,基本上建成了大小规模不等的联网收费...本文介绍了多路径识别的多种算法,并着重分析了识别算法中的汽车牌照识别,根据车牌图像特点,对车牌识别算法关键环节包括数字图像预处理,车牌
  • 这里写自定义目录标题移动机器人路径规划算法介绍及A*算法...对于移动机器人的研发最为基本的问题就是如何对机器人的运动进行控制,在目前众多的机器人路径规划算法中,针对静态、动态环境存在着很多不同的解决方案...
  • 路径规划算法简介

    千次阅读 2019-09-24 01:50:29
    路径规划算法简介 1.涉及问题: 这里的路径规划是指如何寻找一条从给定起点到终点的路径,使机器人沿该路径移动的过程中不与障碍物发生碰撞且路程最短或移动代价最小。 2.简要介绍的算法: 1.遗传算法; 2.模拟退火...
  • 数据结构与算法——最短路径Dijkstra算法的C++实现

    万次阅读 多人点赞 2016-05-04 13:26:04
    数据结构与算法——最短路径Dijkstra算法的C++实现
  • 带权图的最短路径算法(Dijkstra)实现

    千次阅读 2017-11-17 15:21:00
    本文实现带权图的最短路径算法。给定图中一个顶点,求解该顶点到图中所有其他顶点的最短路径 以及 最短路径的长度。在决定写这篇文章之前,在网上找了很多关于Dijkstra算法实现,但大部分是不带权的。不带权的...
  • 有向图的最短路径算法

    千次阅读 2016-07-27 22:52:47
    最短路径算法属于数据结构的图的应用知识。先介绍基本的图的概念。 图由顶点集和边集组成。(一张图里不就是有顶点和边)。图中边带有方向就是有向图,否则就是无向图。图的存储结构分为邻接表和邻接矩阵。(邻接表...
  • 五大算法设计思想

    万次阅读 多人点赞 2018-05-12 10:18:38
    思想策略: 对于一个规模为n的问题,若该问题可以容易地解决(比如说规模n较小)则直接解决,否则将其分解为k个规模较小的子问题,这些子问题互相独立且与原问题形式相同,递归地解这些子问题,然后将各子问题的解...
  • D*路径搜索算法原理解析及Python实现

    万次阅读 多人点赞 2018-12-17 21:18:30
    D*路径搜索算法原理解析及Python实现1.D*算法简述2.操作2.1扩张 1.D*算法简述 D*是以下三种相关增量搜索算法之一: 最初的D* (Anthony Stentz的)是一种知情的增量搜索算法。 Focussed D是Anthony Stentz设计的一种...
  • 五大算法思想

    千次阅读 2015-07-09 13:53:19
    五大算法思想 分治算法 一、基本概念  在计算机科学中,分治法是一种很重要的算法。字面上的解释是“分而治之”,就是把一个复杂的问题分成两个或更多的相同或相似的子问题,再把子问题分成更小的子问题...
  • Dijkstra 最短路径算法的一种高效率实现Dijkstra 最短路径算法的一种高效率实现Dijkstra 最短路径算法的一种高效率实现[日期:2005-2-7]武汉测绘科技大学学报 作者:乐阳 龚健雅摘 要 在已存在的一些最短路径算法...
  • 五大常用算法思想

    千次阅读 2016-08-18 17:32:30
    最近有空学习了一下算法,参考网上文章,将五中常用的算法思想汇总一下,方便以后工作使用1 分治算法一、基本思想及策略 分治法的设计思想是:将一个难以直接解决的大问题,分割成一些规模较小的相同问题,以便...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 35,758
精华内容 14,303
关键字:

关键路径算法基本思想