程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> 關於C語言 >> C#實現匈牙利算法(3)

C#實現匈牙利算法(3)

編輯:關於C語言

算法的實現代碼

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

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved