--- /dev/null
+package jp.sourceforge.stigmata.birthmarks.osb.hungarian;\r
+\r
+import java.util.ArrayList;\r
+import java.util.Collections;\r
+import java.util.Comparator;\r
+import java.util.List;\r
+\r
+/**\r
+ * <p>\r
+ * ハンガリアン法により，最小和の組み合わせを選択する計算機．\r
+ * ハンガリアン法は以下の手順により行われる．\r
+ * </p>\r
+ * <ul>\r
+ * <li>与えられた2次元配列の各列から，その列の最小値を引く．</li>\r
+ * <li>与えられた2次元配列の各行から，その行の最小値を引く．</li>\r
+ * <li>各行各列から，1つずつ0を選択できれば，その部分が最適な組み合わせであるため，そこで終了する．</li>\r
+ * <li>そうでない場合は，0の生成作業へと移る\r
+ * <ul>\r
+ * <li>1度に多くの0が消えるよう線を入れる．</li>\r
+ * <li>線で消されなかったセルの最小値<em>min</em>を求める．</li>\r
+ * <li>線で消されなかった全てのセルから，求めた最小値<em>min</em>を減算する．</li>\r
+ * </ul>\r
+ * </li>\r
+ * <li>最適な組み合わせを選択する．選択できれば終了．選択できなければ，もう一度0の生成作業を行う．</li>\r
+ * </ul>\r
+ */\r
+public class HungarianMethod{\r
+ private CostMatrix matrix;\r
+ private List<Cell> solutions = new ArrayList<Cell>();\r
+\r
+ public HungarianMethod(CostMatrix matrix){\r
+ this.matrix = matrix;\r
+ }\r
+\r
+ public synchronized Cell[] getSolutions(){\r
+ Collections.sort(solutions, new Comparator<Cell>(){\r
+ @Override\r
+ public int compare(Cell arg0, Cell arg1){\r
+ if(arg0.getX() < arg1.getX()){\r
+ return -1;\r
+ }\r
+ else{\r
+ return 1;\r
+ }\r
+ }\r
+ });\r
+ return solutions.toArray(new Cell[solutions.size()]);\r
+ }\r
+\r
+ public synchronized Line[] getLines(){\r
+ boolean[][] linedMatrix = new boolean[matrix.getSize()][matrix.getSize()];\r
+ List<Line> lines = getLines(matrix, linedMatrix);\r
+ \r
+ return lines.toArray(new Line[lines.size()]);\r
+ }\r
+\r
+ /**\r
+ * ハンガリアン法を解く．\r
+ * @return 最大和もしくは最小和．\r
+ * @see CostMatrix#isMax\r
+ */\r
+ public double solve(){\r
+ // step.1 \r
+ matrix.minimize();\r
+\r
+ boolean[][] linedMatrix = new boolean[matrix.getSize()][matrix.getSize()];\r
+ List<Line> lines = getLines(matrix, linedMatrix);\r
+ while(lines.size() < matrix.getSize()){\r
+ moreMinimize(matrix, lines, linedMatrix);\r
+ resetBooleanMatrix(linedMatrix);\r
+ lines = getLines(matrix, linedMatrix);\r
+ }\r
+ double solution = parseSolutions(matrix, lines);\r
+\r
+ return solution;\r
+ }\r
+\r
+ private void resetBooleanMatrix(boolean[][] matrix){\r
+ for(int i = 0; i < matrix.length; i++){\r
+ for(int j = 0; j < matrix[i].length; j++){\r
+ matrix[i][j] = false;\r
+ }\r
+ }\r
+ }\r
+\r
+ private double parseSolutions(CostMatrix matrix, List<Line> lines){\r
+ double solution = 0d;\r
+\r
+ boolean[][] solutionMatrix = new boolean[matrix.getSize()][matrix.getSize()];\r
+ solutions.clear();\r
+ while(solutions.size() < matrix.getSize()){\r
+ Cell cell = getSolution(matrix, solutionMatrix);\r
+ for(int i = 0; i < matrix.getSize(); i++){\r
+ solutionMatrix[cell.getX()][i] = true;\r
+ solutionMatrix[i][cell.getY()] = true;\r
+ }\r
+ if(cell.isAvailable()){\r
+ solution = solution + cell.getValue();\r
+ }\r
+ solutions.add(cell);\r
+ }\r
+ for(int i = solutions.size() - 1; i >= 0; i--){\r
+ if(!solutions.get(i).isAvailable()){\r
+ solutions.remove(i);\r
+ }\r
+ }\r
+ return solution;\r
+ }\r
+\r
+ private Cell getSolution(CostMatrix matrix, boolean[][] solutionMatrix){\r
+ for(int i = 0; i < matrix.getSize(); i++){\r
+ int count = 0;\r
+ int lastIndex = -1;\r
+ for(int j = 0; j < matrix.getSize(); j++){\r
+ if(matrix.isZero(i, j) && !solutionMatrix[i][j]){\r
+ count++;\r
+ lastIndex = j;\r
+ }\r
+ }\r
+ if(count == 1){\r
+ Cell cell;\r
+ if(matrix.isValidOriginal(i, lastIndex)){\r
+ cell = new Cell(matrix.getOriginal(i, lastIndex), i, lastIndex);\r
+ }\r
+ else{\r
+ cell = new Cell.EmptyCell(i, lastIndex);\r
+ }\r
+ return cell;\r
+ }\r
+ }\r
+ for(int j = 0; j < matrix.getSize(); j++){\r
+ int count = 0;\r
+ int lastIndex = -1;\r
+ for(int i = 0; i < matrix.getSize(); i++){\r
+ if(matrix.isZero(i, j) && !solutionMatrix[i][j]){\r
+ count++;\r
+ lastIndex = i;\r
+ }\r
+ }\r
+ if(count == 1){\r
+ Cell cell;\r
+ if(matrix.isValidOriginal(lastIndex, j)){\r
+ cell = new Cell(matrix.getOriginal(lastIndex, j), lastIndex, j);\r
+ }\r
+ else{\r
+ cell = new Cell.EmptyCell(lastIndex, j);\r
+ }\r
+ return cell;\r
+ }\r
+ }\r
+ for(int i = 0; i < matrix.getSize(); i++){\r
+ for(int j = 0; j < matrix.getSize(); j++){\r
+ if(matrix.isZero(i, j) && !solutionMatrix[i][j]){\r
+ Cell cell;\r
+ if(matrix.isValidOriginal(i, j)){\r
+ cell = new Cell(matrix.getOriginal(i, j), i, j);\r
+ }\r
+ else{\r
+ cell = new Cell.EmptyCell(i, j);\r
+ }\r
+ return cell;\r
+ }\r
+ }\r
+ }\r
+ return null;\r
+ }\r
+\r
+ private List<Line> getLines(CostMatrix matrix, boolean[][] linedMatrix){\r
+ List<Line> lines = new ArrayList<Line>();\r
+ List<Line> candidate;\r
+\r
+ while((candidate = getCandidateLines(matrix, linedMatrix)).size() > 0){\r
+ Line line = candidate.get(candidate.size() - 1);\r
+ lineOut(matrix, linedMatrix, line);\r
+ lines.add(line);\r
+ }\r
+ return lines;\r
+ }\r
+\r
+ /**\r
+ * 対象の２次元配列から，全ての線を取り出す．\r
+ * ただし，線には必ず0を含み，その0は既に引かれた線で選択されていないものとする．\r
+ * また，選択した線は，線に含まれる0の数，交差する線の数によりソートされる．\r
+ */\r
+ private List<Line> getCandidateLines(CostMatrix matrix, boolean[][] linedMatrix){\r
+ List<Line> candidateLines = new ArrayList<Line>();\r
+ for(int i = 0; i < matrix.getSize(); i++){\r
+ int count = 0;\r
+ int crossCount = 0;\r
+ for(int j = 0; j < matrix.getSize(); j++){\r
+ if(matrix.isZero(i, j) && !linedMatrix[i][j]){\r
+ count++;\r
+ }\r
+ if(linedMatrix[i][j]){\r
+ crossCount++;\r
+ }\r
+ }\r
+ if(count > 0){\r
+ candidateLines.add(new Line(i, count, crossCount, Line.Direction.ROW));\r
+ }\r
+ }\r
+ for(int j = 0; j < matrix.getSize(); j++){\r
+ int count = 0;\r
+ int crossCount = 0;\r
+ for(int i = 0; i < matrix.getSize(); i++){\r
+ if(matrix.isZero(i, j) && !linedMatrix[i][j]){\r
+ count++;\r
+ }\r
+ if(linedMatrix[i][j]){\r
+ crossCount++;\r
+ }\r
+ }\r
+ if(count > 0){\r
+ candidateLines.add(new Line(j, count, crossCount, Line.Direction.COLUMN));\r
+ }\r
+ }\r
+ Collections.sort(candidateLines);\r
+\r
+ return candidateLines;\r
+ }\r
+\r
+ private void lineOut(CostMatrix matrix, boolean[][] linedMatrix, Line line){\r
+ if(line.getDirection() == Line.Direction.COLUMN){\r
+ for(int i = 0; i < linedMatrix.length; i++){\r
+ linedMatrix[i][line.getIndex()] = true;\r
+ }\r
+ }\r
+ else{\r
+ for(int i = 0; i < linedMatrix[0].length; i++){\r
+ linedMatrix[line.getIndex()][i] = true;\r
+ }\r
+ }\r
+ }\r
+\r
+ private List<Cell> getCrossedLineCell(CostMatrix matrix, List<Line> lines){\r
+ List<Cell> cross = new ArrayList<Cell>();\r
+ for(int i = 0; i < lines.size() - 1; i++){\r
+ Line line1 = lines.get(i);\r
+ for(int j = 1; j < lines.size(); j++){\r
+ Line line2 = lines.get(j);\r
+ if(line1.getDirection() != line2.getDirection()){\r
+ int row = line1.getIndex();\r
+ int column = line2.getIndex();\r
+ if(line1.getDirection() == Line.Direction.COLUMN){\r
+ row = line2.getIndex();\r
+ column = line1.getIndex();\r
+ }\r
+ cross.add(matrix.getCell(row, column));\r
+ }\r
+ }\r
+ }\r
+ return cross;\r
+ }\r
+\r
+ public synchronized void reduceMatrix(Line[] lineArray){\r
+ List<Line> lines = new ArrayList<Line>();\r
+ boolean[][] linedMatrix = new boolean[matrix.getSize()][matrix.getSize()];\r
+ for(Line line: lineArray){\r
+ lines.add(line);\r
+ for(int i = 0; i < linedMatrix.length; i++){\r
+ if(line.getDirection() == Line.Direction.COLUMN){\r
+ linedMatrix[i][line.getIndex()] = true;\r
+ }\r
+ else{\r
+ linedMatrix[line.getIndex()][i] = true;\r
+ }\r
+ }\r
+ }\r
+ moreMinimize(matrix, lines, linedMatrix);\r
+ }\r
+\r
+ /**\r
+ * ハンガリアン法のステップ3, 4に相当する．\r
+ * 線の引かれていない箇所から，最小値を引く．\r
+ */\r
+ private void moreMinimize(CostMatrix matrix, List<Line> lines, boolean[][] linedMatrix){\r
+ List<Cell> cross = getCrossedLineCell(matrix, lines);\r
+\r
+ // 線が引かれていない部分から最小値を選択する．\r
+ double min = 1;\r
+ for(int i = 0; i < matrix.getSize(); i++){\r
+ for(int j = 0; j < matrix.getSize(); j++){\r
+ if(!linedMatrix[i][j] && min > matrix.getValue(i, j)){\r
+ min = matrix.getValue(i, j);\r
+ }\r
+ }\r
+ }\r
+\r
+ // 線が引かれていない箇所から，求めた最小値を減算する．\r
+ for(int i = 0; i < matrix.getSize(); i++){\r
+ for(int j = 0; j < matrix.getSize(); j++){\r
+ if(!linedMatrix[i][j]){\r
+ matrix.setValue(matrix.getValue(i, j) - min, i, j);\r
+ }\r
+ }\r
+ }\r
+ // 線が交わっている箇所は減算した値を足す．\r
+ for(Cell cell: cross){\r
+ matrix.setValue(\r
+ matrix.getValue(cell.getX(), cell.getY()) + min,\r
+ cell.getX(), cell.getY()\r
+ );\r
+ }\r
+ }\r
+}
\ No newline at end of file
OSDN Git Service
