http://en.wikipedia.org/wiki/Assignment_problem
Ситуация, которую я собираюсь описать, взята из следующей лекции: http://www.youtube.com/watch?v=BUGIhEecipE в 32:00
Профессор объясняет эту проблему, но не предлагает никакого решения
Предположим, у нас есть следующая таблица. Строки представляют работников, столбцы - назначения и значения - количество времени, необходимое работнику для выполнения назначения
3 1 1 4
4 2 2 5
5 3 4 8
4 2 5 9
Первоначально я нахожу минимальное значение каждой строки и вычитаю его из всех других значений той же строки. Я делаю то же самое для столбцов и получаю следующий результат
0 0 0 0
0 0 0 0
0 0 1 2
0 0 3 4
теперь очевидным решением является то, что рабочий 1 выполняет задачу 4, рабочий 2 - задачу 3, рабочий 3 - задачу 2, рабочий 1 - задачу 1
однако, используя язык программирования, вы не сможете его найти. Если я сделаю произвольный выбор, я могу выбрать, например,
рабочий 1, задание 1
рабочий 2, задание 2
и тогда я не могу ничего выбрать, потому что оставшиеся расходы больше нуля.
если я сделаю тиканье, мне в основном придется пометить все строки и все столбцы, чтобы значения таблицы действительно не изменились.
У меня вопрос, как преодолеть эту проблему? Есть ли способ, который поможет мне достичь этого?
Кроме того, можете ли вы порекомендовать мне более простой способ решения проблемы с назначением? Весь этот процесс тиканья и вычитания мин / макс звучит не так, как сложность с малым временем
Я пытаюсь реализовать алгоритм, но, поскольку мне, возможно, придется иметь дело с подобной ситуацией, я не вижу смысла в реализации чего-то, что в итоге окажется неправильным
заранее спасибо