Венгерский алгоритм и несколько факторов - PullRequest
Новая
       79

Венгерский алгоритм и несколько факторов

4 голосов
/ 03 августа 2009

У меня есть ситуация, когда мне нужно распределить людей по нескольким событиям. Если бы мы просто имели цену как фактор, это было бы хорошо, но есть ряд факторов, которые входят.

Сначала немного фона. Это для некоммерческой организации, которая продвигает часы истории для детей, которые госпитализируются по любой причине, поэтому они зависят от добровольной работы, чтобы сделать это. Таким образом, поскольку они полагаются на добрую волю людей, они дают людям столько работы, сколько люди могут / хотят делать, что варьируется как:

  • Некоторые люди могут делать только по утрам, а некоторые другие могут делать только после обеда;
  • Некоторые люди могут ходить только по понедельникам и четвергам, другие не могут ходить в августе или декабре;
  • Некоторые люди могут ходить только один раз в месяц, другие могут ходить 4 раза (и даже другие люди получают «приоритет» в этих действиях, потому что они более опытны и могут делать это 10 раз в месяц)

Итак, я вроде разобрался с первыми двумя. Поскольку венгерский алгоритм имеет отношение к цене, я бы дал им тупо высокую цену за те времена, когда они не могут идти. Однако, как бы вы поступили с остальными?

Я думал дать им какую-то оценку Нечто подобное: один человек, который может делать это раз в месяц, стоит около 1000 очков. Если кто-то может ходить 10 раз в месяц, этот человек стоит 100 баллов (1000 на основе деления на 10). Кроме того, способ распространить это будет увеличивать цену всякий раз, когда будет выполнено отдельное действие, например, (у выбранных людей есть * на их стоимость):

Первая итерация 

         | August 1st 2009
Person A | 1000
Person B | 500 *

Вторая итерация 

         | August 8th 2009
Person A | 1000 *
Person B | 1000

Это был бы способ распределить соответственно между всеми людьми, отдавая больший приоритет тем, кто может сделать это несколько раз.

Что вы думаете и как бы вы это сделали?

1 Ответ

15 голосов
/ 03 августа 2009

Это проблема планирования / оптимизации, поэтому ключевой вопрос - «какое количество вы пытаетесь максимизировать»? Я предполагаю, что вы стремитесь максимально увеличить общее количество часов, отработанных на всех ваших добровольцах без столкновений, с учетом ограничений по времени каждого добровольца. Вы также упомянули о том, что нужно отдавать предпочтение волонтерам с большим опытом, поэтому звучит так, будто вы говорите, что «некоторые волонтеры предпочитают другим».

Тогда это классическая проблема согласования двудольных . Смотрите, например стр.498 из Стивен Скиена, Руководство по разработке алгоритма (2-е изд.). Основной подход заключается в построении графа с вершинами, представляющими как набор добровольцев, так и набор временных интервалов, которые вы пытаетесь заполнить. Края связывают добровольцев с действительными временными интервалами. Таким образом, оптимальным решением является максимально возможный набор ребер, где ни один волонтер или временной интервал не повторяются. Это совпадение.

Некоторые из ваших добровольцев могут иметь возможность использовать более одного слота; это можно смоделировать, повторяя эту вершину добровольца несколько раз.

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

Если вам нужна дополнительная информация, включая другие альтернативы, и больше ссылок на реализации, я настоятельно рекомендую получить копию Руководства по разработке алгоритмов - это удивительно четкий и практический справочник.

...