Использование ford fulkerson для размещения N сотрудников на M должностях с ролями

Question

Я пытаюсь решить математическую задачу, используя Форд-Фулкерсон, но у меня есть некоторые проблемы.

Это проблема

    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 значение 1, если сотрудник X может работать в позиции Y, в противном случае я ставлю 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, содержащий индексы столбцов (потому что они являются позиционными идентификаторами, а не упорядочены по номерам).

Вот как я создаю матрицу:

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 только там, где у меня есть совпадение между сотрудниками и должностями.

Кто-нибудь знает, как решить эту проблему? заранее спасибо

Answer 1

Вы передаете seen по значению. Это не правильно. Это должно быть передано по ссылке. То, что у вас сейчас есть, на самом деле является своего рода возвратом (первоначальное доказательство сложности времени алгоритма основано на том факте, что каждая вершина может быть посещена максимум один раз во время поиска в глубину, и это не так в вашей текущей реализации). Вот почему это работает медленно. Переходя seen по ссылке должен это исправить.