财经

css 一张图片做导航财经

17 4月 , 2019  

       
只想说:温故而知新,可以为师矣。小编大2的《数据结构》是由申先生讲的,那时候有个别精通,猜想太理论化了(ps:或然是因为本人睡觉了);明日把老王的2011年课件又看了二回,给大2的儿女们又讲了3次,随手谷歌(Google)了N多资料,算是深透搞懂了最短路线难点。请读者尽享……

       
小编确信:未有不佳的上学的小孩子,唯有垃圾的启蒙。然则并未有人理所当然的对你好,所以要学会感恩。

style=”font-family: 华文大篆; font-size: x-large;”>1.难题引进

       
难点:从某顶点出发,沿图的边达到另1顶点所通过的门道中, style=”font-family: 华文行草; font-size: x-large;”>各边上权值之和纤维的一条路径——最短路线。 style=”font-family: 华文大篆; font-size: x-large;”>消除最短路的标题有以下算法,Dijkstra算法,Bellman-Ford算法,Floyd算法和SPFA算法,其它还有有名的启发式搜索算法A*,不过A*准备单独出1篇, style=”font-family: 华文大篆; font-size: x-large;”>当中Floyd算法能够求解任意两点间的最短路线的长短。作者以为随便贰个最短路算法都是遵照那样八个真相: style=”font-family: 华文黑体; font-size: x-large;”>从任意节点A到任意节点B的最短路线不外乎二种恐怕, style=”font-family: 华文行书; font-size: x-large;”>壹是一直从A到B,贰是从A经过若干个节点到B。

style=”font-family: 华文楷书; font-size: x-large;”>2.Dijkstra算法

       
该算法在《数据结构》课本里是以贪求的款型疏解的,可是在《运筹学》教材里被编辑在动态规划章节,建议读者两篇都看看。

           style=”font-family: 华文小篆; font-size: x-large;”>财经 1

       
观看右侧表格发现除最后3个节点外其他均一度求出最短路线。

        (一)  
迪杰Stella(Dijkstra)算法 style=”font-family: 华文燕体; font-size: x-large;”>按路线长度(看下边表格的最后1行,正是next点)递增次序爆发最短路线。 style=”font-family: 华文行草; font-size: x-large;”>先把V分成两组:

  • style=”font-family: 华文行草; font-size: x-large;”>S:已求出最短路径的终端的聚合
  • style=”font-family: 华文燕书; font-size: x-large;”>V-S=T:尚未规定最短路线的终极集合

       
将T中顶点按最短路径递增的次第参预到S中, style=”font-family: 华文楷书; font-size: x-large;”>依据:能够作证V0到T中顶点Vk的最短路线,或是从V0到Vk的 style=”font-family: 华文甲骨文; font-size: x-large;”>直接路子的权值或是从V0经S中顶点到Vk的门道权值之和 style=”font-family: 华文大篆; font-size: x-large;”>(反证法可证,说实话,真不通晓啊)。

        (二)  
求最短路线步骤

  1. 初使时令
    S={V0},T={别的顶点},T中顶点对应的距离值, style=”font-family: 华文黑体; font-size: x-large;”>
    若存在<V0,Vi>,为<V0,Vi>弧上的权值(和SPFA开头化方式分裂), style=”font-family: 华文燕体; font-size: x-large;”>若不存在<V0,Vi>,为Inf。
  2. style=”font-family: 华文小篆; font-size: x-large;”>从T中甄选多个其距离值为最小的顶点W(贪心呈未来此处),参与S(注意不是一贯从S集合中挑选,明白那个对于精通vis数组的效应至关心重视要), style=”font-family: 华文黑体; font-size: x-large;”>对T中顶点的距离值进行退换:若加进W作中间顶点,从V0到Vi的偏离值比不加W的不2秘籍要短,则修改此距离值 style=”font-family: 华文石籀文; font-size: x-large;”>(下边几个并列for循环,使用最小点更新)。
  3. style=”font-family: 华文陶文; font-size: x-large;”>重复上述手续,直到S中含有全数终端,即S=V截止(表达最外层是除源点外的遍历)。

       
上边是上图的求解进程,按列来看,第二列是最先化进程,最终一行是历次求得的next点。

           style=”font-family: 华文楷书; font-size: x-large;”>财经 2

        (三)  
难点:Dijkstar能还是不可能处理负权边?(来自《图论》)

            
答案是不能够,那与贪心选拔性质有关(ps:貌似依旧动态规划啊,晕了), style=”font-family: 华文金鼎文; font-size: x-large;”>每次都找3个距源点近年来的点(dmin),然后将该距离定为那个点到起源的最短路线;但若是存在负权边,那就有望先经过并不是距起点如今的一个次优点(dmin’),再经过这几个负权边L(L<0),使得路线之和越来越小(dmin’+L<dmin),则dmin’+L成为最短路线,并不是dmin,那样dijkstra就被囧掉了。比如n=三,邻接矩阵:
0,3,4
3,0,-2
4,-2,0,用dijkstra求得d[1,2]=3,事实上d[1,2]=二,便是通过了一-三-2驱动路线减小。不知道讲得驾驭不知道。

style=”font-family: 华文黑体; font-size: x-large;”>2.Floyd算法

       
参考了银川理工牛帅(方今在腾讯网)的博客。

       
Floyd算法的骨干考虑如下:从随机节点A到任意节点B的最短路线不外乎2种恐怕,1是直接从A到B,二是从A经过几个节点到B,所以,我们如果dist(AB)为节点A到节点B的最短路线的距离,对于每3个节点K,大家检查dist(AK)

  • dist(KB) <
    dist(AB)是或不是建立,若是建立,表明从A到K再到B的渠道比A直接到B的门道短,大家便安装
    dist(AB) = dist(AK) +
    dist(KB),那样1来,当大家遍历完全数节点K,dist(AB)中记录的正是A到B的最短路线的偏离。

       
很简短吗,代码看起来恐怕像下边那样:

for (int i=0; i<n; ++i) {

  for (int j=0; j<n; ++j) {

    for (int k=0; k<n; ++k) {

      if (dist[i][k] + dist[k][j] < dist[i][j] ) {

        dist[i][j] = dist[i][k] + dist[k][j];

      }

    }

  }

}

       
然而此间我们要留意循环的嵌套顺序,倘使把检查有着节点K放在最内层,那么结果将是不科学的,为何吧?因为那样便太早的把i到j的最短路线明确下来了,而当后边存在更加短的门路时,已经不复会更新了。

       
让大家来看二个例子,看下图:

style=”font-family: 华文钟鼓文; font-size: x-large;”>财经 3

       
图中革命的数字代表边的权重。借使大家在最内层检查有着节点K,那么对于A->B,我们只可以发现一条路子,正是A->B,路线距离为九,而这显明是不得法的,真实的最短路线是A->D->C->B,路线距离为陆。变成错误的原故即是我们把检查有着节点K放在最内层,形成太早的把A到B的最短路线明确下来了,当分明A->B的最短路线时dist(AC)尚未被计算。所以,我们必要改写循环顺序,如下:

       
ps:个人感到,那和银行家算法推断安全情状(每一个财富去测试全数线程),树状数组更新(更新具备有关项)同样的思念。

for (int k=0; k<n; ++k) {

  for (int i=0; i<n; ++i) {

    for (int j=0; j<n; ++j) {

            /*

            实际中为防止溢出,往往需要选判断 dist[i][k]和dist[k][j

            都不是Inf ,只要一个是Inf,那么就肯定不必更新。 

            */

      if (dist[i][k] + dist[k][j] < dist[i][j] ) {

        dist[i][j] = dist[i][k] + dist[k][j];

      }

    }

  }

}

       
若是依旧看不懂,那就用草稿纸模拟三回,之后您就会茅塞顿开。半个时辰足矣(早精晓的话会省去不胜枚举个半时辰了。。财经 4

      
再来看门道保存难题:

void floyd() {

      for(int i=1; i<=n ; i++){

        for(int j=1; j<= n; j++){

          if(map[i][j]==Inf){

               path[i][j] = -1;//表示  i -> j 不通 

          }else{

               path[i][j] = i;// 表示 i -> j 前驱为 i

          }

        }

      }

      for(int k=1; k<=n; k++) {

        for(int i=1; i<=n; i++) {

          for(int j=1; j<=n; j++) {

            if(!(dist[i][k]==Inf||dist[k][j]==Inf)&&dist[i][j] > dist[i][k] + dist[k][j]) {

              dist[i][j] = dist[i][k] + dist[k][j];

              //path[i][k] = i;//删掉

              path[i][j] = path[k][j];

            }

          }

        }

      }

    }

    void printPath(int from, int to) {

        /*

         * 这是倒序输出,若想正序可放入栈中,然后输出。

         * 

         * 这样的输出为什么正确呢?个人认为用到了最优子结构性质,

         * 即最短路径的子路径仍然是最短路径

         */

        while(path[from][to]!=from) {

            System.out.print(path[from][to] +"");

            to = path[from][to];

        }

    }

       
《数据结构》课本上的那种办法本身将来依旧不想看,瞧着不舒适……

       
Floyd算法另壹种精晓DP,为辩白爱好者准备的, style=”font-family: 华文陶文; font-size: x-large;”>上边那些方式的算法其实是Floyd算法的精简版,而真的的Floyd算法是壹种基于DP(Dynamic
Programming)的最短路线算法。 style=”font-family: 华文甲骨文; font-size: x-large;”>设图G中n
个顶峰的号码为一到n。令c [i, j, k]表示从i 到j 的最短路线的尺寸,在那之中k
表示该路径中的最大终端,也正是说c[i,j,k]那条最短路线所通过的中级顶点最大不超越k。由此,要是G中蕴藏边<i,
j>,则c[i, j, 0] =边<i, j> 的长度;若i= j
,则c[i,j,0]=0;假设G中不带有边<i, j>,则c (i, j, 0)=
+∞。c[i, j, n] 则是从i 到j
的最短路线的长短。对于自由的k>0,通过分析能够获取:中间顶点不超越k
的i 到j
的最短路线有二种可能:该路径含或不含中间顶点k。若不含,则该路径长度应为c[i,
j, k-1],不然长度为 c[i, k, k-1] +c [k, j, k-1]。c[i, j,
k]可取两者中的最小值。状态转移方程:c[i, j, k]=min{c[i, j, k-1],
c [i, k, k-1]+c [k, j,
k-1]},k>0。那样,难点便具备了最优子结构性情,能够用动态规划格局来求解。

       
看另三个DP(直接引用王先生课件)

                       style=”font-family: 华文燕体; font-size: x-large;”>财经 5

<html xmlns=”http://www.w3.org/1999/xhtml“>
<head>
<meta http-equiv=”Content-Type” content=”text/html; charset=gb2312″
/>
<title></title>
<style type=”text/css”>
<!–
* {margin:0; padding:0; font-size:12; list-style-type:none; }
#mini_nav {width:390px; height:38px; overflow:hidden; margin:50px
auto; background:url(nav.png) no-repeat 0 0;}
#mini_nav li {width:65px; height:38px; float:left;}
#mini_nav li a {display:block; width:65px; height:38px;
padding-top:40px; overflow:hidden;}
#mini_nav li a:hover {background:url(nav.png) no-repeat;}

 

#mini_nav li.nav1 a:hover {background-position:0 -38px;}
#mini_nav li.nav2 a:hover {background-position:-65px -38px;}
#mini_nav li.nav3 a:hover {background-position:-130px -38px;}
#mini_nav li.nav4 a:hover {background-position:-195px -38px;}
#mini_nav li.nav5 a:hover {background-position:-260px -38px;}
#mini_nav li.nav6 a:hover {background-position:-325px -38px;}
</style>
</head>
 
<body>
<ul id=”mini_nav”>
 <li class=”nav1″><a href=”#”
title=”财经”>财经</a></li>
 <li class=”nav2″><a href=”#”
title=”商业”>商业</a></li>
 <li class=”nav3″><a href=”#”
title=”管理”>管理</a></li>
 <li class=”nav4″><a href=”#”
title=”领袖”>领袖</a></li>
 <li class=”nav5″><a href=”#”
title=”协会”>协会</a></li>
 <li class=”nav6″><a href=”#”
title=”博客”>博客</a></li>
</ul>
</body>
</html>

       
说了这么多,相信读者已经尝试了,大家看壹道例题,以ZOJ
1092为例: style=”font-family: 华文行草; font-size: x-large;”>给你一组国家和国度间的有个别货币汇率兑换表,问您是否存在1种艺术,从一种货币出发,经过一类别的货币兑换,最后回来该货币时超越出发时的数值(ps:那就是所谓的投机倒把吧),上面是1组输入。
3    //国家数
USDollar  //国家名
BritishPound
FrenchFranc
   3    //货币兑换数
USDollar 0.5 BritishPound  //部分货币汇率兑换表
BritishPound 10.0 FrenchFranc
FrenchFranc 0.21 USDollar

       
月赛做的题,但是当下用的思路是求强连通分量(ps:明明说的,那时小编和华杰感到好有道理),也没做出来,未来了解了直接floyd算法就ok了。

       
思路分析:输入的时候能够运用Map<String,Integer> map = new
HashMap<String,Integer>()首倘使为着获取重新包涵汇率输入时候的下标以建图(感到本人写的好拗口),大概第二回直接存入String数组str,再度输入的时候每趟遍历str数组,假诺equals那么就把str的下标赋值给该币种建图。上边正是floyd算法啦,开首化其余点为-一,对角线为一,采纳乘法更新求最大值。

style=”font-family: 华文草书; font-size: x-large;”>三.Bellman-Ford算法

       
为了能够求解边上带有负值的单源最短路线难题,Bellman(Bell曼,动态规划建议者)和Ford(Ford)提议了从起点逐次绕过别的顶点,以减少达到终点的最短路线长度的方式。 style=”font-family: 华文钟鼓文; font-size: x-large;”>
Bellman-ford算法是求含负权图的单源最短路线算法,作用异常低,但代码很轻巧写。即进行不停地松弛,每一遍松弛把每条边都更新一下,若n-1次松弛后还是能够更新,则评释图中有负环,不能得出结果,不然就打响完结。Bellman-ford算法有二个小优化:每一趟松弛先设二个flag,初值为FALSE,若有边更新则赋值为TRUE,最后只要照旧FALSE则一贯成功脱离。Bellman-ford算法浪费了成都百货上千时辰做无须求的松散,所以SPFA算法用队列实行了优化,效果格外醒目,高效神乎其神。SPFA还有SLF,LLL,滚动数组等优化。

       
关于SPFA,请看俺那一篇 style=”font-family: 华文金鼎文; font-size: x-large;”>http://www.cnblogs.com/hxsyl/p/3248391.html

       
style=”font-family: 华文大篆; font-size: x-large;”>递推公式(求顶点u到起点v的最短路线):

         dist
1 [u] = Edge[v][u]

         dist
k [u] = min{ dist k-1 [u], min{ dist k-1 [j] + Edge[j][u] }
}, j=0,1,…,n-1,j≠u

        
Dijkstra算法和贝尔man算法思想有不小的界别: style=”font-family: 华文燕体; font-size: x-large;”>Dijkstra算法在求解过程中,起点到集合S内各顶点的最短路线壹旦求出,则之后不改变了, style=”font-family: 华文甲骨文; font-size: x-large;”>修改 
的唯有是源点到T集合中各顶点的最短路径长度。 style=”font-family: 华文石籀文; font-size: x-large;”>Bellman算法在求解进度中,每趟循环都要修改全数终端的dist[
],也正是谈到点到各顶点最短路线长度一向要到Bellman算法截止才规定下来。

       
算法适用规则

  • style=”font-family: 华文草书; font-size: x-large;”>一.单源最短路线(从起点s到别的具有顶点v)
  • style=”font-family: 华文燕体; font-size: x-large;”>有向图&无向图(无向图能够看成(u,v),(v,u)同属于边集E的有向图)
  • style=”font-family: 华文小篆; font-size: x-large;”>边权可正可负(如有负权回路输出错误提示)
  • style=”font-family: 华文草书; font-size: x-large;”>差分约束系统(于今貌似只看过壹道题)

       
贝尔man-Ford算法描述:

  1. style=”font-family: 华文燕体; font-size: x-large;”>初叶化:将除起点外的具备终端的最短距离臆想值
    d[v] ←+∞, d[s] ←0
  2. style=”font-family: 华文小篆; font-size: x-large;”>迭代求解:反复对边集E中的每条边进行松弛操作,使得顶点集V中的每种顶点v的最短距离臆想值稳步逼近其最短距离;(运营|v|-2遍,看上边包车型客车描述性注解(当做树))
  3. style=”font-family: 华文楷书; font-size: x-large;”>核查负权回路:判别边集E中的每一条边的五个端点是不是收敛。假若存在未熄灭的极限,则算法重回false,表明难题无解;不然算法重临true,并且从起点可达的顶点v的最短距离保存在d[v]中

       
描述性注明:(这些解释很好)

       
首先提出,图的轻巧一条最短路线既不可能包蕴负权回路,也不会蕴藏正权回路,由此它最多包罗|v|-一条边。

style=”font-family: 华文小篆; font-size: x-large;”>其次,从源点s可达的全部终端即使存在最短路线,则那么些最短路线构成1个以s为根的最短路径树。Bellman-Ford算法的迭代松弛操作,实际上正是按顶点距离s的层次,逐层生成那棵最短路线树的历程。

style=”font-family: 华文草书; font-size: x-large;”>在对每条边实行3遍松弛的时候,生成了从s出发,层次至多为一的那几个树枝。相当于说,找到了与s至多有壹条边相联的那贰个极端的最短路线;对每条边举办第二遍松弛的时候,生成了第①层次的树枝,正是说找到了通过贰条边相连的那一个极端的最短路径……。因为最短路线最多只含有|v|-一条边,所以,只须求循环|v|-三次。

style=”font-family: 华文小篆; font-size: x-large;”>每实践一回松弛操作,最短路线树上就会有1层顶点达到其最短距离,此后那层顶点的最短距离值就会直接保持不改变,不再受持续松弛操作的熏陶。(可是,每趟还要判定松弛,那里浪费了大批量的年月,那便是Bellman-Ford算法效用底下的来头,也多亏SPFA优化的所在)。

style=”font-family: 华文仿宋; font-size: x-large;”>财经 6 style=”font-family: 华文宋体; font-size: x-large;”>,如图(没找到画图工具的射线),要是B和C的最短路线不创新,那么点D的最短路线肯定也无力回天立异,那正是优化所在。

style=”font-family: 华文钟鼓文; font-size: x-large;”>倘诺未有负权回路,由于最短路径树的惊人最八只好是|v|-壹,所以最多通过|v|-一回松弛操作后,全体从s可达的顶点必将求出最短距离。若是d[v]仍维持 +∞,则注脚从s到v不可达。

style=”font-family: 华文石籀文; font-size: x-large;”>固然有负权回路,那么第
|v|-一 遍松弛操作还是会马到功成,那时,负权回路上的极限不会消退。

          style=”font-family: 甲骨文; font-size: 1八pt;”> 参考了《图论》。 style=”font-family: 华文草书; font-size: x-large;”>

       
难点: style=”font-family: 华文燕体; font-size: x-large;”>Bellman-福特算法是不是必然要循环n-贰遍么? style=”font-family: 华文甲骨文; font-size: x-large;”>未必!其实若是在某次循环进程中,思量每条边后,都没能改换方今源点到持有终端的最短路线长度,那么Bellman-Ford算法就足以提前截止了(开篇提出的小优化正是这些)。

       
上代码(参考了牛帅的博客)

#include<iostream>

#include<cstdio>

using namespace std;

#define MAX 0x3f3f3f3f

#define N 1010

int nodenum, edgenum, original; //点,边,起点

typedef struct Edge //边

{

  int u, v;

  int cost;

}Edge;

Edge edge[N];

int dis[N], pre[N];

bool Bellman_Ford()

{

  for(int i = 1; i <= nodenum; ++i) //初始化

    dis[i] = (i == original ? 0 : MAX);

  for(int i = 1; i <= nodenum - 1; ++i)

    for(int j = 1; j <= edgenum; ++j)

      if(dis[edge[j].v] > dis[edge[j].u] + edge[j].cost) //松弛(顺序一定不能反~)

      {

        dis[edge[j].v] = dis[edge[j].u] + edge[j].cost;

        pre[edge[j].v] = edge[j].u;

      }

      bool flag = 1; //判断是否含有负权回路

      for(int i = 1; i <= edgenum; ++i)

        if(dis[edge[i].v] > dis[edge[i].u] + edge[i].cost)

        {

          flag = 0;

          break;

        }

        return flag;

}

void print_path(int root) //打印最短路的路径(反向)

{

  while(root != pre[root]) //前驱

  {

    printf("%d-->", root);

    root = pre[root];

  }

  if(root == pre[root])

    printf("%d\n", root);

}

int main()

{

  scanf("%d%d%d", &nodenum, &edgenum, &original);

  pre[original] = original;

  for(int i = 1; i <= edgenum; ++i)

  {

    scanf("%d%d%d", &edge[i].u, &edge[i].v, &edge[i].cost);

  }

  if(Bellman_Ford())

    for(int i = 1; i <= nodenum; ++i) //每个点最短路

    {

      printf("%d\n", dis[i]);

      printf("Path:");

      print_path(i);

    }

  else

    printf("have negative circle\n");

  return 0;

}

style=”font-family: 华文大篆; font-size: x-large;”>肆.SPFA算法

       
用一个队列来进展维护。初始时将源加入队列。每趟从队列中收取3个因素,并对具有与她相邻的点开始展览松弛 style=”font-family: 华文行书; font-size: x-large;”>,若有些相邻的点松弛成功,则将其入队。直到队列为空时算法甘休; style=”font-family: 华文楷体; font-size: x-large;”>那个算法,简而言之正是队列优化的bellman-ford,利用了各样点不会更新次数太多的本性 style=”font-family: 华文小篆; font-size: x-large;”>发明的此算法(看本身上边11分图,唯有相邻点更新了,该点才有望更新)

         style=”font-family: 华文燕体; font-size: x-large;”>代码参见  style=”font-family: 华文燕体; font-size: x-large;”>:  style=”font-family: 华文行书; font-size: x-large;”>http://www.cnblogs.com/hxsyl/p/3248391.html

style=”font-family: 华文宋体; font-size: x-large;”>伍.趣闻

       
整理该篇博文的时候,一男子发布网址到大家群,网址很完美,一牛神(acmol)使用fork炸弹,结果服务器立马挂啦,退换后又挂啦,目测近年来最棒挂中。。。

style=”font-family: 华文行书; font-size: x-large;”>陆、欢迎加群

style=”font-family: 华文石籀文; font-size: x-large;”>  本群创建于二〇一三肆.2九%/四:
 CodeForFuture(1633541一柒,左侧有加群链接)……本群专注于互连网、电子商务及数据挖掘,群内成员来自各大高校的硕士和本科生(比如南开东军政大学学、北大、中大、东京(Tokyo)联合大学、华南理工科、江南京大学学、北京航空航天津高校学、计算机技术研商所、上理、北京邮政和邮电通讯高校,北交,山大、布里斯托地质、南平院、同济大学、南京经济高校,伊斯坦布尔赫鲁大学学、埃德蒙顿理工科、中夏族民共和国矿业余大学学、莱比锡科学和技术、华师、湖北金融,华科、上海大学、河海、暨南大学、互连网切磋所、清华、广东科技(science and technology)、哈工大,中南,吉林理工、深圳大学、四川大学,萨尔瓦多商业余大学学……不再1一列举)以及各大集团的员工(比如百度、博客园、金山、航天科学和技术公司,爱奇艺、Samsung科学和技术,民生银行、乐逗游戏等等),还有猎头偶……期待你的进入,让大家一齐从理想走向非凡……

style=”font-family: 华文陶文; font-size: x-large;”>财经 7

 请获取上面图片 并取名称为:nav.png

财经 8


相关文章

发表评论

电子邮件地址不会被公开。 必填项已用*标注

网站地图xml地图