算法的原理:
范例:
有四位教授被分派開設四門課程,如何指派使所需的總准備時間為最小.已知個人對各 課程之准備時間如下表所示:
課程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
Step 3. 檢驗可否完成僅含零的完全指派,若不能,則畫出最少數目的垂直與水平的刪 除線來包含所有的零至少一次.
[tr=red][tr=red] 0
0 8 2 5 11 0 5 4 2 3 0 0 0 11 4 5Step 4. 找出未被畫線的元素中之最小值 K,將含有此些未被畫線的元素的各列所有 元素減去K (Step 4.1),若造成負值,則將該欄加上K (Step 4.2).形成新矩陣後回到Step 2.
Step 4.1
[tr=red][tr=red] -2
-2 6 0 3 11 0 5 4 2 3 0 0 -2 9 2 3Step 4.2
0 6 0 3 13 0 5 4 4 3 0 0 0 9 2 3形成新矩陣 Step 2.
0 6 0 3 13 0 5 4 4 3 0 0 0 9 2 3由上表知,指派順序為 (2,2), (4,1), (1,3), (3,4),可得到完全指派.
課程1 課程2 課程3 課程4
教授A 9 教授B 4 教授C 11 教授D 4總准備時間為 9+4+11+4 = 28 為最佳解.
算法的實現代碼
1using System.Collections.Generic;
2using System.Drawing;
3
4namespace ConsoleApplication1
5{
6 class Program
7 {
8 static void Main(string[] args)
9 {
10 ZMatrix m = new ZMatrix(4, 4);
11
12 m.Calculation();
13
14
15 int debug = 0;
16 }
17 }
18
19 class ZMatrix
20 {
21 private int[,] _data;
22 private List<Point> _result = new List<Point>();
23 private int _x;
24 private int _y;
25
26 public ZMatrix(int botNum, int PointNum)
27 {
28 _x = botNum;
29 _y = PointNum;
30 _data = new int[botNum, PointNum];
31
32 _data[0, 0] = 9;
33 _data[0, 1] = 4;
34 _data[0, 2] = 6;
35 _data[0, 3] = 8;
36
37 _data[1, 0] = 8;
38 _data[1, 1] = 5;
39 _data[1, 2] = 9;
40 _data[1, 3] = 10;
41
42 _data[2, 0] = 9;
43 _data[2, 1] = 7;
44 _data[2, 2] = 3;
45 _data[2, 3] = 5;
46
47 _data[3, 0] = 4;
48 _data[3, 1] = 8;
49 _data[3, 2] = 6;
50 _data[3, 3] = 9;
51 }
52
53 public void Calculation()
54 {
55 step1();
56 while (!step2())
57 {
58 step3();
59 }
60 }
61
62 /**////<summary>
63 /// 畫出最少數目的垂直與水平的刪除線來包含所有的零至少一次.
64 ///</summary>
65 private void step3()
66 {
67 bool[,] isDelete = new bool[_x, _y];
68 for (int x = 0; x < _x; x++)
69 {
70 for (int y = 0; y < _y; y++)
71 {
72 if (_data[x, y] == 0 && !isDelete[x, y])
73 {
74 int xc = 0;
75 int yc = 0;
76
77 //lie
78 for (int nx = 0; nx < _x; nx++)
79 {
80 if (nx != x && _data[nx, y] == 0)
81 {
82 xc++;
83 }
84 }
85
86 //hang
87 for (int ny = 0; ny < _y; ny++)
88 {
89 if (ny != y && _data[x, ny] == 0)
90 {
91 yc++;
92 }
93 }
94
95 if (xc > yc)
96 {
97 for (int xx = 0; xx < _x; xx++)
98 {
99 isDelete[xx, y] = true;
100 }
101 }
102 else
103 {
104 for (int yy = 0; yy < _y; yy++)
105 {
106 isDelete[x, yy] = true;
107 }
108 }
109 }
110 }
111 }
112
113 //找出未被畫線的元素中之最小值 K
114 int k = 99999;
115 for (int x = 0; x < _x; x++)
116 {
117 for (int y = 0; y < _y; y++)
118 {
119 if (!isDelete[x, y])
120 {
121 if (_data[x, y] < k)
122 {
123 k = _data[x, y];
124 }
125 }
126 }
127 }
128
129 //將含有此些未被畫線的元素的各列所有元素減去K
130 for (int x = 0; x < _x; x++)
131 {
132 for (int y = 0; y < _y; y++)
133 {
134 if (!isDelete[x, y])
135 {
136 for (int y1 = 0; y1 < _y; y1++)
137 {
138 _data[x, y1] -= k;
139 }
140 break;
141 }
142 }
143 }
144
145 //若造成負值,則將該欄加上K (Step 4.2).形成新矩陣後回到Step2
146 for (int x = 0; x < _x; x++)
147 {
148 for (int y = 0; y < _y; y++)
149 {
150 if (_data[x, y] < 0)
151 {
152 for (int x1 = 0; x1 < _x; x1++)
153 {
154 _data[x1, y] += k;
155 }
156 break;
157 }
158 }
159 }
160 }
161
162 /**////<summary>
163 /// 檢驗各列,對碰上之第一個零,做記號,同列或同欄的其他零則畫X (由零 較少的列先做,可不依順序)
164 ///
165 /// 檢驗可否完成僅含零的完全指派,若不能,則false
166 ///</summary>
167 private bool step2()
168 {
169 _result.Clear();
170 bool[,] isDelete = new bool[_x, _y];
171
172 //零的數量由少到多
173 List<ZZeroNode> zeroNodes = new List<ZZeroNode> ();
174 for (int x = 0; x < _x; x++)
175 {
176 int zeroNum = 0;
177 for (int y = 0; y < _y; y++)
178 {
179 if (_data[x, y] == 0)
180 {
181 zeroNum++;
182 }
183 }
184 if (zeroNum > 0)
185 {
186 zeroNodes.Add(new ZZeroNode(x, zeroNum));
187 }
188 }
189 zeroNodes.Sort(ZZeroNode.Cmp);
190
191 //從零較少的行開始
192 while (zeroNodes.Count > 0)
193 {
194 ZZeroNode node = zeroNodes[0];
195
196 if (node.ZeroNum <= 0)
197 {
198 zeroNodes.RemoveAt(0);
199 }
200 else
201 {
202 for (int y = 0; y < _y; y++)
203 {
204 if (_data[node.X, y] == 0 && !isDelete [node.X, y])
205 {
206 _result.Add(new Point(node.X, y));
207 zeroNodes.RemoveAt(0);
208
209 //刪除與該零在同一列的其他零
210 for (int xxx = 0; xxx < _x; xxx++)
211 {
212 if (_data[xxx, y] == 0)
213 {
214 isDelete[xxx, y] = true;
215 for (int i = 0; i < zeroNodes.Count; i++)
216 {
217 if (zeroNodes.X == xxx)
218 {
219 zeroNodes.ZeroNum--;
220 }
221 }
222 }
223 }
224 break;
225 }
226 }
227 }
228 zeroNodes.Sort(ZZeroNode.Cmp);
229 }
230
231 return _result.Count == _x;
232 }
233
234 /**////<summary>
235 /// 在各列中找最小值,將該列中各元素檢去此值,對各行重復一次.
236 ///</summary>
237 private void step1()
238 {
239 //列
240 for (int x = 0; x < _x; x++)
241 {
242 int minY = 99999;
243 //找到每列最小的值
244 for (int y = 0; y < _y; y++)
245 {
246 if (_data[x, y] < minY)
247 {
248 minY = _data[x, y];
249 }
250 }
251 //讓該列減去最小的值
252 for (int y = 0; y < _y; y++)
253 {
254 _data[x, y] -= minY;
255 }
256 }
257 //行
258 for (int y = 0; y < _y; y++)
259 {
260 int minX = 99999;
261 //找到每列最小的值
262 for (int x = 0; x < _x; x++)
263 {
264 if (_data[x, y] < minX)
265 {
266 minX = _data[x, y];
267 }
268 }
269 //讓該列減去最小的值
270 for (int x = 0; x < _x; x++)
271 {
272 _data[x, y] -= minX;
273 }
274 }
275 }
276 }
277
278 class ZZeroNode
279 {
280 public int X;
281 public int ZeroNum;
282
283 public ZZeroNode(int x, int zeroNum)
284 {
285 X = x;
286 ZeroNum = zeroNum;
287 }
288
289 public static int Cmp(ZZeroNode a, ZZeroNode b)
290 {
291 return a.ZeroNum.CompareTo(b.ZeroNum);
292 }
293 }
294}
295
