《分派问题的回溯算法》由会员分享，可在线阅读，更多相关《分派问题的回溯算法（5页珍藏版）》请在金锄头文库上搜索。
1、分派问题的回溯算法一. 设计目的1. 掌握回溯法解题的基本思想；2. 掌握回溯算法的设计方法；3. 针对分派问题，熟练掌握回溯递归算法、迭代算法的设计与实现。二. 设计内容1. 任务描述1.1.分派问题简介：给n个人分派n件工作，把工作j分派给第i个人的成本为cost(i, j),设计、编程、试回溯算法，在给每个人分派一件不同工作的情况下使得总成本最小。1. 2.阐述用回溯法求解的状态空间树结构：画出部分树，说明节点、边、到根节点的路径的意义，给出答案节点的定义。1. 3.阐述用回溯法求解的基本思想：设计并说明规范函数，扼要阐述搜索过程。1.4. 画出搜索过程的主要流程图。1.5. 说明输入数
2、据的表示方法、主要的数据变量、主要的函数功能。1.6. 写出各函数的伪C语言代码。2. 分派问題的表示方案设计的状态空间树：x2832V uvvV4434yzv爲 3 y-o x3x4454X图一图一是用静态树表示分派问题的状态空间树，图中xl, x2, x3,皿表示分派工作的 三个人，结点1到2,18,34,50分别表示xl分别选则工作1,2, 3, 4不同的状态，同样结点2到 3, & 13表示的是在xl选择问题1的情况下x2的三种不同选择。阐述用回溯法求解的基本思想：1)先设定一个最小成本min,然后深度优先搜索，当找到一组解并且他们的成本总和sum 小于min时，用sum覆盖min,在
3、搜索过程中，如果在某个结点出现sum人于min时，就没有必 要在搜索下去了。直接杀死该结点。2)规范函数int place(int k) 判断第k个人能否做工作Xkint i;for(i=0;ik;i+)辻(Xi=Xk)判断Xk在前面是否有人做return false;return true;3. 主要数据类型与变量int sum;/*成本总和*/int min/*最小的成本总和*/int k /*第k个人*/Xk/*d第k个人做第Xk个任务*/*表示i个人做第j号任务的成本*/4. 算法或程序模块int place (int k)功能：判断第k个人能否做第Xk号任务void back(int
4、 k, int sum)功能：遍历每种情况，比较每种情况下的的成本，得出最小成本summin 各函数的伪C语言代码： int place(int k)int i;for(i=0;i=0)Xk=Xk+l;while(XkN)&(Iplace(k)Xk二Xk+l;/找到可以解if (XkN)sum二sum+CkXk; if(kN-l)k卄;/移到下一个人 xk=-l;else /是一个完整的解时辻(summin) /判断此解是否最优 min二sum;for(i=0;i#define N 4static min=100;int XN,CN Nl;int QN;void Cost (int CN, i
5、nt n)int i, j;printf (”请输入成本：n);for(i=0;in;i+)for(j=0; jN;j+)scanf&Ci j);int place(int k)int i;for(i=0;i=0)Xk=Xk+l;while(XkN)&(!place(k)Xk=Xk+1;if (XkN)sum二sum+CkXk;if(kN-l)k+;xk=-l;elseif(summin) min=sum;for(i=0;iN;i+) Qi二 Xi;sum二sum-CkXk;elsek=k-l; sum=sum-CkXk;void mainOint sum;n=N;sum=0;Cost(C, n);back(sum);printfC分配方案：n);for(i=0;iN;i+)printfC $d 分配任务d ”, i+1, Qi+1);printf(n);printfC最小成本：)；printf (“dn, min);
