分支限界法分配任务

分支限界法分配任务（1）

来点技术的。

算法课结束了，不能交手写版作业，电子版的把我写死了，怎么也得贴出来一下。

题目：

用分支定界法求解下面问题。需给出搜索树及其中各节点上的部分解和界。

将5个任务分配各5个人，1个任务1个人，表中单元格中的数值代表把某项任务分配各某个人员的成本，请找出总成本最小的分配方案。

	任务1	任务2	任务3	任务4	任务5
人员1	7	2	5	3	8
人员2	6	4	3	7	7
人员3	5	8	1	9	8
人员4	6	7	2	5	4
人员5	7	6	9	3	6

解：

本题用极小堆存储活节点表的方法，每次从堆中选取成本最小的活节点成为扩展节点。

说明：

l 表格中一行代表一个节点；

l 红色标记的行为扩展节点；

l 黄色标记的行为死节点；

l 绿色标记的为最优解

一、分配任务1：

任务1	成本
人员1	7
人员2	6
人员3	5
人员4	6
人员5	7

1月10日 17:47| 添加评论| 阅读评论 (1)| 固定链接| 写入日志| 算法

分支限界法分配任务（2）

一、分配任务2：

任务1分配给人员3成为扩展节点：

任务1	任务2	成本
人员3（5）	人员1	7
	人员2	9
	人员4	12
	人员5	11

（表2）

将表1中的黄色行标记为死节点。

任务1分配给人员2成为扩展节点：

任务1	任务2	成本
人员2（6）	人员1	8
	人员3	14
	人员4	13
	人员5	12

（表3）

任务1分配给人员4成为扩展节点：

任务1	任务2	成本
人员4（6）	人员1	8
	人员2	10
	人员3	14
	人员5	12

（表4）

1月10日 17:45| 添加评论| 固定链接| 写入日志| 算法

分支限界法分配任务（3）

一、分配任务3：

表2中的第一行成为扩展节点：

任务1	任务2	任务3	成本
人员3（5）	人员1（7）	人员2	10
		人员4	9
		人员5	16

（表5）

因为 表中第二行 成本为9，所以标注表2、3、4中死节点为黄色。

任务1	任务2	任务3	成本
人员2（6）	人员1（8）	人员3	9
		人员4	10
		人员5	17

（表6）

任务1	任务2	任务3	成本
人员4（6）	人员1（8）	人员2	11
		人员3	9
		人员5	17

（表格7）

1月10日 17:44| 添加评论| 固定链接| 写入日志| 算法

分支限界法分配任务（4）

四、分配任务4：

任务1	任务2	任务3	任务4	成本
人员3（5）	人员1（7）	人员4（9）	人员2	16
			人员5	12

（表8）

任务1	任务2	任务3	任务4	成本
人员2（6）	人员1（8）	人员3（9）	人员4	14
			人员5	12

（表9）

任务1	任务2	任务3	任务4	成本
人员4（6）	人员1（8）	人员3（9）	人员2	16
			人员5	12

（表10）

分配任务3后，成本为10、11的节点也成为死节点，因为任务4最低成本为3，扩展成本为10、11的节点加上任务4的成本后，必然大于12。

标记表5、6、7中的死节点为黄色。

1月10日 17:40| 添加评论| 固定链接| 写入日志| 算法

分支限界法分配任务（5）

五、分配任务5：

任务1	任务2	任务3	任务4	任务5	成本
人员3（5）	人员1（7）	人员4（9）	人员5（12）	人员2	19

(表11)

任务1	任务2	任务3	任务4	任务5	成本
人员2（6）	人员1（8）	人员3（9）	人员5（12）	人员4	16

（表12）

任务1	任务2	任务3	任务4	任务5	成本
人员4（6）	人员1（8）	人员3（9）	人员5（12）	人员2	19

（表13）

得出最优解16，

任务分配如下：

任务1	任务2	任务3	任务4	任务5
人员2（6）	人员1（8）	人员3（9）	人员5（12）	人员4（16）

（表14）