贪心算法和分支限界法解决单源最短路径.doc

《贪心算法和分支限界法解决单源最短路径.doc》由会员分享，可在线阅读，更多相关《贪心算法和分支限界法解决单源最短路径.doc（39页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、Four short words sum up what has lifted most successful individuals above the crowd: a little bit more.-author-date贪心算法和分支限界法解决单源最短路径贪心算法和分支限界法解决单源最短路径单源最短路径计科1班 朱润华 2012040732方法1：贪心算法一、 贪心算法解决单源最短路径问题描述：单源最短路径描述：给定带权有向图G=(V,E),其中每条边的权是非负实数。另外，还给定V中的一个顶点，称之为源(origin)。现在要计算从源到其他各顶点的最短路径的长度。这里的路径长度指的是

2、到达路径各边权值之和。Dijkstra算法是解决单源最短路径问题的贪心算法。Dijkstra算法的基本思想是：设置顶点集合S并不断地做贪心选择来扩充集合。一个顶点属于集合S当且仅当从源点到该顶点的最短路径长度已知。贪心扩充就是不断在集合S中添加新的元素（顶点）。初始时，集合S中仅含有源(origin)一个元素。设curr是G的某个顶点，把从源到curr且中间只经过集合S中顶点的路称之为从源到顶点curr的特殊路径，并且使用数组distance记录当前每个顶点所对应的最短路径的长度。Dijkstra算法每次从图G中的(V-S)的集合中选取具有最短路径的顶点curr，并将curr加入到集合S中，同

3、时对数组distance进行必要的修改。一旦S包含了所有的V中元素，distance数组就记录了从源(origin)到其他顶点的最短路径长度。二、 贪心算法思想步骤：Dijkstra算法可描述如下，其中输入带权有向图是G=(V,E)，V=1,2,，n，顶点v是源。c是一个二维数组，cij表示边(i,j)的权。当(i,j)不属于E时，cij是一个大数。disti表示当前从源到顶点i的最短特殊路径长度。在Dijkstra算法中做贪心选择时，实际上是考虑当S添加u之后，可能出现一条到顶点的新的特殊路，如果这条新特殊路是先经过老的S到达顶点u,然后从u经过一条边直接到达顶点i，则这种路的最短长度是di

4、stu+cui。如果distu+cuidisti，则需要更新disti的值。步骤如下： 1、用带权的邻接矩阵c来表示带权有向图, cij表示弧上的权值。设S为已知最短路径的终点的集合,它的初始状态为空集。从源点v经过S到图上其余各点vi的当前最短路径长度的初值为：disti=cvi, vi属于V； 2、选择vu, 使得distu=Mindisti | vi属于V-S,vj就是长度最短的最短路径的终点。令S=S U u；3、修改从v到集合V-S上任一顶点vi的当前最短路径长度:如果 distu+cuj distj 则修改 distj= distu+cuj； 4、重复操作(2),(3)共n-1次。

5、三、 算法实现代码：#include #include #include #include using namespace std; const int N = 5;const int M = 1000;ifstream fin(4d5.txt); templatevoid Dijkstra(int n,int v,Type dist,int prev,Type cN+1); void Traceback(int v,int i,int prev);/输出最短路径 v源点，i终点 int main() int v = 1;/源点为1 int distN+1,prevN+1,cN+1N+1; c

6、out有向图权的矩阵为：endl; for(int i=1; i=N; i+) for(int j=1; jcij; coutcij ; coutendl; Dijkstra(N,v,dist,prev,c); for(int i=2; i=N; i+) cout源点1到点i的最短路径长度为:disti，其路径为; Traceback(1,i,prev); coutendl; return 0; template void Dijkstra(int n,int v,Type dist,int prev,Type cN+1) bool sN+1; for(int i=1; i=n; i+) di

7、sti = cvi;/disti表示当前从源到顶点i的最短特殊路径长度 si = false; if(disti = M) previ = 0;/记录从源到顶点i的最短路径i的前一个顶点 else previ = v; distv = 0; sv = true; for(int i=1; in; i+) int temp = M; int u = v;/上一顶点 /取出V-S中具有最短特殊路径长度的顶点u for(int j=1; j=n; j+) if(!sj) & (distjtemp) u = j temp = distj; su = true; /根据作出的贪心选择更新Dist值 fo

8、r(int j=1; j=n; j+) if(!sj) & (cujM) Type newdist = distu + cuj; if(newdist distj) distj = newdist; prevj = u; /输出最短路径 v源点，i终点void Traceback(int v,int i,int prev) if(v = i) couti; return; Traceback(v,previ,prev); coutI; 四、计算复杂性 对于一个具有n个顶点和e条边的带权有向图，如果用带权邻接矩阵表示这个图，那么Dijkstra算法的主循环体需要O(n)时间。这个循环需要执行n-

9、1次，所以完成循环需要O(n2)时间。算法的其余部分所需要的时间不超过O(n2)。五、 运行结果：方法2：分支限界法一、 分支限界法解决单源最短路径问题描述：采用广度优先产生状态空间树的结点，并使用剪枝函数的方法称为分枝限界法。所谓“分支”是采用广度优先的策略，依次生成扩展结点的所有分支（即：儿子结点）。所谓“限界”是在结点扩展过程中，计算结点的上界（或下界），边搜索边减掉搜索树的某些分支，从而提高搜索效率按照广度优先的原则，一个活结点一旦成为扩展结点（E-结点）R后，算法将依次生成它的全部孩子结点，将那些导致不可行解或导致非最优解的儿子舍弃，其余儿子加入活结点表中。然后，从活结点表中取出一个

10、结点作为当前扩展结点。重复上述结点扩展过程，直至找到问题的解或判定无解为止。二、 分支限界法算法思想描述：算法从图G的源顶点s和空优先队列开始。结点s被扩展后，它的儿子结点被依次插入堆中。此后，算法从堆中取出具有最小当前路长的结点作为当前扩展结点，并依次检查与当前扩展结点相邻的所有顶点。如果从当前扩展结点i到顶点j有边可达，且从源出发，途经顶点i再到顶点j的所相应的路径的长度小于当前最优路径长度，则将该顶点作为活结点插入到活结点优先队列中。这个结点的扩展过程一直继续到活结点优先队列为空时为止。 在算法扩展结点的过程中，一旦发现一个结点的下界不小于当前找到的最短路长，则算法剪去以该结点为根的子树

11、。在算法中，利用结点间的控制关系进行剪枝。从源顶点s出发，2条不同路径到达图G的同一顶点。由于两条路径的路长不同，因此可以将路长长的路径所对应的树中的结点为根的子树剪去。三、 算法实现代码：#include stdafx.h #include MinHeap2.h #include #include using namespace std; ifstream fin(6d2.txt); template class Graph friend int main(); public: void ShortesPaths(int); private: int n, /图G的顶点数 *prev; /前

12、驱顶点数组 Type *c, /图G的领接矩阵 *dist; /最短距离数组 ; template class MinHeapNode friend Graph; public: operator int ()constreturn length; private: int i; /顶点编号 Type length; /当前路长 ; template void Graph:ShortesPaths(int v)/单源最短路径问题的优先队列式分支限界法 MinHeapMinHeapNode H(1000); MinHeapNode E; /定义源为初始扩展节点 E.i=v; E.length=0

13、; distv=0; while (true)/搜索问题的解空间 for (int j = 1; j = n; j+) if (cE.ij!=0)&(E.length+cE.ijdistj) / 顶点i到顶点j可达，且满足控制约束 distj=E.length+cE.ij; prevj=E.i; / 加入活结点优先队列 MinHeapNode N; N.i=j; N.length=distj; H.Insert(N); try H.DeleteMin(E); / 取下一扩展结点 catch (int) break; if (H.currentsize=0)/ 优先队列空 break; int

14、main() int n=11; int prev12 = 0,0,0,0,0,0,0,0,0,0,0,0; int dist12=1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000; cout单源图的邻接矩阵如下：endl; int *c = new int*n+1; for(int i=1;i=n;i+) ci=new intn+1; for(int j=1; jcij; coutcij ; coutendl; int v=1; Graph G; G.n=n; G.c=c; G.dist=dist; G.prev=prev

15、; G.ShortesPaths(v); cout从S到T的最短路长是：dist11endl; for (int i = 2; i = n; i+) coutprev(i)=previ endl; for (int i = 2; i = n; i+) cout从1到i的最短路长是：distiendl; for(int i=1;i=n;i+) delete ci; delete c; c=0; return 0; 四、 算法复杂度分析：时间复杂度：O(n!);空间复杂度：O(n*n);五、 运行结果：六、贪心算法与分支限界法比较分析：以分支限界法实现的单源最短路径复杂度比贪心算法高。成 绩 单评语成绩-