Венгерский алгоритм (также алгоритм присвоения Munkres)
Ошибка «команда не найдена» печатается в stderr, когда он не находит двоичный файл в папках, сконфигурированных в env $ PATH
. Сначала вам нужно выяснить, существует ли он с: 110]
, если вы найдете двоичный файл, попробуйте установить переменную PATH с помощью:
export PATH=$PATH:/usr/bin/
, затем попробуйте снова запустить sudo.
5 ответов
Страница Wikipedia, с которой Вы связались, имеет шаги о том, как сделать этот алгоритм вручную на матрице. Реализация Python также использует матрицы. Иногда единственный способ понять алгоритм состоит в том, чтобы ступить через него вручную или в интерактивной консоли.
Это говорит, что y значений S и T является потенциальным ответом, если y в я и y в j - вместе меньше, чем стоимость, вычисленная для того положения до сих пор (находящий самый низкий потенциальный ответ) для каждого положения в S и T.
Это - проблема динамического программирования, если я вспоминаю правильно. Идеальное соответствие состояло бы в том, когда парень, самый дешевый уровень которого, оказывается, то, что он выбран, чтобы сделать.
Функция отображает каждую вершину в графике, который является объединением S и T, который является тем, что тот U-образный символ означает в систему рационального числа, которая является тем, что это Q представляет тем неравенством для данной пары вершин. Какая часть нотации там не имеет смысла все еще?
Потенциальная функция y присваивает номер каждой вершине в Вашем полном биграфе таким способом, что сумма потенциалов любой вершины от S (группа всех людей) и любой вершины от T (набор всех заданий) меньше, чем значение края, соединяющего эти вершины (настолько меньший, чем стоимость человека, делающего задание). Функция, которая присваивает 0 каждой вершине, является хорошим примером допустимой потенциальной функции.
Значение потенциала y является суммой потенциалов всех вершин (это - определение).
Таким образом стоимость каждого идеального соответствия является, по крайней мере, значением каждого потенциала.
Это довольно очевидно: в идеальном соответствии необходимо выбрать n края, которые не имеют общих вершин. Стоимость каждого края ниже, чем сумма потенциала ее вершин (из определения потенциала). При подведении итогов затрат на все края от соответствия это будет выше, чем значение потенциала для графика.
Теперь, алгоритм вычисляет потенциал и соответствие, такое, что они стоят/оценивают, то же. Поскольку значение потенциала является нижней границей минимальной стоимости для проблемы, Вы получаете оптимальное решение.
Это доказывает алгоритм. Теперь необходимо посмотреть на него и понять, почему и как это находит идеальное соответствие и потенциал с равной стоимостью/значением.
Вы можете проверить эту книгу Jungnickel, которая содержит тщательное теоретическое обсуждение венгерского алгоритма, начиная с P 421, но также работает пример. Работая через пример, вы должны уметь видеть, почему алгоритм является O (N3)).