PHP 中具有多项分配的匈牙利算法

Question

下面我们面临匈牙利算法的多重赋值问题

场景：

我们有100名学生和5门课程，学生可以优先投票。所以每个学生都会被分配到一门特定的课程。

优先级从 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 中。

Answer 1

假设课程 1 可以容纳 x_1 名学生，课程 2 可以容纳 x_2 名学生，...，课程 5 可以容纳 x_5 名学生，用 x_1 列用于课程 1，x_2 列用于课程 2，...，x_5 列用于课程 5。在每个 x_i 列中复制每个学生对课程 i 的评分.除非您的课程容量不超过您的学生人数，否则算法终止时将有未分配的列，除非您的课程容量不小于您的学生人数，否则将有未分配的行。

PHP 中具有多项分配的匈牙利算法

Hungarian algorithm in PHP with multiple assignments

php

algorithm

subgraph

assign

pairing-heap