В проблема назначения заключается в назначении задач работникам, где каждая пара (работник, задача) имеет стоимость. В Венгерский алгоритм строит оптимальное решение этой проблемы. Он имеет два варианта, в зависимости от представления отношений затрат: один с двудольными графами и один с матрицами затрат. Я реализовал последнюю форму, как описано здесь потому что у меня возникли проблемы с преобразованием примера шага 3 из Википедии в алгоритм. Цель состоит в том, чтобы создать библиотеку, которую я мог бы использовать в другом проекте, в котором я намерен назначить наставников для студентов, исходя из их вероятности поладить.
Короче говоря, алгоритм изменяет матрицу затрат, чтобы появились нули, и выбирает некоторые из них для построения оптимального решения. Он использует два типа меток: звездочки (для нулей, принадлежащих к возможному решению) и простые числа (для нулей, которые могут заменить нули, отмеченные звездочкой в решении). Он перемещается между 6 шагами:
- Матрица предварительно обрабатывается (проверки достоверности, необязательное вращение, чтобы иметь как минимум столько же столбцов, чем строк, вычитание минимального значения каждой строки из всех значений одной и той же строки, а затем то же самое для столбцов)
- Жадно подготовьте вариант решения, поставив нули в звезду
- Проверьте, завершено ли возможное решение; если да, верните его; иначе переходите к следующему шагу
- Попытайтесь найти ноль, который мог бы заменить помеченный звездочкой в возможном решении; если он найден, переходите к следующему шагу; в противном случае перейдите к шагу 6
- Следуйте чередующемуся пути нулей со штрихом и звездочкой, чтобы изменить решение-кандидат, и вернитесь к шагу 3.
- Измените некоторые значения в матрице, чтобы появилось больше нулей, и вернитесь к шагу 4.
Например, возьмем следующую матрицу затрат.
0 | 1 | 2 | 3 | |
---|---|---|---|---|
0 | 1 | 2 | 25 | 13 |
1 | 5 | 7 | 25 | 15 |
2 | 10 | 13 | 16 | 13 |
3 | 17 | 21 год | 11 | 18 |
4 | 15 | 15 | 15 | 14 |
Алгоритм должен вывести следующее решение с общей стоимостью 2 + 5 + 13 + 11 = 31 (и последней строке не назначена никакая задача, потому что рабочий слишком дорог).
0 | 1 | 2 | 3 | |
---|---|---|---|---|
0 | Икс | |||
1 | Икс | |||
2 | Икс | |||
3 | Икс | |||
4 |
Мой код на Java 11 работает, как задумано, на нескольких ручных примерах и стандартных крайних случаях (нулевой ввод, неквадратная матрица стоимости, матрица наихудшего случая для этого алгоритма). Если вы обнаружите какое-либо дело, с которым плохо разбираются, я был бы рад узнать, но это не моя главная проблема.
Я использовал junit5 для написания модульных тестов, и мне кажется, что написанная мною структура тестирования может быть излишне сложной. Я хотел получить отдельный результат теста для каждого запуска метода тестирования на каждом из его входных данных, и несколько методов тестирования будут иметь один и тот же вход. Я написал интерфейсы TestFrameWork и TestArguments как способ использования потоков тестов junit5, и каждый тестовый класс должен реализовывать интерфейс TestFrameWork с служебным классом, реализующим интерфейс TestArguments. Затем для большинства тестов достаточно написать простую лямбда-функцию, выполняющую только фактическую проверку. Интересно, хорошая это идея или ужасная.
Кроме того, я сделал три метода package-private, а не private, потому что я хотел протестировать их специально, что тоже пахнет подозрительно: конструктор, reduceInitialMatrix и getState (которые существуют только для тестирования reduceInitialMatrix, и это кажется еще хуже). У меня небольшие проблемы с установкой баланса между инкапсуляцией и тестированием, я с радостью приму любой совет и по этому поводу.
Всю исходную кодовую базу можно найти на мой гитхаб. Для этого вопроса я немного отредактировал его: вместо того, чтобы заставить HungarianSolver расширять абстрактный Solver и наследовать javadoc, я сделал HungarianSolver автономным и поместил javadoc непосредственно в него. Я построил и провел тесты на модифицированной версии, чтобы убедиться, что я ничего не сломал.
HungarianSolver.java
package AssignmentProblem;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
/**
* Implementation of the HungarianAlgorithm.
*/
class HungarianSolver {
final private int[][] costMatrix;
final private int[][] assignments;
final private int[] rowAssignments;
final private int[] colAssignments;
final private int nRows;
final private int nCols;
final private boolean[] coveredRows;
final private boolean[] coveredCols;
final private int[] starredRows;
final private int[] starredCols;
final private int[] primedRows;
final private int[] primedCols;
private int numberCoveredCols;
final private boolean transposed;
/**
* Instantiates a new solver on the given cost matrix. The proper way to get
* the solution of the assignment problem with a {@link HungarianSolver} is
* to call {@link #initialise(int[][])} rather than directly the constructor.
*
* @param costMatrix
*/
HungarianSolver(int[][] costMatrix) {
Solver.checkMatrixValidity(costMatrix);
if (costMatrix.length > costMatrix[0].length){
//flip matrix to have more columns than rows
transposed = true;
nRows = costMatrix[0].length;
nCols = costMatrix.length;
this.costMatrix = new int[nRows][nCols];
for (int i = 0; i < nRows; i++) {
for (int j = 0; j < nCols; j++) {
this.costMatrix[i][j] = costMatrix[j][i];
}
}
} else {
this.costMatrix = costMatrix;
nRows = costMatrix.length;
nCols = costMatrix[0].length;
transposed = false;
}
assignments = new int[nRows][2];
rowAssignments = new int[transposed ? nCols : nRows];
colAssignments = new int[transposed ? nRows : nCols];
coveredRows = new boolean[nRows];
coveredCols = new boolean[nCols];
starredRows = new int[nRows];
starredCols = new int[nCols];
primedRows = new int[nRows];
primedCols = new int[nCols];
Arrays.fill(starredRows, -1);
Arrays.fill(starredCols, -1);
Arrays.fill(primedRows, -1);
Arrays.fill(primedCols, -1);
Arrays.fill(rowAssignments, -1);
Arrays.fill(colAssignments, -1);
for (int[] assignment : assignments) {
Arrays.fill(assignment, -1);
}
}
protected static HungarianSolver initialise(int[][] costMatrix) {
HungarianSolver result = new HungarianSolver(costMatrix);
result.reduceInitialMatrix();
result.solveReducedMatrix();
return result;
}
/**
* Returns the column index assigned to each row.
* @return The result of the assignment problem from the row perspective.
* The i-th element of the output is the index of the column assigned to the
* i-th row, or -1 if the row has not been assigned.
*/
public int[] getRowAssignments() {
return this.rowAssignments;
}
public int[] getColumnAssignemnts() {
return this.colAssignments;
}
/**
* Returns the pairs of row and column indices of the assignments.
* @return The result of the assignment problem as pairs. Each element of
* the output is an assigned pair whose first element is the index of the
* row and the second element is the index of the column. Unassigned rows
* and columns are not included.
*/
public int[][] getAssignments() {
return this.assignments;
}
/**
* Reduces the values of the matrix to make zeroes appear. This
* corresponds to the first step of the Hungarian Algorithm.
*/
void reduceInitialMatrix() {
//first part: reduce all rows
for (int[] row : costMatrix) {
int min = row[0];
for (int val : row) {
if (val < min) {
min = val;
}
}
for (int j = 0; j < row.length; j++) {
row[j] -= min;
}
}
//second part: reduce all columns
for (int j = 0; j < nCols; j++) {
int min = costMatrix[0][j];
for (int[] row : costMatrix) {
if (row[j] < min) {
min = row[j];
}
}
for (int[] row : costMatrix) {
row[j] -= min;
}
}
}
/**
* Performs the main loop of the Hungarian algorithm.
*/
private void solveReducedMatrix() {
//Steps 0 and 1 have been preprocessed
//Step 2 : initial zero starring
for (int i = 0; i < nRows; i++) {
for (int j = 0; j < nCols; j++) {
if (costMatrix[i][j] == 0 && starredCols[j] == -1) {
coveredCols[j] = true;
numberCoveredCols++;
starredRows[i] = j;
starredCols[j] = i;
break;
}
}
}
while (numberCoveredCols < nRows) {
int[] position = primeZero();
while (position == null){
//Perform step 6
//Get minimal unmarked value
int min = Integer.MAX_VALUE;
for (int i = 0; i < nRows; i++) {
if (coveredRows[i]) {
continue;
}
for (int j = 0; j < nCols; j++) {
if (coveredCols[j]) {
continue;
}
if (costMatrix[i][j] < min) {
min = costMatrix[i][j];
if (min == 1){
break;
}
}
if (min == 1){
break;
}
}
}
//modify the matrix
for (int i = 0; i < nRows; i++) {
for (int j = 0; j < nCols; j++) {
if (!coveredRows[i]) {
/* If the row is uncovered and the column is covered,
then it's a no-op: add and subtract the same value.
*/
if (!coveredCols[j]) {
costMatrix[i][j] -= min;
}
} else if (coveredCols[j]) {
costMatrix[i][j] += min;
}
}
}
//go back to step 4
position = primeZero();
}
//perform step 5
invertPrimedAndStarred(position);
}
//format the result
int assignmentIndex = 0;
if (transposed){
for (int i = 0; i < nCols; i++){
rowAssignments[i] = starredCols[i];
if (starredCols[i] != -1){
assignments[assignmentIndex][0] = starredCols[i];
assignments[assignmentIndex][1] = i;
assignmentIndex++;
}
}
System.arraycopy(starredRows, 0, colAssignments, 0, nRows);
} else {
for (int i = 0; i < nRows; i++){
rowAssignments[i] = starredRows[i];
if (starredRows[i] != -1) {
assignments[assignmentIndex][0] = i;
assignments[assignmentIndex][1] = starredRows[i];
assignmentIndex++;
}
}
System.arraycopy(starredCols, 0, colAssignments, 0, nCols);
}
}
/**
* Primes uncovered zeroes in the cost matrix.
* Performs the fourth step of the Hungarian Algorithm.
* @return the (rowIndex,colIndex) coordinates of the primed zero to star
* that has been found, or null if no such zero has been found.
*/
private int[] primeZero() {
Queue<Integer> uncoveredColumnQueue = new LinkedList<>();
for (int i = 0; i < nRows; i++) {
if (coveredRows[i]) {
continue;
}
for (int j = 0; j < nCols; j++) {
if (coveredCols[j] || costMatrix[i][j] > 0) {
continue;
}
//Found a non-covered zero
primedRows[i] = j;
primedCols[j] = i;
if (starredRows[i] == -1) {
return new int[]{i,j};
} else {
coveredRows[i] = true;
coveredCols[starredRows[i]] = false;
numberCoveredCols -= 1;
//ignore the rest of the row but handle the uncovered column
uncoveredColumnQueue.add(starredRows[i]);
break;
}
}
}
while (!uncoveredColumnQueue.isEmpty()){
int j = uncoveredColumnQueue.remove();
for (int i = 0; i < nRows; i++){
if(coveredRows[i] || costMatrix[i][j] > 0) {
continue;
}
primedRows[i] = j;
primedCols[j] = i;
if (starredRows[i] == -1){
return new int[]{i,j};
} else {
coveredRows[i] = true;
coveredCols[starredRows[i]] = false;
numberCoveredCols -= 1;
uncoveredColumnQueue.add(starredRows[i]);
}
}
}
return null;
}
/**
* Stars selected primed zeroes to increase the line coverage of the matrix.
* Performs the fifth step of the Hungarian Algorithm.
* @param position array of size 2 containing the row and column indices of
* the first primed zero in the alternating series to modify.
*/
private void invertPrimedAndStarred(int[] position){
int currentRow = position[0];
int currentCol = position[1];
int tmp;
starredRows[currentRow] = currentCol;
while (starredCols[currentCol] != -1){
//Move star to its new row in the column of the primed zero
tmp = starredCols[currentCol];
starredCols[currentCol] = currentRow;
currentRow = tmp;
//Move star to its new column in the column of the previously
//starred zero
tmp = primedRows[currentRow];
starredRows[currentRow] = tmp;
currentCol = tmp;
}
//set starredCols of last changed zero and reset primes and lines covering
starredCols[currentCol] = currentRow;
for (int i = 0; i < coveredRows.length; i++){
coveredRows[i] = false;
primedRows[i] = -1;
}
//in next step, all columns containing a starred zero will be marked
//--> do it right away
for (int j = 0; j < nCols; j++){
if(!coveredCols[j] && starredCols[j] != -1){
numberCoveredCols++;
coveredCols[j] = true;
}
//if a column contained a prime zero, it will still contain one
//after the inversion, so the case where a column needs to be
//uncovered does not arise
primedCols[j] = -1;
}
}
/**
* @return The internal state of the cost matrix.
*/
int[][] getState() {
return this.costMatrix;
}
/**
* Checks the validity of the input cost matrix.
* @param costMatrix the matrix to solve.
* @throws IllegalArgumentException if {@code costMatrix } is not
* rectangular (e.g. rows do not all have the same length).
*/
static void checkMatrixValidity(int[][] costMatrix)
throws IllegalArgumentException{
if (costMatrix == null){
throw new IllegalArgumentException("input matrix was null");
}
if (costMatrix.length == 0){
throw new IllegalArgumentException("input matrix was of length 0");
}
for (int[] row : costMatrix){
if (row.length != costMatrix[0].length){
throw new IllegalArgumentException("input matrix was not rectangular");
}
}
}
}
TestArguments.java
package test.tools;
/**
* Interface defining the general contract that inner classes should implement
* to ease the unit testing.
*
* Concrete classes implementing it should provide a unique constructor similar
* to the main one of the class parameter, and override the toString object
* method.
*
* @param <T> class under test: the arguments will be used to generate
* instances of that class.
*/
public interface TestArguments<T> {
/**
* Initialises an object to use in a test.
* @return
*/
T convert();
}
TestFrameWork.java
package test.tools;
import static org.junit.jupiter.api.DynamicContainer.dynamicContainer;
import static org.junit.jupiter.api.DynamicTest.dynamicTest;
import java.util.Map;
import java.util.function.Consumer;
import java.util.function.Function;
import java.util.stream.Stream;
import org.junit.jupiter.api.DynamicNode;
import org.junit.jupiter.api.DynamicTest;
import org.junit.jupiter.api.function.Executable;
public interface TestFrameWork<T, S extends TestArguments<T>> {
/**
* @return a {@link Stream} of arguments to initialise an object to test.
*/
Stream<S> argumentsSupplier();
default String testName(String methodName, S args){
return String.format("%s.%s on %s",
this.getClass().getCanonicalName(), methodName, args);
}
/**
* Forges a {@link DynamicTest} to run the input test for each element
* returned by the implementation of
* {@link TestFrameWork#argumentsSupplier()}.
* @param methodName to set as the test name.
* @param tester to run as the test.
* @return a stream of nodes running the test.
*/
default Stream<DynamicTest> test(String methodName, Consumer<S> tester){
return test(argumentsSupplier(), methodName, tester);
}
/**
* Forges a {@link Stream} of {@link DynamicNode} that runs in independent
* {@link DynamicTest} instances each {@link Executable} returned by the
* input {@link Function} on each element returned by the implementation of
* {@link TestFrameWork#argumentsSupplier()}.
* @param methodName to set as the test container's name.
* @param testerStream to generate the {@link Stream} of test using for
* each element the {@link String} as a suffix in the test name and the
* {@link Executable} as the test to run.
* @return a stream of nodes running the tests.
*/
default Stream<DynamicNode> testContainer(String methodName,
Function<S, Stream<Map.Entry<String, Executable>>> testerStream){
return testContainer(argumentsSupplier(), methodName, testerStream);
}
/**
* Forges a {@link DynamicTest} to run the input test for each element
* of a {@link Stream} of arguments.
* @param stream of arguments, the tests will be run on each
* element.
* @param methodName to set as the test name.
* @param tester to run as the test.
* @return a stream of nodes running the tests.
*/
default Stream<DynamicTest> test(Stream<S> stream, String methodName, Consumer<S> tester){
return stream.map(args
-> dynamicTest(testName(methodName, args), () -> tester.accept(args)));
}
/**
* Forges a {@link Stream} of {@link DynamicNode} that runs in independent
* {@link DynamicTest} instances each {@link Executable} returned by the
* input {@link Function} on each element of the input {@link Stream}.
* @param stream of arguments, the tests will be run on each
* element.
* @param methodName to set as the test container's name.
* @param testerStream to generate the {@link Stream} of test using for
* each element the {@link String} as a suffix in the test name and the
* {@link Executable} as the test to run.
* @return a stream of nodes running the tests.
*/
default Stream<DynamicNode> testContainer(Stream<S> stream, String methodName,
Function<S, Stream<Map.Entry<String, Executable>>> testerStream){
return stream.map(args
-> {
String message = testName(methodName, args);
return dynamicContainer(message,
testerStream.apply(args).map(entry
-> dynamicTest(message + entry.getKey(), entry.getValue())));
});
}
}
HungarianSolverTest.java
package AssignmentProblem;
import java.util.Arrays;
import java.util.Comparator;
import java.util.stream.Stream;
import org.junit.jupiter.api.Assertions;
import static org.junit.jupiter.api.Assertions.assertArrayEquals;
import org.junit.jupiter.api.DynamicTest;
import org.junit.jupiter.api.TestFactory;
import test.tools.TestArguments;
import test.tools.TestFrameWork;
public class HungarianSolverTest implements TestFrameWork<HungarianSolver, HungarianArgument> {
@TestFactory
public Stream<DynamicTest> testInitialiseValidInput() {
//Check that initialise does not crash on valid input.
//Correctness of the result is checked in tests linked to the methods getting the results.
return test("initialise (valid input)", v -> v.convert());
}
@TestFactory
public Stream<DynamicTest> testInitialiseInvalidInput(){
Stream<HungarianArgument> cases = Stream.of(
new HungarianArgument(null, null, null, null, "null cost matrix"),
new HungarianArgument(new int[0][0], null, null, null, "size 0 cost matrix"),
new HungarianArgument(new int[][]{{0}, {0,1}, {0,1,2},{0,1},{0}}, null, null, null, "non-rectangular cost matrix"));
return test(cases,
"initialise (invalid input)",
v -> Assertions.assertThrows(IllegalArgumentException.class,
() -> v.convert()));
}
@TestFactory
public Stream<DynamicTest> testGetRowAssignments() {
return test("getRowAssignments", v -> assertArrayEquals(v.expectedRowAssignment, v.convert().getRowAssignments()));
}
@TestFactory
public Stream<DynamicTest> testGetColumnAssignemnts() {
return test("getColumnAssignments", v -> assertArrayEquals(v.expectedColAssignment, v.convert().getColumnAssignemnts()));
}
@TestFactory
public Stream<DynamicTest> testGetAssignments() {
Comparator<int[]> comparator = (first, second) ->
Integer.compare(first[0], second[0]) == 0 ? Integer.compare(first[1], second[1]) : Integer.compare(first[0], second[0]);
return test("getAssignments", v-> {
/*
There is no contract on the ordering of the result values.
*/
int[][] assignments = v.convert().getAssignments();
Arrays.sort(assignments, comparator);
Arrays.sort(v.expectedMatrixResult, comparator);
assertArrayEquals(v.expectedMatrixResult, assignments);
});
}
@TestFactory
public Stream<DynamicTest> testReduceInitialMatrix() {
Stream<HungarianArgument> cases = Stream.of(
new HungarianArgument(new int[][]{{25, 40, 35}, {40, 60, 35}, {20, 40, 25}},
new int[][]{{0, 0, 10}, {5, 10, 0}, {0, 5, 5}},
null, null, "square 3*3 matrix"),
new HungarianArgument(new int[][]{{150, 400, 450},{200, 600, 350}, {200, 400, 250}},
new int[][]{{0, 50, 250}, {0, 200, 100}, {0, 0, 0}},
null, null, "second square 3*3 matrix"),
new HungarianArgument(new int[][]{{70, 40, 20, 55},{65, 60, 45, 90},{30, 45, 50, 75},{25,0,55,40}},
new int[][]{{50, 20, 0, 0},{20, 15, 0, 10},{0, 15, 20, 10},{25, 0, 55, 5}},
null, null, "square 4*4 with initial zeroes matrix"),
new HungarianArgument(new int[][]{{1,2,25,13},{5,7,25,15},{10,13,16,13},{17,21,11,18},{15,15,15,14}},
new int[][]{{0,2,9,16,13},{0,3,11,19,12},{14,12,5,0,3},{0,0,0,5,0}},
null, null, "5*4 matrix without initial zeroes")
);
return test(cases,
"reduceInitialMatrix",
v -> {
HungarianSolver solver = v.convertWithConstructor();
solver.reduceInitialMatrix();
assertArrayEquals(v.expectedMatrixResult, solver.getState());
});
}
@Override
public Stream<HungarianArgument> argumentsSupplier() {
int worstCaseSize = 200;
int[][] worstCaseMatrix = new int[worstCaseSize][worstCaseSize];
for (int i = 0; i < worstCaseMatrix.length; i++) {
for (int j = 0; j < worstCaseMatrix[i].length; j++){
worstCaseMatrix[i][j] = (i+1)*(j+1);
}
}
int[] worstCaseLinearExpectation = new int[worstCaseSize];
Arrays.setAll(worstCaseLinearExpectation, i -> worstCaseSize-i-1);
int[][] worstCaseExpectedAssignments = new int[worstCaseSize][2];
for (int i = 0; i < worstCaseSize; i++){
worstCaseExpectedAssignments[i][0] = i;
worstCaseExpectedAssignments[i][1] = worstCaseSize-i-1;
}
return Stream.of(new HungarianArgument(new int[][]{{2500, 4000, 3500}, {4000, 6000, 3500}, {2000, 4000, 2500}},
new int[][]{{0,1},{1,2},{2,0}}, new int[]{1,2,0}, new int[]{2,0,1}, "simple 3*3 matrix"),
new HungarianArgument(new int[][]{{2000,6000,3500},{1500, 4000, 4500},{2000,4000,2500}},
new int[][]{{0,0},{1,1},{2,2}}, new int[]{0,1,2}, new int[]{0,1,2}, "mildly complex 3*3 matrix"),
new HungarianArgument(new int[][]{{1,2,3,4},{5,6,7,8},{9,10,11,12}},
new int[][]{{0,0},{1,1},{2,2}}, new int[]{0,1,2}, new int[]{0,1,2,-1}, "complex 4*3 matrix with equality case"),
new HungarianArgument(new int[][]{{1,2,25,13},{5,7,25,15},{10,13,16,13},{17,21,11,18},{15,15,15,14}},
new int[][]{{0,1},{1,0},{2,3},{3,2}}, new int[]{1,0,3,2,-1}, new int[]{1,0,3,2}, "first complex 5*4 matrix without equality case"),
new HungarianArgument(new int[][]{{1,2,25,13},{5,7,25,15},{10,13,16,14},{17,21,11,18},{15,15,15,13}},
new int[][]{{0,1},{1,0},{2,3},{3,2}}, new int[]{1,0,3,2,-1}, new int[]{1,0,3,2}, "second complex 5*4 matrix without equality case"),
new HungarianArgument(worstCaseMatrix, worstCaseExpectedAssignments,
worstCaseLinearExpectation, worstCaseLinearExpectation, "worst case " + worstCaseSize + "*" + worstCaseSize + " matrix")
);
}
}
class HungarianArgument implements TestArguments<HungarianSolver>{
final int[][] costMatrix;
final int[][] expectedMatrixResult;
final int[] expectedRowAssignment;
final int[] expectedColAssignment;
private final String name;
HungarianArgument(int[][] costMatrix, int[][] expectedMatrixResult,
int[] expectedRowAssignment, int[] expectedColAssignment,
String name){
this.costMatrix = costMatrix;
this.expectedMatrixResult = expectedMatrixResult;
this.expectedRowAssignment = expectedRowAssignment;
this.expectedColAssignment = expectedColAssignment;
this.name = name;
}
@Override
public HungarianSolver convert() {
return HungarianSolver.initialise(costMatrix);
}
public HungarianSolver convertWithConstructor(){
return new HungarianSolver(costMatrix);
}
@Override
public String toString(){
return this.name;
}
}