0

我正在尝试使用 Ford-Fulkerson 解决数学问题，但我遇到了一些问题。

这就是问题

    I have a list of employees (Jack, John, Al, ...).
    I have a list of roles (R1, R2, R3, ...).
    I have a list of working positions (W1, W2, W3, ...).

    Every employee has a set of roles, like Jack has R1 and R2, ...
    Every working position has a set of roles that can support,
    like to work in position W1 you need R1 or R2, ...

我需要找到员工的最佳配置 - 工作职位，以确保每个工作职位都有一名具有合适角色的员工在那里工作（每个职位一名员工）。

我尝试使用此算法http://www.geeksforgeeks.org/maximum-bipartite-matching/

我建立了一个矩阵，其中每个员工都有一行，每个工作职位都有一个列。如果 X 员工可以在 Y 位置工作，我在 X 行、Y 列输入值 1，否则我输入 0。

上面的算法用 PHP 重写，在员工数量 <= 职位数量之前运行良好。

如果我的员工比职位多，算法计算时间往往会发散到无限大。

下面是算法代码：

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;
}

一切都类似于上面链接中的算法，除了我传递了 $cols 数组，其中包含列的索引（因为它们是位置 ID，而不是数字排序的）。

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

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;
}

所以我只在员工和职位匹配的地方放 1。

任何人都知道如何解决这个问题？提前致谢

4

1 回答 1

0

你按价值传递seen。这是不正确的。它应该通过引用传递。您现在所拥有的实际上是某种回溯（原始算法时间复杂度证明基于这样一个事实，即在深度优先搜索期间每个顶点最多可以访问一次，而在您当前的实现中并非如此）。这就是它运行缓慢的原因。seen通过引用传递应该修复它。

于 2014-08-08T08:54:10.143 回答