资源预览内容
第1页 / 共7页
第2页 / 共7页
第3页 / 共7页
第4页 / 共7页
第5页 / 共7页
第6页 / 共7页
第7页 / 共7页
亲,该文档总共7页全部预览完了,如果喜欢就下载吧!
资源描述
贪心算法和分支限界法解决单源最短路径单源最短路径计科 1 班 朱润华 *-*32方法 1:贪心算法一、贪心算法解决单源最短路径问题描述:单源最短路径描述:给定带权有向图G=(V,E),其中每条边的权是 非负实数。另外,还给定V中的一个顶点,称之为源(origin)。现在要 计算从源到其他各顶点的最短路径的长度。这里的路径长度指的是到 达路径各边权值之和。Dijkstra算法是解决单源最短路径问题的贪心算法。Dijkstra算法 的基本思想是:设置顶点集合 S 并不断地做贪心选择来扩充集合。一 个顶点属于集合S当且仅当从源点到该顶点的最短路径长度已知。贪 心扩充就是不断在集合S中添加新的元素(顶点)。初始时,集合S中仅含有源(origin)个元素。设curr是G的某 个顶点,把从源到 curr 且中间只经过集合 S 中顶点的路称之为从源 到顶点curr的特殊路径,并且使用数组distance记录当前每个顶点 所对应的最短路径的长度。Dijkstra算法每次从图G中的(V-S)的集合 中选取具有最短路径的顶点curr,并将curr加入到集合S中,同时对 数组 distance 进行必要的修改。一旦 S 包含了所有的 V 中元素, distance数组就记录了从源(origin)到其他顶点的最短路径长度。二、贪心算法思想步骤:Dijkstra 算法可描述如下,其中输入带权有向图是 G=(V,E), V二12?,n,顶点v是源。c是一个二维数组,cij表示边(i,j)的权。 当(i,j)不属于E时,cij是一个大数。disti表示当前从源到顶点i的 最短特殊路径长度。在 Dijkstra 算法中做贪心选择时,实际上是考虑 当 S 添加 u 之后,可能出现一条到顶点的新的特殊路,如果这条新特 殊路是先经过老的S到达顶点u,然后从u经过一条边直接到达顶点i, 则这种路的最短长度是 distu+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次。三、算法实现代码:#include #include #include #include using namespace std; const int N = 5; const int M = 1000;ifstream fin(template void Dijkstra(int n,int v,Type dist,int prev,Type cN+1); voidTraceback(int v,int i,int prev);输出最短路径 v 源点,i 终点int main() int v = 1;/源点为 1int distN+1,prevN+1,cN+1N+1;cout有向图权的矩阵为: for(int i=1; i i+) for(int j=1; j j+) fincij; cout coutendl; Dijkstra(N,v,dist,prev,c);for(int i=2; i i+) cout 源 点 1 到 点 的最短路径长度为 :,其路径为 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 i+) disti = 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 j +) if(!sj) (distjtemp) u = jtemp = distj; su = true;根据作出的贪心选择更新Dist值for(int j = 1; j 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) cout return; Traceback(v,previ,prev); cout四、计算复杂性对于一个具有n个顶点和e条边的带权有向图,如果用带权邻接 矩阵表示这个图,那么Dijkstra算法的主循环体需要O(n)时间。这个 循环需要执行n-1次,所以完成循环需要O(nA2)时间。算法的其余 部分所需要的时间不超过O(n2)o五、运行结果:方法 2:分支限界法一、分支限界法解决单源最短路径问题描述: 采用广度优先产生状态空间树的结点,并使用剪枝函数的方法称为分枝限界法。所谓“分支”是采用广度优先的策略,依次生成扩展结 点的所有分支(即:儿子结点)。所谓“限界是在结点扩展过程中,计 算结点的上界(或下界),边搜索边减掉搜索树的某些分支,从而提 高搜索效率按照广度优先的原则,一个活结点一旦成为扩展结点(E-结点) R 后,算法将依次生成它的全部孩子结点,将那些导致不可行解或导 致非最优解的儿子舍弃,其余儿子加入活结点表中。然后,从活结点 表中取出一个结点作为当前扩展结点。重复上述结点扩展过程,直至 找到问题的解或判定无解为止。二、分支限界法算法思想描述:算法从图G的源顶点s和空优先队列开始。结点s被扩展后,它 的儿子结点被依次插入堆中。此后,算法从堆中取出具有最小当前路 长的结点作为当前扩展结点,并依次检查与当前扩展结点相邻的所有 顶点。如果从当前扩展结点 i 到顶点 j 有边可达,且从源出发,途经 顶点 i 再到顶点 j 的所相应的路径的长度小于当前最优路径长度,则 将该顶点作为活结点插入到活结点优先队列中。这个结点的扩展过程 一直继续到活结点优先队列为空时为止。在算法扩展结点的过程中, 一旦发现一个结点的下界不小于当前找到的最短路长,则算法剪去以 该结点为根的子树。在算法中,利用结点间的控制关系进行剪枝。从源顶点 s 出发, 2 条不同路径到达图 G 的同一顶点。由于两条路径的路长不同,因此 可以将路长长的路径所对应的树中的结点为根的子树剪去。三、算法实现代码: #include #include #include #include using namespace std; ifstream fin(template class Graph friend int main();public:void ShortesPaths(int);private:int n, /图 G 的顶点数 *prev; /前驱顶点数组 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) 单源最短路径问题的优先队列式分支限界法 MinHeapH(1000);MinHeapNodeE; /定义源为初始扩展节点 E.i=v;E.length=0; distv=0;while (true)/搜索问题的解空间for (int j = 1; j 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.I ength二distj; H.lnsert(N); try H.DeleteMin(E); / 取下一扩展结点 catch (int) break;if (H.currentsize=0)/ 优先队列空 break; int main()int n=11;int prev = 0,0,0,0,0,0,0,0,0,0,0,0;intdist=1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,100 0;cout单源图的邻接矩阵如下: int *c = new int*n + 1;for(int i=1;ii+) ci=new intn+1; for(int j=1; j j+) fincij; cout /cij
网站客服QQ:2055934822
金锄头文库版权所有
经营许可证:蜀ICP备13022795号 | 川公网安备 51140202000112号