0

基于这篇很棒的文章http://www.geeksforgeeks.org/maximum-bipartite-matching/ ，我有一个 Ford Fulkerson 算法的工作 php 实现

目前，控制算法的矩阵可以在其单元格中具有 1 或 0 的值，以表示每个员工在该职位上工作的可能性。我想为算法增加容量，基本上在矩阵中放置更高的值，如 2、3 等，以表达选择员工而不是另一个员工的偏好。

您对如何编辑算法以增加容量有什么建议吗？

这是算法代码：

function maxMatch($matrix, $cols) {
    $match = array();
    foreach ($cols as $v => $item) {
        $match[$item] = -1;
    }
    $result = 0;
    foreach ($matrix as $u => $row) {
        $seen = array();
        foreach ($cols as $v => $item) {
            $seen[$item] = 0;
        }
        if ($this->checkVertex($matrix, $u, $seen, $match)) {
            print_r($match);
            $result++;
        }
    }
    return $match;
}

function checkVertex($matrix, $u, &$seen, &$match) {
    foreach ($matrix[$u] as $v => $row) {
        if ($matrix[$u][$v] && !$seen[$v]) {
            $seen[$v] = TRUE;
            if ($match[$v] < 0 || $this->checkVertex($matrix, $match[$v], $seen, $match)) {
                $match[$v] = $u;
                return TRUE;
            }
        }
    }
    return FALSE;
}

这就是我创建矩阵的方式：

function createMatrix($year, $month, $day, $shift) {
    global $sql;

    $result = $sql->query("VERY HUGE SELECT FOR EMPLOYEES AND POSITIONS MATCH");

    while ($row = $result->fetch_assoc()) {
        $matrix[$row['employee']][$row['position']] = 1;
    }
    return $matrix;
}

非常感谢，马可

4

0 回答 0