下面我们将面临匈牙利算法的多重赋值问题。
场景:
我们有100名学生和5门类(class)，学生可以优先投票。 因此，每个学生都会被分配到一门特定类(class)。
优先级从 1 到 5。1 最低，5 最高
原始数据如下所示:
显然行数多于列数。
我们面临的问题是:每列需要不止一个赋值。
这是负责使用返回无效结果的匈牙利算法进行赋值的 PHP 代码。
<?php
class Hungarian {
function Hungarian() {
//Default constructor
}
function do_hungarian($matrix)
{
$h = count($matrix);
$w = count($matrix[0]);
if ($h < $w)
{
for ($i = $h; $i < $w; ++$i)
{
$matrix[$i] = array_fill(0, $w, INF);
}
}
elseif ($w < $h)
{
foreach ($matrix as &$row)
{
for ($i = $w; $i < $h; ++$i)
{
$row[$i] = INF;
}
}
}
$h = $w = max($h, $w);
$u = array_fill(0, $h, 0);
$v = array_fill(0, $w, 0);
$ind = array_fill(0, $w, -1);
foreach (range(0, $h - 1) as $i)
{
$links = array_fill(0, $w, -1);
$mins = array_fill(0, $w, INF);
$visited = array_fill(0, $w, false);
$markedI = $i;
$markedJ = -1;
$j = 0;
while (true)
{
$j = -1;
foreach (range(0, $h - 1) as $j1)
{
if (!$visited[$j1])
{
$cur = $matrix[$markedI][$j1] - $u[$markedI] - $v[$j1];
if ($cur < $mins[$j1])
{
$mins[$j1] = $cur;
$links[$j1] = $markedJ;
}
if ($j == -1 || $mins[$j1] < $mins[$j])
{
$j = $j1;
}
}
}
$delta = $mins[$j];
foreach (range(0, $w - 1) as $j1)
{
if ($visited[$j1])
{
$u[$ind[$j1]] += $delta;
$v[$j1] -= $delta;
}
else
{
$mins[$j1] -= $delta;
}
}
$u[$i] += $delta;
$visited[$j] = true;
$markedJ = $j;
$markedI = $ind[$j];
if ($markedI == -1)
{
break;
}
}
while (true)
{
if ($links[$j] != -1)
{
$ind[$j] = $ind[$links[$j]];
$j = $links[$j];
}
else
{
break;
}
}
$ind[$j] = $i;
}
$result = array();
foreach (range(0, $w - 1) as $j)
{
$result[$j] = $ind[$j];
}
return $result;
}
/*$m = [
[ INF, 7858, 8743, 17325, 18510, 9231, 4920, 7056, 9701, 5034, 7825],
[ 8128, INF, 5021, 13603, 19635, 11386, 7075, 8840, 1843, 7189, 9256],
[ 6809, 5364, INF, 8582, 14614, 10067, 5756, 5904, 7207, 3882, 4235],
[ 7849, 5515, 1040, INF, 15654, 11107, 6796, 4713, 7358, 4900, 5275],
[10918, 8365, 4109, 5808, INF, 14176, 9865, 7928, 931, 7991, 8344],
[ 336, 7285, 2830, 11412, 17444, INF, 4347, 6483, 6688, 4461, 7065],
[ 1053, 2938, 3823, 12405, 15835, 4311, INF, 2136, 4781, 114, 2905],
[ 8930, 802, 5823, 14405, 20437, 12188, 7877, INF, 2645, 7429, 10058],
[ 9987, 7434, 3178, 11760, 17792, 13245, 8934, 6997, INF, 7060, 7413],
[10518, 2824, 3709, 12291, 15721, 13776, 9465, 2022, 4667, INF, 7944],
[ 2574, 4459, 5344, 9561, 17356, 5832, 1521, 3657, 6302, 1635, INF]
];
print_r(hungarian($m));*/
}
?>
编辑:这是返回有效结果的 Sktip。
<?php
/*
Author: © Noli
Edited: 21.06.2015
Description: Klasse zur Verwendung der Ungarischem Methode
- Ermittlung des optimalzustands einer relation anhand von bipatite graph matching.
Portierung von © Noli
*/
class HungarianBipatiteMatching {
public $costMatrix = array();
public $rows = 0;
public $cols = 0;
public $dim = 0;
public $labelByWorker = array();
public $labelByJob =array();
public $minSlackWorkerByJob=array();
public $minSlackValueByJob=array();
public $matchJobByWorker=array();
public $matchWorkerByJob=array();
public $parentWorkerByCommittedJob=array();
public $committedWorkers=array();
public function HungarianBipatiteMatching($intMatrix) {
$this->rows = sizeof($intMatrix);
$this->cols = sizeof($intMatrix[0]);
$this->dim = max($this->rows,$this->cols);
for($i = 0;$i<$this->dim;$i++) {
$costMatrix[$i] = array_fill(0,$this->dim,0);
}
for ($w = 0; $w < $this->dim; $w++) {
if ($w < sizeof($intMatrix)){
if (sizeof($intMatrix[$w]) != $this->cols){
throw new InvalidArgumentException("Irregular cost matrix");
}
$this->costMatrix[$w] = $this->arrayCopyOf($intMatrix[$w],$this->dim);
}
else {
$this->costMatrix[$w] = array();
for($i = 0;$i<$this->dim;$i++){
$this->costMatrix[$w][] = 0;
}
}
}
for($i = 0;$i<$this->dim;$i++) {
$this->labelByWorker[] = 0;
$this->labelByJob[] = 0;
$this->minSlackWorkerByJob[] = 0;
$this->minSlackValueByJob[] = 0;
$this->parentWorkerByCommittedJob[] = 0;
$this->matchJobByWorker[] = 0;
$this->matchWorkerByJob[] = 0;
}
$this->committedWorkers = array_fill(0, $this->dim, false);
$this->matchJobByWorker = array_fill(0,$this->dim,-1);
$this->matchWorkerByJob = array_fill(0,$this->dim,-1);
}
public function computeInitialFeasibleSolution() {
for ($j = 0; $j < $this->dim; $j++) {
$this->labelByJob[$j] = INF;
}
for ($w = 0; $w < $this->dim; $w++) {
for ($j = 0; $j < $this->dim; $j++) {
if ($this->costMatrix[$w][$j] < $this->labelByJob[$j]) {
$this->labelByJob[$j] = $this->costMatrix[$w][$j];
}
}
}
}
public function execute() {
$this->reduce();
$this->computeInitialFeasibleSolution();
$this->greedyMatch();
$w = $this->fetchUnmatchedWorker();
while ($w < $this->dim) {
$this->initializePhase($w);
$this->executePhase();
$w = $this->fetchUnmatchedWorker();
}
$result = $this->arrayCopyOf($this->matchJobByWorker, $this->rows);
for ($w = 0; $w < sizeof($result); $w++){
if ($result[$w] >= $this->cols){
$result[$w] = -1;
}
}
return $result;
}
protected function executePhase() {
while (true)
{
$minSlackWorker = -1;
$minSlackJob = -1;
$minSlackValue = INF;
for ($j = 0; $j < $this->dim; $j++)
{
if ($this->parentWorkerByCommittedJob[$j] == -1)
{
if ($this->minSlackValueByJob[$j] < $minSlackValue)
{
$minSlackValue = $this->minSlackValueByJob[$j];
$minSlackWorker = $this->minSlackWorkerByJob[$j];
$minSlackJob = $j;
}
}
}
if ($minSlackValue > 0)
{
$this->updateLabeling($minSlackValue);
}
$this->parentWorkerByCommittedJob[$minSlackJob] = $minSlackWorker;
if ($this->matchWorkerByJob[$minSlackJob] == -1)
{
$committedJob = $minSlackJob;
$parentWorker = $this->parentWorkerByCommittedJob[$committedJob];
while (true)
{
$temp = $this->matchJobByWorker[$parentWorker];
$this->match($parentWorker, $committedJob);
$committedJob = $temp;
if ($committedJob == -1)
{
break;
}
$parentWorker = $this->parentWorkerByCommittedJob[$committedJob];
}
return;
}
else
{
$worker = $this->matchWorkerByJob[$minSlackJob];
$this->committedWorkers[$worker] = true;
for ($j = 0; $j < $this->dim; $j++)
{
if ($this->parentWorkerByCommittedJob[$j] == -1)
{
$slack = $this->costMatrix[$worker][$j]
- $this->labelByWorker[$worker] - $this->labelByJob[$j];
if ($this->minSlackValueByJob[$j] > $slack)
{
$this->minSlackValueByJob[$j] = $slack;
$this->minSlackWorkerByJob[$j] = $worker;
}
}
}
}
}
}
protected function fetchUnmatchedWorker()
{
$w;
for ($w = 0; $w < $this->dim; $w++)
{
if ($this->matchJobByWorker[$w] == -1)
{
break;
}
}
return $w;
}
protected function greedyMatch()
{
for ($w = 0; $w < $this->dim; $w++)
{
for ($j = 0; $j < $this->dim; $j++)
{
if ($this->matchJobByWorker[$w] == -1
&& $this->matchWorkerByJob[$j] == -1
&& $this->costMatrix[$w][$j] - $this->labelByWorker[$w] - $this->labelByJob[$j] == 0)
{
$this->match($w, $j);
}
}
}
}
protected function initializePhase($w)
{
$this->committedWorkers = array_fill(0,sizeof($this->committedWorkers),false);
//Arrays.fill(committedWorkers, false);
$this->parentWorkerByCommittedJob = array_fill(0,sizeof($this->parentWorkerByCommittedJob),-1);
//Arrays.fill(parentWorkerByCommittedJob, -1);
$this->committedWorkers[$w] = true;
for ($j = 0; $j < $this->dim; $j++)
{
$this->minSlackValueByJob[$j] = $this->costMatrix[$w][$j] - $this->labelByWorker[$w]
- $this->labelByJob[$j];
$this->minSlackWorkerByJob[$j] = $w;
}
}
protected function match($w, $j)
{
$this->matchJobByWorker[$w] = $j;
$this->matchWorkerByJob[$j] = $w;
}
protected function reduce()
{
for ($w = 0; $w < $this->dim; $w++)
{
$min = INF;
for ($j = 0; $j < $this->dim; $j++)
{
if ($this->costMatrix[$w][$j] < $min)
{
$min = $this->costMatrix[$w][$j];
}
}
for ($j = 0; $j < $this->dim; $j++)
{
$this->costMatrix[$w][$j] -= $min;
}
}
$min = array_fill(0,$this->dim,0); //ALERT
for ($j = 0; $j < $this->dim; $j++)
{
$min[$j] = INF;
}
for ($w = 0; $w < $this->dim; $w++)
{
for ($j = 0; $j < $this->dim; $j++)
{
if ($this->costMatrix[$w][$j] < $min[$j])
{
$min[$j] = $this->costMatrix[$w][$j];
}
}
}
for ($w = 0; $w < $this->dim; $w++)
{
for ($j = 0; $j < $this->dim; $j++)
{
$this->costMatrix[$w][$j] -= $min[$j];
}
}
}
protected function updateLabeling($slack)
{
for ($w = 0; $w < $this->dim; $w++)
{
if ($this->committedWorkers[$w])
{
$this->labelByWorker[$w] += $slack;
}
}
for ($j = 0; $j < $this->dim; $j++)
{
if ($this->parentWorkerByCommittedJob[$j] != -1)
{
$this->labelByJob[$j] -= $slack;
}
else
{
$this->minSlackValueByJob[$j] -= $slack;
}
}
}
public function arrayCopyOf($array, $size) { // Java API port
$tmp = array();
foreach($array as $arr) {
$tmp[] = $arr;
}
if(sizeof($array) < $size) {
for($i = 0; $i < $size-sizeof($array); $i++) {
$tmp[]=0;
}
}
return $tmp;
}
}
/*$m = array(
array(73, 52, 35, 83, 97, 18, 74, 58),
array(39, 61, 69, 93, 8, 29, 21, 80),
array(88, 54, 55, 28, 80, 32, 77, 86),
array(73, 82, 25, 34, 26, 13, 74, 25),
array(65, 65, 17, 92, 71, 85, 69, 39),
array(40, 32, 43, 45, 12, 41, 72, 41),
array(75, 33, 82, 48, 25, 65, 71, 9),
array(39, 32, 12, 48, 86, 77, 36, 69)
);
$hungarian = new HungarianBipatiteMatching($m);
$result = $hungarian->execute();
echo("RESULT");
print_r($result);
echo("<br>done");*/
?>
注意:请耐心等待，这是来自 Java 的低质量移植。
因此算法正在生成这个矩阵的方阵，结果显示损坏的数据。
我考虑了多种解决方案。
根据列的大小切割矩阵，产生很多方阵。这可能会破坏算法的主要功能。
另一种解决方案是尽可能多地分配，并在新例程中处理其余部分，直到没有更多条目为止。
显然该算法还没有提供这种能力。
是否有可能在 MySQL 中执行此操作的解决方案，因此原始数据存储在 MySQL DBS 中。
最佳答案
假设类(class) 1 可以容纳 x_1 名学生，类(class) 2 可以容纳 x_2 名学生，...，类(class) 5 可以容纳 x_5 名学生，创建您的初始矩阵，其中 x_1 列用于类(class) 1，x_2 列用于类(class) 2，... ，类(class) 5 的 x_5 列。在每个 x_i 列中复制每个学生对类(class) i 的评分。除非您的类(class)容量不超过学生人数，否则算法终止时将有未分配的列，除非您的类(class)容量不小于学生人数，否则将有未分配的行。
关于php - 具有多项分配的 PHP 中的匈牙利算法，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/30892659/