分派问题的回溯解法

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

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

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

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

4、，返回上一个节点继续搜索；如此循环，直到搜索搜索结束。Y[i]即为所求的答案节点。1．主要数据类型与变量intos;//记录任务分派过程中当前最小成本；ints;//表示在分派任务过程中每成功分派一个累计成本；intx[n];//记录每成功分派任务给的人员；inty[n];//记录分派任务时任务分派所给的人员所得最小成本；intPlace(intk)//功能:规范函数，判断任务k是否可以分给x[k]号人员。voidwork()//功能：用回溯法得可行解并选最优解。2．算法或程序模块#include<

5、stdio.h>#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=0){x[k]=x[k]+1;while((x[k]

6、x[k]=x[k]+1;//求可行解if(x[k]

7、printf("%d",c[i][j]);printf("");}work();for(i=0;i

8、怎么都没得出正确解，所以我就想在得出可行解后再来判断可能就容易实现。于是我就定义了os这个变量，并定义y[n]数组来记录结果。结果成功得出结果。此程序有个不足之处就是当最优解有两个后两个以上，结果也只会有一个。因为只有一个数组y[n]记录最优解。