匈牙利算法的Java版本

java

最近一直在做蚁群,都是因为不经意,真是一个不经意。

我在去年的时候得一老师的推荐,跟随我们分院的副院长做项目,而她是我们毕业设计的导师之一。自然而然,

我的毕设跟她这个老师做了。到毕设出题的时候,她让我出一个题目,让别人来做,她出我的题,我就出了。然

后呢,她说,你就做这个题吧,这个题呢,就是之前我贴出来的那个题目~~

之后,老师让我写一篇关于人力资源的文章。我就憋呀憋,终于想起我们运筹学曾经学过的指派问题,着手编

了。递归,让我头痛的递归,放弃。某一天在论文海洋中遨游的时候发现,蚁群算法,不错不错,我喜欢。

最终确定写这个作为人力资源论文。写呀写,越写越深,编呀编,越编越多,体系变庞大了。老师说,既然误打

误撞,就把这个做为毕设吧,于是,我现在的毕设就是蚁群了~~~

蚁群编出来了,老师说,从网上找匈牙利的源程序,验证一下我们的算法执行结果。结果呢,网上匈牙利算法

程序过来过去就C++那么一个,而且要命的是,这个程序在执行规模为5的问题的时候没有错误,在执行22规模

的时候,执行了3天都出不来个结果,让我对匈牙利算法的实用性产生了极大的怀疑;还找了一个VB做的,我想

不明白,既然贴出这个程序了,怎么就不说明一下,excel文件的格式都不说,唉,极度崩溃了。

这样呢,老师就让我硬着头皮编一个Java版本的,于是我就编了,结果和C++那个效果非常类似,5的成功执行

,22的循环到现在还没出来结果,是昨天下午4点开始执行的。

废了这么多话,该到正题了,贴出我的程序,希望有心人热心指导,本人不胜感激,呵呵

需要注意的是:

系数矩阵文件的格式为下面这样,第一行是问题的规模,运行的时候注意文件的路径,其它的以空格隔开:

1
2
3
4
5
6

5

4 8 7 15 12

7 9 17 14 10

6 9 12 8 7

6 7 14 6 10

6 9 12 10 6



代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351

import java.io.BufferedReader;

import java.io.File;

import java.io.FileReader;

import java.util.*;

 

public class HungarianAlgorithm {

static int[][] cost_init;

static int[][] cost_temp;

static int[] selected;

int minRow=-1;

StringBuffer notRows=new StringBuffer("");

int min=9999;

static Vector<String> paths=new Vector<String>();

int numberOfZro=0;//保存独立零元素的个数

public void readData(String filepath) //从文本文件中读取代价矩阵

{

BufferedReader bufread;

String read;

int row=0;

try

{ //得到文本文件的路径

File file=new File(filepath);

FileReader fileread=new FileReader(file);

bufread=new BufferedReader(fileread);

while((read=bufread.readLine())!=null)

{

String[] c=read.toString().substring(1).split(" ");

if(row==0){

int a=Integer.parseInt(c[0]);

cost_init=new int[a][a];

cost_temp=new int[a][a];

selected=new int[a];

}

else{

for(int i=0;i<c.length;i++)

{

cost_init[row-1][i]=Integer.parseInt(c[i]);

cost_temp[row-1][i]=Integer.parseInt(c[i]);

selected[row-1]=-1;

}

}

row++;

}//end while

}catch(Exception d){System.out.println("文件读入出错"+d.getMessage());}

// System.out.println("经过方法readData之后的矩阵为:");

// for(int i=0;i<cost_init.length;i++){

// for(int j=0;j<cost_init.length;j++){

// System.out.print(cost_init[i][j]+" ");

// }

// System.out.println();

// }

}//end readData

public void processFirst(){//每行每列各剪掉本行本列的最小值,得到的新的矩阵保存在cost_temp中

int min=0;

for(int i=0;i<cost_temp.length;i++){//开始对行的计算

min=cost_temp[i][0];

for(int j=0;j<cost_temp.length;j++){

if(cost_temp[i][j]><min) min=cost_temp[i][j];

}//找到本行的最小值

if(min!=0){

for(int j=0;j<cost_temp.length;j++){

cost_temp[i][j]=cost_temp[i][j]-min;

}//找到本行的最小值

}//每个元素减去本行的最小值

}//-----------------------行计算结束

min=0;

for(int j=0;j<cost_temp.length;j++){//开始对行的计算

min=cost_temp[0][j];

for(int i=0;i<cost_temp.length;i++){

if(cost_temp[i][j]><min) min=cost_temp[i][j];

}//找到本列的最小值

if(min!=0){

for(int i=0;i<cost_temp.length;i++){

cost_temp[i][j]=cost_temp[i][j]-min;

}//找到本列的最小值

}//每个元素减去本列的最小值

}//-----------------------行计算结束

// System.out.println("经过方法processFirst处理之后的矩阵为:");

// for(int i=0;i<cost_temp.length;i++){

// for(int j=0;j<cost_temp.length;j++){

// System.out.print(cost_temp[i][j]+" ");

// }

// System.out.println();

// }

}//end precessFirst

public void processSecond(int row){//找到一条独立零元素路径

///-------------------------------------------------无迭代

// for(int i=0;i<cost_temp.length;i++){

// for(int j=0;j<cost_temp.length;j++){

// if(cost_temp[i][j]==0 && judge(j)){

// selected[i]=j;

// break;

// }

// }

// }

// ----------------------------------------------有迭代

for(int j=0;j<cost_temp.length;j++){

selected[row]=-1;

if(cost_temp[row][j]==0 && judge(j)){

selected[row]=j;

if(row!=(cost_temp.length-1)){

processSecond(row+1);

}

}

if(row!=(cost_temp.length-1) && j==(cost_temp.length-1)){

processSecond(row+1);

}

 

if(row==(cost_temp.length-1) && j==(cost_temp.length-1)){

String path=new String();

for(int i=0;i<selected.length;i++){

// System.out.print(selected[i]+" ");

path=path+String.valueOf(selected[i])+",";

}//for

// System.out.println();

// System.out.println("一次迭代结束,得到的路径条数为:"+paths.size());

//-------在插入之前判断selected中非-1的值的个数,如果大于等于当前值就压入,否则不压入

int localNumberOfZro=0;

for(int i=0;i<selected.length;i++){

if(selected[i]!=-1)localNumberOfZro++;

}

if(localNumberOfZro>this.numberOfZro){

System.out.println("清空前,独立零元素的个数为:"+this.numberOfZro+",已存的记录条数为:"+paths.size());

paths=new Vector<String>();//清空Vector,将这个大的值压入

this.numberOfZro=localNumberOfZro;

paths.add(path);

System.out.println("清空后,独立零元素的个数为:"+this.numberOfZro);

}

if(localNumberOfZro==this.numberOfZro){

//判断是否已经有这个元素了,如果有,不加入,没有,则加入

if(ifNotHave(path)){

System.out.println("加入一条记录,现在的总记录数为:"+paths.size()+"独立零元素的个数为:"+this.numberOfZro);

paths.add(path);//不清空Vector,将这个大的值压入

}

}

}// ifif(row==(cost_temp.length-1) && j==(cost_temp.length-1))

}

}//end processSecond

public boolean ifNotHave(String path){//返回值为真,表示没有包含此条记录

boolean r=true;

for(int i=0;i<paths.size();i++){

if(paths.elementAt(i).equals(path)){

r=false;

break;

}

}

return r;

}

public boolean judge(int colomn){

boolean r=false;

for(int i=0;i<selected.length;i++){

if(selected[i]==colomn){

r=false;

break;

}//if

else if(i==(selected.length-1)){

r=true;

break;

}//else

}//for

return r;

}

public void processT(){//得到未被直线覆盖的元素的最小值

for(int i=0;i<cost_temp.length;i++){

int selectCo=selected[i];

if(selectCo==-1){

notRows.append(i+",");

for(int j=0;j<cost_temp.length;j++){

// System.out.println(cost_temp[i][j]);

if(cost_temp[i][j]><min && judge(j)) {

this.min=cost_temp[i][j];

minRow=i;

}//if

}//for

}// end if(selectCo==-1){

}// for

//---找到未被直线覆盖的最小值

// System.out.println("最小值是"+min+",所在行是:"+minRow+"未被直线覆盖的行是"+notRows);

// System.out.println("没减之前的矩阵为:");

// for(int i=0;i<cost_temp.length;i++){

// for(int j=0;j<cost_temp.length;j++){

// System.out.print(cost_temp[i][j]+" ");

// }

// System.out.println();

// }

}

public void sRow(){//未被直线覆盖的行减去最小值

String[] rows=notRows.toString().split(",");

for(int i=0;i<rows.length;i++){

int row=Integer.parseInt(rows[i]);

for(int j=0;j<cost_temp.length;j++){

cost_temp[row][j]=cost_temp[row][j]-this.min;

}

}

// System.out.println("经过方法sRow之后的矩阵为:");

// for(int i=0;i<cost_temp.length;i++){

// for(int j=0;j<cost_temp.length;j++){

// System.out.print(cost_temp[i][j]+" ");

// }

// System.out.println();

// }

}

public void sCol(){//出现负数的列加为0

//找出每列的最小值,如果小于0,给这列加上这个最小值的相反数

for(int j=0;j<cost_temp.length;j++){

int cloMin=999;

for(int i=0;i<cost_temp.length;i++){

if(cost_temp[i][j]><cloMin) cloMin=cost_temp[i][j];

}//找到本列的最小值

if(cloMin><0){

for(int i=0;i<cost_temp.length;i++){

cost_temp[i][j]=cost_temp[i][j]-cloMin;

}//减去本列的最小值

}//if

}//end j

// System.out.println("经过方法sCol之后的矩阵为:");

// for(int i=0;i<cost_temp.length;i++){

// for(int j=0;j<cost_temp.length;j++){

// System.out.print(cost_temp[i][j]+" ");

// }

// System.out.println();

// }

}

public static void main(String[] args) {

HungarianAlgorithm ha=new HungarianAlgorithm();

String filename="C:\\Data\\22C.txt";

ha.readData(filename);

int iteraiton=1;

ha.processFirst();

while(true){

System.out.println("---------------循环次数为-----------------"+iteraiton);

iteraiton++;

ha.numberOfZro=0;

paths=new Vector><String>();

selected=new int[cost_temp.length];

for(int i=0;i<selected.length;i++){

selected[i]=-1;

}

ha.min=9999;

ha.minRow=-1;

ha.notRows=new StringBuffer("");

ha.processSecond(0);

//得到很多条路径,找出-1最少的这一条付给独立矩阵

ha.selectPath();

// System.out.println("独立矩阵");

// for(int i=0;i<selected.length;i++){

// System.out.print(selected[i]+" ");

// }//for

// System.out.println();

System.out.println("独立零元素的个数为"+ha.numberOfZro);

if(ha.numberOfZro><selected.length){

ha.processT();

ha.sRow();

ha.sCol();

}

else{

System.out.println("最终花费代价为:"+ha.getCost(selected)+",分配矩阵为:");

// System.out.println("xuzelu______________");

// for(int i=0;i<selected.length;i++){

// System.out.print(selected[i]+" ");

// }//for

// System.out.println();

for(int i=0;i<cost_temp.length;i++){

for(int j=0;j<cost_temp.length;j++){

System.out.print(cost_temp[i][j]+" ");

}//for

System.out.println();

}//for

break;

}//else

}

}

public void selectPath(){

System.out.println("初步选择的路径的条数:"+paths.size());

//shuchupaths

for(int i=0;i<paths.size();i++){

System.out.println(paths.elementAt(i));

}

int maxBiao=0;//保存对应的路径的在Vector中的标号返回独立零元素的个数

// 将独立零元素最大的路径付给selectedPath

if(paths.size()!=1){//如果Vector的大小超过1,从中找出对应的代价最大的路径

int cost=0;

for(int i=0;i<paths.size();i++){

String pa=paths.elementAt(i);

int costR=getCost(pa);

if(costR>cost){

maxBiao=i;

}

}// for

}//if

String bestPath=paths.elementAt(maxBiao);

String[] a=bestPath.split(",");

for(int i=0;i<cost_temp.length;i++){

selected[i]=Integer.parseInt(a[i]);

}

}//fangfa

public int getCost(String path){//根据路径,得到这条路径的代价之和

int cost=0;

String[] sel=path.split(",");

for(int i=0;i<cost_init.length;i++){

if(!sel[i].equals("-1")){

cost=cost+cost_init[i][Integer.parseInt(sel[i])];

}

}//for i

return cost;

}

public int getCost(int path[]){//根据路径,得到这条路径的代价之和

int cost=0;

for(int i=0;i<cost_init.length;i++){

if(path[i]!=-1){

cost=cost+cost_init[i][path[i]];

}

}//for i

return cost;

}

 

}

 



有问题之处,还请有兴趣的人指点迷津,呵呵,先谢谢了>

以上是 匈牙利算法的Java版本 的全部内容, 来源链接: utcz.com/z/390889.html

回到顶部