README

PHP实现线性指派问题各种算法。

文档

Jonker和Volgenant的原始论文可以在SpringerLink或doc/文件夹中找到。

使用方法

hungarian库包含解决线性指派问题所需的基本元素，以及一些抽象，使集成更容易。

基本用法

原始矩阵对象通过整数索引，允许获取和设置值，它始终是正方形矩阵。要填充一个三乘三的矩阵，您可以这样做。

use Kickin\Hungarian\Matrix\Matrix;

$matrix = new Matrix(3);
$matrix->set(0, 0, 10);
$matrix->set(1, 0, 15);
$matrix->set(2, 0, 12);
$matrix->set(0, 1, 12);
$matrix->set(1, 1, 13);
$matrix->set(2, 1, 14);
$matrix->set(0, 2, 15);
$matrix->set(1, 2, 17);
$matrix->set(2, 2, 25);

使用上面的矩阵，我们可以使用匈牙利方法。

use Kickin\Hungarian\Algo\Hungarian;

$solver = new Hungarian();
$result = $solver->solve($matrix);

或者，如果您想找到得分最高的分配，可以调用solveMax()。

$result = $solver->solveMax($matrix);

在底层，这相当于调用invert()后解决矩阵。

然后将此结果用作元组的列表。

foreach($result as [$row, $col]){
  echo $row . ": " . $col . "\n";
}

其他类型的矩阵

在大多数情况下，您实际上并不是试图配对整数，相反，您可能希望将用户分配到任务。一种方法是通过使用字符串标签来实现。

use Kickin\Hungarian\Matrix\StringMatrix;

$matrix = new StringMatrix(["Alice", "Bob", "Carol"], ["Bathroom", "Kitchen", "Windows"]);
$matrix->set("Alice", "Bathroom", 10);
$matrix->set("Bob",   "Bathroom", 15);
$matrix->set("Carol", "Bathroom", 12);
$matrix->set("Alice", "Kitchen",  12);
$matrix->set("Bob",   "Kitchen",  13);
$matrix->set("Carol", "Kitchen",  14);
$matrix->set("Alice", "Windows",  15);
$matrix->set("Bob",   "Windows",  17);
$matrix->set("Carol", "Windows",  25);

另一种选择是使用对象作为标签，例如使用Eloquent。

use Kickin\Hungarian\Matrix\LabeledMatrix;

$matrix = new LabeledMatrix(User::all(), Task::all());

MatrixBuilder

最后，您可能没有正方形矩阵，或者需要编写相当多的模板代码来创建适当的矩阵。为了帮助您，您可以使用MatrixBuilder类。这将自动确保您的矩阵是正方形的，并在需要时进行扩展。

use Kickin\Hungarian\Matrix\MatrixBuilder;

$builder = new MatrixBuilder();
$builder->setRowSource(["Alice", "Bob", "Carol", "Dave"]);
$builder->setColSource(["Garbage", "Sweep floor"]);
$builder->setDefaultValue(1);
$builder->setAugmentValue(10);
$builder->setMappingFunction(function($row, $col){
  return 1; // Define your own scoring for any assignment pair
});

$matrix = $builder->build();

如果需要，您可以轻松地从结果中删除未分配的行和列。

$result = $solver->solve($matrix);
$assignedOnly = $result->withoutUnassigned();