分派问题的回溯解法

《分派问题的回溯解法》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、设计五分派问题的回溯解法班级通信08-2BF学号14082300929姓名杨福成绩分一、设计目的1.掌握回溯法解题的基本思想；2.掌握回溯算法的设计方法；3.针对子集和数问题，熟练掌握回溯递归算法、迭代算法的设计与实现。二、设计内容a)任务描述1）分派问题简介假设有n个人的成本是w,工作效率p和完成工作的总成本M均为已知正数，这个问题要求选择出成本的一个子集,使得，且极小化，这n个x构成一个取0/1值的向量。2）设计任务简介分派问题:给n个人分派n件工作,把工作j分派给第i个人的成本为cost(i,j),设计、编程、测试回溯算法,在给每个人分派一件不同工作的情况下

2、使得总成本最小。1）阐述用回溯法求解的状态空间树结构：画出部分树，说明节点、边、到根节点的路径的意义，给出答案节点的定义。2）阐述用回溯法求解的基本思想：设计并说明规范函数，扼要阐述搜索过程。3）画出搜索过程的主要流程图。4）说明输入数据的表示方法、主要的数据变量、主要的函数功能。5）写出函数的为C语言代码分派问题的表示方案功能：用回溯法得可行解并选最优解。树中的节点：求解过程的一个状态树中的边：标示xi的一个可能的值解向量：由根节点到任意叶节点的路径定义解空间：由根节点到所有叶节点的路径定义答案节点：求出最优解的状态回溯法求解的基本思想：基本任务：1)根据问题特

3、点设计状态空间树2)逐个地生成问题状态3)确定问题状态是否是解状态4)确定解状态是否是答案状态规范函数：intPlace(intk){inti;for(i=0;i

4、个累计成本；intx[n];//记录每成功分派任务给的人员；inty[n];//记录分派任务时任务分派所给的人员所得最小成本；intPlace(intk)//功能:规范函数，判断任务k是否可以分给x[k]号人员。voidwork()//功能：用回溯法得可行解并选最优解。2．算法或程序模块#include#definen4intc[n][n]={4,1,2,1,2,3,1,3,4,2,1,5,4,2,1,2};intx[n],y[n];intos;intPlace(intk)//规范函数{inti;for(i=0;i

5、x[k])return0;return1;}voidwork()//求最优解函数{intk,s;os=1000;k=0;x[k]=-1;while(k>=0){x[k]=x[k]+1;while((x[k]

6、=s;}}}}elsek=k-1;//如果不是可行解就返回上一个节点}}voidmain(){inti,j;for(i=0;i

7、题一样设计一个上界函数来判断是否为最小成本，结果发现像那样在还没得出一个可行解就去查找最优解是个很麻烦的事，怎么都没得出正确解，所以我就想在得出可行解后再来判断可能就容易实现。于是我就定义了os这个变量，并定义y[n]数组来记录结果。结果成功得出结果。此程序有个不足之处就是当最优解有两个后两个以上，结果也只会有一个。因为只有一个数组y[n]记录最优解。