分支限界法,运动员最佳配对,实验总结

1 / 41 分支限界法 ,运动员最佳配对 ,实验总结 xxxxx实验报告 课程名称： _算法设计与分析 项目名称： _分支限界法实现_ 姓名： _xxxxx 专业： xxxxxxx 班级： _xxxxxxx_学号：_xxxxxxxxxxxxxxxxx_ 同组成员 _无 _ 一、课题名称 用分枝限界法求解单源最短路径问题 二、课题内容和 要求 设计要求：学习算法设计中分枝限界法的思想，设计算法解决数据结构中求解单源最短路径问题，编程实现： 2 / 41 给出指定源点的单源最短路径； 说明算法的时间复杂度。 三、需求分析 1.实现极小堆的创建，用来存储活结点表。 2.实现循环队列的创建、初始化、入队、出队等操作。 3.实现分支限界法来实现求解单元最短路径的算法。 4.实现最短路径的正确输出。 四、概要设计 建立工程 ,加入源文件，头文件 ,，和 中实现极小堆的创建，循环队列的创建、初始化、入队、出队等操作，中实现分支限界法来实现求解单元最短路径的算法。中实现最短路径的正确输出。如下图所示： 实验用例如下，通过邻接矩阵的方式写在中： 3 / 41 五、详细设计 main函数： #include #include #include #include #include void main() int k; int q; cout cink; coutq; while(k11) cout cink; 4 / 41 MinPath(k); output(k,q); const int size = 200; const int inf = 1000; /两点距离上界置为 1000 const int n = 12; /图顶点个数加 1 int prevn; /图的前驱顶点 int dist = 0,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf; /最短距离数组 int cnn = 0,0,0,0,0,0,0,0,0,0,0,0, 0,0,2,3,4,inf,inf,inf,inf,inf,inf,inf, 5 / 41 0,inf,0,3,inf,7,2,inf,inf,inf,inf,inf, 0,inf,inf,0,inf,inf,9,2,inf,inf,inf,inf, 0,inf,inf,inf,0,inf,inf,2,inf,inf,inf,inf, 0,inf,inf,inf,inf,0,inf,inf,3,3,inf,inf, 0,inf,inf,inf,inf,inf,0,1,inf,3,inf,inf, 0,inf,inf,inf,inf,inf,inf,0,inf,5,1,inf, 0,inf,inf,inf,inf,inf,inf,inf,0,inf,inf,3, 0,inf,inf,inf,inf,inf,inf,inf,inf,0,inf,2, 0,inf,inf,inf,inf,inf,inf,inf,inf,2,inf,2, 0,inf,inf,inf,inf,inf,inf,inf,inf,inf( 转载于 : 海 达 范 文网 :分支限界法 ,运动员最佳配对 ,实验总结 ),inf,0,; /矩阵 6 / 41 class MinHeapNode/创建极小堆用来存储活结点表 public : int i; /顶点编号 int length; /当前路长 ; class CirQueue/循环队列 private: 图的邻接 int front,rear;/头指针和尾指针 7 / 41 MinHeapNode datasize; public: CirQueue()/初始化建空队列 front = rear = 0; void queryIn(MinHeapNode e)/元素入队操作 if(rear +1)%size != front)/队列未满 rear = (rear+1)%size; /插入新的队尾元素 datarear = e; /在队尾插入元素 void queryOut()/元素出队操作 8 / 41 if(rear != front) front = (front+1)%size; /删除队头元素 MinHeapNode getQuery()/读取队头元素，但不出队 if(rear != front) return data(front+1)%size; return data1; 9 / 41 运动员最佳配对问题 (习题 5 14) 羽毛球队有男女运动员各 n人 .给定两个 nn 得矩阵 P和 Q. Pij是男运动员 i 和女运动员 j 配对组成混合双打的运动员竞赛优势 . Qij是女运动员 i 和男运动员 j 配合的女运动员竞赛优势 . 由于技术配合和心理状态等各种因素影响 ,Pij不一定等于 Qij. 男运动员 i女运动员 j配合组成混合双打的男女双方竞赛优势为 PijQji. 设计一个算法 ,计算男女运动员最佳配对法 ,使各组男女双方竞赛优势的总和达到最大 . 此题目的解空间显然是一棵排列树 ,可以套用搜索排列树的回溯法框架 : 10 / 41 void backtrack(int t) if(tn)compute(); else for(int j=i;j swap(r,t,j); backtrack(i+1); swap(r,t,j); void compute() 11 / 41 int temp=0; for(int i=1;i temp+=piri*qrii; if(tempbest) best=temp; for(int i=1;i bestri=ri; 无和集问题 (习题 5 16) 设 S是正整数集合。 S 是一个无和集当且仅当 x,y属于 S, 蕴含 x+y不属于 S 。 12 / 41 对于任意正整数 k ，如果可将 1,2. k 划分为 n 个无和子集 S1,S2.Sn，称正整 数 k 是 n 可分的。记 F(n) =max k | k 是 n 可分的 。 试设计一个算法，对任意给定的 n，计算 F(n) 的值。 该题是子集选取问题 ,解 空间显然是一棵子集树 ,同样可以套用搜索子集树的回溯法框架 . 但是由于搜索的空间很大 ,用搜索时间控制搜索深度 : Bool search(int dep) t1=clock(); elapsed+=(t1-t2)/()double)clock_per_sec); t0=t1; 13 / 41 If(elapsed)return false; If(depk)out();return true; for(int i=1;i If(sumidep=0) tdep=I;sidep=true; for(int j=1;j If(search(dep+1) return true; sidep=false;tdep=0; for(j=1;j Return false; 整数变换问题 (习题 5 18) 14 / 41 关于整数 i的变换 f 和 g。 f=3i,g=向下取整。 对于给定的两个整数 m， n.要求从 n 变换为 m。 如 15,4 4=ggfg(15) 首先分析 : 永远可以。 g 操作就是对一个数字的二进制表示向右移动一位。 就可以了。 为了找最短路径 ,用逐步加深的回溯法搜索 : 具体算法 : Void compute() K=1; 15 / 41 While(! Search(1,n) K+; If(kmaxdep)break; Init(); If(found)output(); Else cout Bool search(int dep, int n) if(depk) return false; For(int i=0;i Int n1=f(n,i);tdep=I; 16 / 41 If (n1=n)|search(dep+1,n1)found=true;out();return true; Return false; 无优先级运算 (习题 5 27) #include #include int n; /给定数字的个数 int a999;/给定的数字 int m;/利用给定的数字 运算求出的数字 m int num999; int oper999; 17 / 41 int flag999; int k; found() int x=num0; for(int i=0;i switch(operi) case 0: x+=numi+1;break; case 1: x-=numi+1;break; case 2: x*=numi+1;break; case 3: x/=numi+1;break; 18 / 41 return(x=m); search(int dep) if(depk) if(found() return true; else return false; 19 / 41 for(int i=0;i if(flagi=0) numdep=ai; flagi=1; for(int j=0;j operdep=j; if(search(dep+1) return true; flagi=0; 20 / 41 return false; main() coutn; for (int p=0;p coutap; flagp=0; cout cinm; for(k=0;k if(search(0) 21 / 41 cout /out(); return; cout 运行 : 算法设计与分析实验报告 实验报告细表 1 实验题目 算法设计思想 圆排列问题的解空间是一棵排列树。按照回溯法搜索排列树22 / 41 的算法框架，设开始时 a=r1， r2， ， rn是所给的 N个圆的半径，则相应的排列树由 a=1： n的所有排列构成。 解圆的排列 问题的回溯算法中 circlePerm 返回找到的最小圆排列长度。初始时，数组 a的输入 N 个圆的半径，计算结束后返回相应于最优解的圆排列。 Center用于计算当前所选择的圆在当前排列中圆心的横坐标。 compute 用于计算当前圆排列的长度。变量 min用于记录当前最小圆排列的长度；数组 r 表示当前圆排列；数组 x 则记录当前圆排列中各圆的圆心横坐标。算法中约定在当前圆排列中排在第一个的圆的横坐标为 0。 在递归算法中 bracktrack 中，当 i n 时，算法搜索至叶结点，得到新的圆方案。此时算法调用 compute 计算当 前圆排列的长度，适时更新当前最优值。 当 i 程序源码 package h06; public class Circles public int n;/待排 列圆的个数 public float min;/当前最优值 23 / 41 public float x;/当前圆排列圆心横坐标 public float r;/当前圆排列 public float circlePerm(int nn,float rr) n=nn; r=rr; min=1000000; x=new floatn+1; backtrack(1); return min; public void backtrack(int t) 24 / 41 if(tn) compute(); else for(int j=t;j swap(r,t,j); float centerx=center(t); if(centerx+rt+r1 xt=centerx; backtrack(t+1); swap(r,t,j); 25 / 41 public void swap(float r,int i,int j) float temp=ri; ri=rj; rj=temp; public float center(int t)/计算当前所选择圆的圆心横坐标 float temp=0; for(int j=1;j float valuex=(float) (xj+*(rt*rj); if(valuextemp) temp=valuex; 26 / 41 return temp; public void compute()/计算当前圆排列的长度 float low=0; float high=0; for(int i=1;i if(xi-ri if(xi+rihigh) high=xi+ri; if(high-low min=high-low; public static void main(String args) 27 / 41 (实验六 分支界限法 ); (题目：圆排列问题 ); (姓名：胡文峰 学号：1207122113); int n=3; float r=0,1,1,2;/r 下标从 1 开始， 0无用，只是凑数 Circles c=new Circles(); float min=(n, r); (最小圆排列长度为 +min); 实验结论 28 / 41 心得体会 最后一份实验了！说说做这些报告的感受吧！ 1、 百度搜索代码和设计思想 Ctrl+C。 2、 打开工具。 3、 Ctrl+V。 4、 贴上上份报告的。 (实验六 分支界限法 ); (题目：圆排列问题 ); (姓名：胡文峰 学号： 1207122113); 5、 结束 总而言之，并没有加强多少对该算法的了解 。希望老师可以29 / 41 看看有没有更好的方式去做实验。 运动员最佳配对问题 1) 回溯法求解问题的一般思路，回溯法求解本问题的思路及其 C/C+程序实现及效率分析。 回溯法求解本问题的思路： 假设男运动员已经按照 1 到 n排好序不动，用一个数组 w 存放配对的女运动员的编号，即第 i 号男运动员配第 wi号女运动员，初始时设 wi=i,然后不断的重新排列 w 数组，每得到一次排列，就要计算在此排列下的配对总和，若发现比之前的总和大，则更新最优解。套用排列树框架，做好初始化后开始回溯，关键在于到达叶子节点时，需要计算 sum += piwi * qwii，若发现 sum比之前的最优值大，则更新最优值和配对顺序，回溯完成后则可得到最大总和及其相应的运动员配对方法 。 1) 分支限界法求解问题的一般思路，分支限界法求解本问题的思路及其 C/C+程序实现及 效率分析。 30 / 41 代码： #include #include /文件输入输出流 #include /I/O 流控制头文件 #include /vector 是一个能够存放任意类型的动态数组， /能够增加和压缩数据 using namespace std; vector Re; /全局变量 ,Re 用来记录配对情况 vector P; vector Q; 31 / 41 class PairUp friend int nPairUp(int); private: bool Place(int k); void Backtrack(int k); int n; /运动员个数 int bestsum; vector x; /当前解 public: PairUp(int m,int c,int b) (m+1); (m+1); 32 / 41 n = c; bestsum = b; PairUp() ; bool PairUp:Place(int k) for(int j=1;j if(xj=xk) /同一个男运动员和不同一个女运动员配对 return false; return true; void PairUp:Backtrack(int t) if(tn) int currentsum=0; /第次还原为进行下次的累加 for(int i=1;i currentsum += (Pixi) * (Qxii); /累加，计算当前配对总和 if(bestsum bestsum=currentsum; copy(),(),(); 33 / 41 else for(int i=t;i swap(xt,xi); if(Place(t) Backtrack(t+1); swap(xt,xi); int nPairUp(int n) PairUp X(n,n,0); /初始化 X vector p; for(int i=0;i _back(i); /当前的 P 数组尾部插入 i的值 34 / 41 copy(),(),(); (1); return ; int main() ifstream fin(); ofstream fout(); int n,i,j,currentsum; vector r; vector t; finn; _back(0); _back(r); _back(0); _back(t); 35 / 41 cout cout for(i=1;i for(j=1;j fincurrentsum; _back(currentsum); _back(r); for(vector:iterator vr = ()+1;vr != ();) vr = (vr); for(i=1;i for(j=1;j fincurrentsum; _back(currentsum); _back(t); for(vector:iterator vt = ()+1;vt != ();) vt = (vt); 36 / 41 cout for(i=1;i cout fout return 0 ; 效率分析： 回溯法用到的是递归的进行深度优先搜索整个排列树，算法中没有剪枝函数和限界函数，算法的时间复杂度为 O(n!),复杂度很高 2）分支限界法求解本问题 思路： 算法开始时创建一个最大堆，用于表示活结点优先队列堆中每个节点的 val值是优先队列的优先级。接着算法计算出图中每个顶点的最大 val如果搜索到所搜索的排队树的叶子节点，算法即告结束。 代码： #include 37 / 41 #include #include #include #include using namespace std; int n; int *P; /女运动员和男运动员配对的竞赛优势 int *Q; /男运动员和女运动员配对的竞赛优势 int best; /最优解 int *w;/当前男运动员排列 class ArgNo