首页 / 软件开发 / C# / C#实现匈牙利算法

C#实现匈牙利算法2011-03-25墙头草算法的原理:

范例:

有四位教授被分派开设四门课程,如何指派使所需的总准备时间为最小.已知个人对各 课程之准备时间如下表所示:

课程1

课程2

课程3

课程4

教授A	2	10	9	7
教授B	15	4	14	8
教授C	13	14	16	11
教授D	4	15	13	9

解法:

Step 1. 在各列中找最小值,将该列中各元素检去此值,对各行重复一次.

08 7 5 本列各减2

11 0 10 4 本列各减4

2

3

5

0

本列各减11

0

11

9

5

本列各减4

0	8	2	5
11	0	5	4
2	3	0	0
0	11	4	5

本栏各减0

本栏各减0

本栏各减5

本栏各减0

Step 2. 检验各列,对碰上之第一个零,做记号,同列或同栏的其他零则画X （由零较少 的列先做,可不依顺序）

0	8	2	5
11	0	5	4
2	3	0	0
0	11	4	5