单源最短路径1 分支限界.docVIP

? 一、实验名称：单源最短路径问题? 时间：X年X月X日，星期3，第三、四节? 地点：0#601? 二、实验目的及要求? 1、掌握分支限界法解题步骤：? 1在问题的边带权的解空间树中进行广度优先有哪些信誉好的足球投注网站??2找一个叶结点使其对应路径的权最小(最大)? 3当有哪些信誉好的足球投注网站到达一个扩展结点时,一次性扩展它的所有儿子? 4将满足约束条件且最小耗费函数?目标函数限界的儿子,插入活结点???表中? 5从活结点表中取下一结点同样扩展直到找到所需的解或活动结点表? ??为空为止? 三、实验环境? Window下的vs2010? 四、实验内容? 单源最短路径问题? 以一个例子来说明单源最短路径问题：在下图所给的有向图G中，每一边都有一个非负边权。? 求图G的从源顶点s到目标顶点t之间的最短路径? 五、算法描述及实验步骤? ?算法思想： 解单源最短路径问题的优先队列式分支限界法用一极小堆来存储活结点表。其优先级是结点所对应的当前路长。? ? 算法从图G的源顶点s和空优先队列开始。结点s被扩展后，它的儿子结点被依次插入堆中。? 算法每次从堆中取出具有最小当前路长的结点作为当前扩展结点，并依次检查与当前扩展结点相邻的所有顶点。? 如果从当前扩展结点i到j有边可达，且从源出发，途经i再到j的所相应路径长度，小于当前最优路径长度，则将该顶点作为活结点插入到活结点优先队列中。? 结点扩展过程一直继续到活结点优先队列为空时为止 二．单源最短路径问题? 1.问题描述? 下面以一个例子来说明单源最短路径问题：在下图所给的有向图G中，每一边都有一个非负边权。要求图G的从源顶点s到目标顶点t之间的最短路径。 下图是用优先队列式分支限界法解有向图G的单源最短路径问题产生的解空间树。其中，每一个结点旁边的数字表示该结点所对应的当前路长。 2.?算法思想? 解单源最短路径问题的优先队列式分支限界法用一极小堆来存储活结点表。其优先级是结点所对应的当前路长。 算法从图G的源顶点s和空优先队列开始。结点s被扩展后，它的儿子结点被依次插入堆中。此后，算法从堆中取出具有最小当前路长的结点作为当前扩展结点，并依次检查与当前扩展结点相邻的所有顶点。如果从当前扩展结点i到顶点j有边可达，且从源出发，途经顶点i再到顶点j的所相应的路径的长度小于当前最优路径长度，则将该顶点作为活结点插入到活结点优先队列中。? 这个结点的扩展过程一直继续到活结点优先队列为空时为止。 3.?剪枝策略? ? ?在算法扩展结点的过程中，一旦发现一个结点的下界不小于当前 找到的最短路长，则算法剪去以该结点为根的子树。?? ????在算法中，利用结点间的控制关系进行剪枝。从源顶点s出发，2条不同路径到达图G的同一顶点。由于两条路径的路长不同，因此可以将路长长的路径所对应的树中的结点为根的子树剪去。?? ? 下图是用优先队列式分支限界法解有向图G的单源最短路径问题产生的解空间树的剪枝情况。 三．程序设计： #includeiostream using namespace std; const int size = 100; const int inf = 5000; //两点距离上界 //第一组测试参数 const int n = 6; //图顶点个数加1 int prev[n]; //图的前驱顶点 int dist[] = {0,0,5000,5000,5000,5000}; //最短距离数组 int c[n][n] = {{0,0,0,0,0,0},{0,0,2,3,5000,5000}, //图的邻接矩阵 {0,5000,0,1,2,5000},{0,5000,5000,0,9,2}, {0,5000,5000,5000,0,2},{0,5000,5000,5000,5000,0}}; /*第二组测试参数 const int n = 5; //图顶点个数加1 int prev[n]; //图的前驱顶点 int dist[] = {0,0,5000,5000,5000}; int c[][n]={{0,0,0,0,0},{0,0,2,3,5000},{0,5000,0,1,2},{0,5000,5000,0,9},{0,5000,5000,5000,0} }; */ class MinHeapNode { public : int i; //顶点编号 int length; //当前路长 }; //循环队列 class CirQueue { private: int front,rear; MinHeapNode data[size]; public: CirQueue() { front = rear = 0; } //元素