ЛУЧШЕЕ совпадение с использованием алгоритма максимального потока - PullRequest
Новая
       31

ЛУЧШЕЕ совпадение с использованием алгоритма максимального потока

0 голосов
/ 22 января 2019

Я хотел бы сделать ЛУЧШЕЕ соответствие между человеком и компанией, используя алгоритм максимального потока.

Каждая строка в следующей таблице представляет для каждого человека, если он / она хотел бы обратиться кэта компания.(ДА = человек будет применяться, НЕТ = не будет применяться, МОЖЕТ = может применяться).Скобки человека представляют количество заявок, которые каждый человек отправит, а скобки компании представляют количество открытых вакансий.

СМОТРИТЕ ТАБЛИЦУ

Я думалчтобы сделать эту задачу проблемой максимального потока, сделав каждого человека и каждую компанию вершиной в графе, следующим образом:

Например: 

S -> Bob -> Apple -> T
S -> Bob -> Google -> T
S -> David -> Apple -> T

Пожалуйста, сообщите:

  1. Как мне обратиться к предпочтениям (ДА / МОЖЕТ БЫТЬ) каждого человека?
  2. Каким должен быть вес каждого ребра?

Спасибовсе

1 Ответ

0 голосов
/ 23 января 2019

Кажется, это не проблема максимального потока, но это двусторонний подход с максимальным весом.

Во-первых, количество заявок, которые каждый человек отправит, является неактуальной информацией, потому что, как только мы сделаемна свидание, все должны только отправить одно заявление.Таким образом, мы можем убрать это из проблемы.

Затем мы можем расширить столбцы в 1 для каждой позиции.Например, у Apple есть две открытые позиции, поэтому мы расширили бы это до двух столбцов яблока и удалили информацию о скобках из столбцов.

Теперь задача состоит в том, чтобы найти максимальное двустороннее соответствие между строками и столбцами,для которых был бы уместен венгерский алгоритм или аналогичный.

...