OSDN Git Service

cflib は plugins プロジェクトから,Stigmata直下のプロジェクトに移行したため,このリポジトリからは削除した.
[stigmata/stigmata-plugins.git] / osb / src / main / java / jp / sourceforge / stigmata / birthmarks / osb / hungarian / HungarianMethod.java
1 package jp.sourceforge.stigmata.birthmarks.osb.hungarian;\r
2 \r
3 import java.util.ArrayList;\r
4 import java.util.Collections;\r
5 import java.util.Comparator;\r
6 import java.util.List;\r
7 \r
8 /**\r
9  * <p>\r
10  * ハンガリアン法により,最小和の組み合わせを選択する計算機.\r
11  * ハンガリアン法は以下の手順により行われる.\r
12  * </p>\r
13  * <ul>\r
14  *   <li>与えられた2次元配列の各列から,その列の最小値を引く.</li>\r
15  *   <li>与えられた2次元配列の各行から,その行の最小値を引く.</li>\r
16  *   <li>各行各列から,1つずつ0を選択できれば,その部分が最適な組み合わせであるため,そこで終了する.</li>\r
17  *   <li>そうでない場合は,0の生成作業へと移る\r
18  *    <ul>\r
19  *      <li>1度に多くの0が消えるよう線を入れる.</li>\r
20  *      <li>線で消されなかったセルの最小値<em>min</em>を求める.</li>\r
21  *      <li>線で消されなかった全てのセルから,求めた最小値<em>min</em>を減算する.</li>\r
22  *    </ul>\r
23  *   </li>\r
24  *   <li>最適な組み合わせを選択する.選択できれば終了.選択できなければ,もう一度0の生成作業を行う.</li>\r
25  * </ul>\r
26  */\r
27 public class HungarianMethod{\r
28     private CostMatrix matrix;\r
29     private List<Cell> solutions = new ArrayList<Cell>();\r
30 \r
31     public HungarianMethod(CostMatrix matrix){\r
32         this.matrix = matrix;\r
33     }\r
34 \r
35     public synchronized Cell[] getSolutions(){\r
36         Collections.sort(solutions, new Comparator<Cell>(){\r
37             @Override\r
38             public int compare(Cell arg0, Cell arg1){\r
39                 if(arg0.getX() < arg1.getX()){\r
40                     return -1;\r
41                 }\r
42                 else{\r
43                     return 1;\r
44                 }\r
45             }\r
46         });\r
47         return solutions.toArray(new Cell[solutions.size()]);\r
48     }\r
49 \r
50     public synchronized Line[] getLines(){\r
51         boolean[][] linedMatrix = new boolean[matrix.getSize()][matrix.getSize()];\r
52         List<Line> lines = getLines(matrix, linedMatrix);\r
53     \r
54         return lines.toArray(new Line[lines.size()]);\r
55     }\r
56 \r
57     /**\r
58      * ハンガリアン法を解く.\r
59      * @return 最大和もしくは最小和.\r
60      * @see CostMatrix#isMax\r
61      */\r
62     public double solve(){\r
63         // step.1  \r
64         matrix.minimize();\r
65 \r
66         boolean[][] linedMatrix = new boolean[matrix.getSize()][matrix.getSize()];\r
67         List<Line> lines = getLines(matrix, linedMatrix);\r
68         while(lines.size() < matrix.getSize()){\r
69             moreMinimize(matrix, lines, linedMatrix);\r
70             resetBooleanMatrix(linedMatrix);\r
71             lines = getLines(matrix, linedMatrix);\r
72         }\r
73         double solution = parseSolutions(matrix, lines);\r
74 \r
75         return solution;\r
76     }\r
77 \r
78     private void resetBooleanMatrix(boolean[][] matrix){\r
79         for(int i = 0; i < matrix.length; i++){\r
80             for(int j = 0; j < matrix[i].length; j++){\r
81                 matrix[i][j] = false;\r
82             }\r
83         }\r
84     }\r
85 \r
86     private double parseSolutions(CostMatrix matrix, List<Line> lines){\r
87         double solution = 0d;\r
88 \r
89         boolean[][] solutionMatrix = new boolean[matrix.getSize()][matrix.getSize()];\r
90         solutions.clear();\r
91         while(solutions.size() < matrix.getSize()){\r
92             Cell cell = getSolution(matrix, solutionMatrix);\r
93             for(int i = 0; i < matrix.getSize(); i++){\r
94                 solutionMatrix[cell.getX()][i] = true;\r
95                 solutionMatrix[i][cell.getY()] = true;\r
96             }\r
97             if(cell.isAvailable()){\r
98                 solution = solution + cell.getValue();\r
99             }\r
100             solutions.add(cell);\r
101         }\r
102         for(int i = solutions.size() - 1; i >= 0; i--){\r
103             if(!solutions.get(i).isAvailable()){\r
104                 solutions.remove(i);\r
105             }\r
106         }\r
107         return solution;\r
108     }\r
109 \r
110     private Cell getSolution(CostMatrix matrix, boolean[][] solutionMatrix){\r
111         for(int i = 0; i < matrix.getSize(); i++){\r
112             int count = 0;\r
113             int lastIndex = -1;\r
114             for(int j = 0; j < matrix.getSize(); j++){\r
115                 if(matrix.isZero(i, j) && !solutionMatrix[i][j]){\r
116                     count++;\r
117                     lastIndex = j;\r
118                 }\r
119             }\r
120             if(count == 1){\r
121                 Cell cell;\r
122                 if(matrix.isValidOriginal(i, lastIndex)){\r
123                     cell = new Cell(matrix.getOriginal(i, lastIndex), i, lastIndex);\r
124                 }\r
125                 else{\r
126                     cell = new Cell.EmptyCell(i, lastIndex);\r
127                 }\r
128                 return cell;\r
129             }\r
130         }\r
131         for(int j = 0; j < matrix.getSize(); j++){\r
132             int count = 0;\r
133             int lastIndex = -1;\r
134             for(int i = 0; i < matrix.getSize(); i++){\r
135                 if(matrix.isZero(i, j) && !solutionMatrix[i][j]){\r
136                     count++;\r
137                     lastIndex = i;\r
138                 }\r
139             }\r
140             if(count == 1){\r
141                 Cell cell;\r
142                 if(matrix.isValidOriginal(lastIndex, j)){\r
143                     cell = new Cell(matrix.getOriginal(lastIndex, j), lastIndex, j);\r
144                 }\r
145                 else{\r
146                     cell = new Cell.EmptyCell(lastIndex, j);\r
147                 }\r
148                 return cell;\r
149             }\r
150         }\r
151         for(int i = 0; i < matrix.getSize(); i++){\r
152             for(int j = 0; j < matrix.getSize(); j++){\r
153                 if(matrix.isZero(i, j) && !solutionMatrix[i][j]){\r
154                     Cell cell;\r
155                     if(matrix.isValidOriginal(i, j)){\r
156                         cell = new Cell(matrix.getOriginal(i, j), i, j);\r
157                     }\r
158                     else{\r
159                         cell = new Cell.EmptyCell(i, j);\r
160                     }\r
161                     return cell;\r
162                 }\r
163             }\r
164         }\r
165         return null;\r
166     }\r
167 \r
168     private List<Line> getLines(CostMatrix matrix, boolean[][] linedMatrix){\r
169         List<Line> lines = new ArrayList<Line>();\r
170         List<Line> candidate;\r
171 \r
172         while((candidate = getCandidateLines(matrix, linedMatrix)).size() > 0){\r
173             Line line = candidate.get(candidate.size() - 1);\r
174             lineOut(matrix, linedMatrix, line);\r
175             lines.add(line);\r
176         }\r
177         return lines;\r
178     }\r
179 \r
180     /**\r
181      * 対象の2次元配列から,全ての線を取り出す.\r
182      * ただし,線には必ず0を含み,その0は既に引かれた線で選択されていないものとする.\r
183      * また,選択した線は,線に含まれる0の数,交差する線の数によりソートされる.\r
184      */\r
185     private List<Line> getCandidateLines(CostMatrix matrix, boolean[][] linedMatrix){\r
186         List<Line> candidateLines = new ArrayList<Line>();\r
187         for(int i = 0; i < matrix.getSize(); i++){\r
188             int count = 0;\r
189             int crossCount = 0;\r
190             for(int j = 0; j < matrix.getSize(); j++){\r
191                 if(matrix.isZero(i, j) && !linedMatrix[i][j]){\r
192                     count++;\r
193                 }\r
194                 if(linedMatrix[i][j]){\r
195                     crossCount++;\r
196                 }\r
197             }\r
198             if(count > 0){\r
199                 candidateLines.add(new Line(i, count, crossCount, Line.Direction.ROW));\r
200             }\r
201         }\r
202         for(int j = 0; j < matrix.getSize(); j++){\r
203             int count = 0;\r
204             int crossCount = 0;\r
205             for(int i = 0; i < matrix.getSize(); i++){\r
206                 if(matrix.isZero(i, j) && !linedMatrix[i][j]){\r
207                     count++;\r
208                 }\r
209                 if(linedMatrix[i][j]){\r
210                     crossCount++;\r
211                 }\r
212             }\r
213             if(count > 0){\r
214                 candidateLines.add(new Line(j, count, crossCount, Line.Direction.COLUMN));\r
215             }\r
216         }\r
217         Collections.sort(candidateLines);\r
218 \r
219         return candidateLines;\r
220     }\r
221 \r
222     private void lineOut(CostMatrix matrix, boolean[][] linedMatrix, Line line){\r
223         if(line.getDirection() == Line.Direction.COLUMN){\r
224             for(int i = 0; i < linedMatrix.length; i++){\r
225                 linedMatrix[i][line.getIndex()] = true;\r
226             }\r
227         }\r
228         else{\r
229             for(int i = 0; i < linedMatrix[0].length; i++){\r
230                 linedMatrix[line.getIndex()][i] = true;\r
231             }\r
232         }\r
233     }\r
234 \r
235     private List<Cell> getCrossedLineCell(CostMatrix matrix, List<Line> lines){\r
236         List<Cell> cross = new ArrayList<Cell>();\r
237         for(int i = 0; i < lines.size() - 1; i++){\r
238             Line line1 = lines.get(i);\r
239             for(int j = 1; j < lines.size(); j++){\r
240                 Line line2 = lines.get(j);\r
241                 if(line1.getDirection() != line2.getDirection()){\r
242                     int row = line1.getIndex();\r
243                     int column = line2.getIndex();\r
244                     if(line1.getDirection() == Line.Direction.COLUMN){\r
245                         row = line2.getIndex();\r
246                         column = line1.getIndex();\r
247                     }\r
248                     cross.add(matrix.getCell(row, column));\r
249                 }\r
250             }\r
251         }\r
252         return cross;\r
253     }\r
254 \r
255     public synchronized void reduceMatrix(Line[] lineArray){\r
256         List<Line> lines = new ArrayList<Line>();\r
257         boolean[][] linedMatrix = new boolean[matrix.getSize()][matrix.getSize()];\r
258         for(Line line: lineArray){\r
259             lines.add(line);\r
260             for(int i = 0; i < linedMatrix.length; i++){\r
261                 if(line.getDirection() == Line.Direction.COLUMN){\r
262                     linedMatrix[i][line.getIndex()] = true;\r
263                 }\r
264                 else{\r
265                     linedMatrix[line.getIndex()][i] = true;\r
266                 }\r
267             }\r
268         }\r
269         moreMinimize(matrix, lines, linedMatrix);\r
270     }\r
271 \r
272     /**\r
273      * ハンガリアン法のステップ3, 4に相当する.\r
274      * 線の引かれていない箇所から,最小値を引く.\r
275      */\r
276     private void moreMinimize(CostMatrix matrix, List<Line> lines, boolean[][] linedMatrix){\r
277         List<Cell> cross = getCrossedLineCell(matrix, lines);\r
278 \r
279         // 線が引かれていない部分から最小値を選択する.\r
280         double min = 1;\r
281         for(int i = 0; i < matrix.getSize(); i++){\r
282             for(int j = 0; j < matrix.getSize(); j++){\r
283                 if(!linedMatrix[i][j] && min > matrix.getValue(i, j)){\r
284                     min = matrix.getValue(i, j);\r
285                 }\r
286             }\r
287         }\r
288 \r
289         // 線が引かれていない箇所から,求めた最小値を減算する.\r
290         for(int i = 0; i < matrix.getSize(); i++){\r
291             for(int j = 0; j < matrix.getSize(); j++){\r
292                 if(!linedMatrix[i][j]){\r
293                     matrix.setValue(matrix.getValue(i, j) - min, i, j);\r
294                 }\r
295             }\r
296         }\r
297         // 線が交わっている箇所は減算した値を足す.\r
298         for(Cell cell: cross){\r
299             matrix.setValue(\r
300                 matrix.getValue(cell.getX(), cell.getY()) + min,\r
301                 cell.getX(), cell.getY()\r
302             );\r
303         }\r
304     }\r
305 }