指派问题的回溯算法
提问于2008-04-24 10:08:05 解决时间:2008-05-01 08:31:35
利用回溯方法设计指派问题的算法，掌握回溯法的基本思想和算法设计的基本步骤。
要求：设计指派问题的回溯算法，注意回溯算法解决此问题要找出问题所有的可行解，然后一次比较保留问题的最优解(即最少耗费的解)，并输出结果。利用c语言（c++语言）实现算法，给出程序的正确运行结果。
指派问题描述：
n个雇员被指派做n件工作，使得指派第i个人做第i件工作的耗费为ci,j,找出一种指派使得总耗费最少。
(1)空间搜索( 可能是你说的回溯吧)
因为"有n份作业分配给n个人去完成，每人完成一份作业"
所以 实际上工作完成序列(以工作序号为索引)就是 这i个人的全排列
例如 n=3时 有排列
1 2 3 (表示 1号人完成1号作业,2号人完成2号作业,3号人完成3号作业)
1 3 2 (表示 1号人完成1号作业,3号人完成2号作业,2号人完成3号作业)
.....
3 2 1
遍历排列空间并计算 每种排列的总花费, 取最小
求排列的用回溯法,这个不用说了把;
(2)动态规划
设函数 cost(i,V)表示 前i个人做 V作业集合中的作业的最小总开销
因此 由最优原理 得
cost(i,v)=min{ cost(i+1,V-j)+Cij }
(j属于V)
最后 令V为n个作业集合
计算 cost(n,V) 即可
不知上述是否符合你的要求
|
