分派问题的回溯算法与实现.doc

期末考查设计科目： 算法设计与分析 设计名称： 分派问题的回溯算法与实现姓名： 学号： 序号： 班级： 分派问题的回溯算法与实现一、 期末考查题目 分派问题: 给n个人分派n件工作, 把工作j分派给第i个人的成本cost(i, j), 设计、编程、测试回溯算法, 在给每个人分派一件不同工作的情况下使得总成本最小。二、问题分析 回溯法原理分析 回溯法是一种选优搜索法，按选优条件向前搜索，以达到目标。但当探索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择，这种走不通就退回再的技术为回溯法。 可用回溯法求解的问题P，通常要能表达为：对于已知的由n元组（x1，x2，xn）组成的一个状态空间E=（x1，x2，xn）xiSi ，i=1，2，n，给定关于n元组中的一个分量的一个约束集D，要求E中满足D的全部约束条件的所有n元组。其中Si是分量xi的定义域，且 |Si| 有限，i=1，2，n。我们称E中满足D的全部约束条件的任一n元组为问题P的一个解。 分派问题原理 假设有n 个人的成本是w,工作效率p和完成工作的总成本M均为已知正数，这个问题要求选择出成本的一个子集,使得，且极小化，这n个x构成一个取0/1值的向量。 分派问题的表示方案 功能：用回溯法得可行解并选最优解。树中的节点：求解过程的一个状态树中的边：标示 xi 的一个可能的值解向量： 由根节点到任意叶节点的路径定义解空间：由根节点到所有叶节点的路径定义答案节点：求出最优解的状态回溯法求解的基本思想：基本任务： 1) 根据问题特点设计状态空间树 2) 逐个地生成问题状态 3) 确定问题状态是否是解状态 4) 确定解状态是否是答案状态 规范函数： int FIND(int k) int i; for(i=0; ik; i+) if(xi=xk) return 0; return 1; 搜索过程： 先深度搜索记录搜索的各节点的成本和s再与os比较如果s比os小，将s赋值给os,并将搜索到的节点赋给yi，当深度搜索结束，返回上一个节点继续搜索；如此循环，直到搜索搜索结束。Yi即为所求的答案节点。 1、主要数据类型与变量int sum; / 表示在分派任务过程中每成功分派一个累计成本；int xn; / 记录每成功分派任务给的人员；int yn; / 记录分派任务时任务分派所给的人员所得最小成本；int SACNF()；/ 输入人员和任务表int PRINTF();/输出人员和任务表 int FIND(int k) /规范函数，判断任务k是否可以分给xk号人员。 void TASK() /用回溯法得可行解并选最优解。 int ARRANGE();/输出查找后分配的对应表 2、源程序 #include #define N 5 int aNN; int xN,yN; int min=100; SCANF() int i,j; for(i=0;iN;i+) for(j=0;jN;j+) scanf(%d,&aij); PRINTF() int i,j; for(i=0;iN;i+) for(j=0;jN;j+) printf(%d ,aij); printf(n); FIND(k) int i; for(i=0; i=0) xk+; while(xkN) & (!FIND(k) xk+; if(xkN) if(kN-1) k=k+1; xk=-1; else sum=0; for(i=0;iN;i+) sum+=aixi; if(summin) min=sum; for(i=0;iN;i+) yi=xi; else k-; ARRANGE() int i; for(i=0;iN;i+) printf(序号为%d做任务%dn,i+1,yi+1);void main() int i,j; printf(输入人和任务对应表：%d行（人序号）%d列（任务）n,N,N); SCANF(); printf(%d行%d列对应表:n,N,N); PRINTF(); TASK(); ARRANGE(); printf(n); printf(最小成本:); printf(%dn,min); 二、测试运行1 编译在VC6.0中进行编译、运行以上程序，编译正确，运行正常。2 测试数据输入： 2 3 4 5 6 1 9 7 3 4 3 4 5 9 1 2 3 9 7 5 9 7 5 4 23 运行结果三、分析与总结 显然程序是对的，但仍然存在下面方面的原因：1、只能找出最优解，但不能找出符合全部最优解的对应