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

《分派问题的回溯算法与实现》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、期末考查设计科目：算法设计与分析设计名称：分派问题的回溯算法与实现姓名：学号：序号：班级：分派问题的回溯算法与实现一、期末考查题目分派问题:给n个人分派n件工作,把工作j分派给第i个人的成本cost(i,j),设计、编程、测试回溯算法,在给每个人分派一件不同工作的情况下使得总成本最小。二、问题分析回溯法原理分析回溯法是一种选优搜索法，按选优条件向前搜索，以达到目标。但当探索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择，这种走不通就退回再的技术为回溯法。可用回溯法求解的问题P，通常要能表达为：对于已知的由n元组（x1

2、，x2，…，xn）组成的一个状态空间E={（x1，x2，…，xn）∣xi∈Si，i=1，2，…，n}，给定关于n元组中的一个分量的一个约束集D，要求E中满足D的全部约束条件的所有n元组。其中Si是分量xi的定义域，且

3、Si

4、有限，i=1，2，…，n。我们称E中满足D的全部约束条件的任一n元组为问题P的一个解。分派问题原理假设有n个人的成本是w,工作效率p和完成工作的总成本M均为已知正数，这个问题要求选择出成本的一个子集,使得，且极小化，这n个x构成一个取0/1值的向量。分派问题的表示方案功能：用回溯法得可行解并选最优解。树中的节点：

5、求解过程的一个状态树中的边：标示xi的一个可能的值解向量：由根节点到任意叶节点的路径定义解空间：由根节点到所有叶节点的路径定义答案节点：求出最优解的状态回溯法求解的基本思想：基本任务：1)根据问题特点设计状态空间树2)逐个地生成问题状态3)确定问题状态是否是解状态4)确定解状态是否是答案状态规范函数：intFIND(intk){inti;for(i=0;i

6、点赋给y[i]，当深度搜索结束，返回上一个节点继续搜索；如此循环，直到搜索搜索结束。Y[i]即为所求的答案节点。1、主要数据类型与变量intsum;//表示在分派任务过程中每成功分派一个累计成本；intx[n];//记录每成功分派任务给的人员；inty[n];//记录分派任务时任务分派所给的人员所得最小成本；intSACNF()；//输入人员和任务表intPRINTF();//输出人员和任务表intFIND(intk)//规范函数，判断任务k是否可以分给x[k]号人员。voidTASK()//用回溯法得可行解并选最优解。intARR

7、ANGE();//输出查找后分配的对应表2、源程序#include#defineN5inta[N][N];intx[N],y[N];intmin=100;SCANF(){inti,j;for(i=0;i

8、k;i++)if(x[i]==x[k])return0;return1;}TASK(){intk=0,sum,i;x[k]=-1;while(k>=0){x[k]++;while((x[k]

9、nti;for(i=0;i

10、试数据输入：23456197343459123975975423．运行结果三、分析与总结显然程序是对的，但仍然存在下面方面的原因：1、只能找出最优解，但不能找出符合全部最优解的对应表2、当N变化时只能改变定义的N，不能进行选择N输出。