Хабр Курсы для всех
РЕКЛАМА
Практикум, Хекслет, SkyPro, авторские курсы — собрали всех и попросили скидки. Осталось выбрать!
Хабр доступен 24/7 благодаря поддержке друзей
Комментарии 21
Очень интересный вопрос, попытаюсь ответить:
Потому что каждый шаг алгоритма двигает нас к тому, чтобы получить нули, и чем больше будет нулей, тем быстрее будет найден результат. Если на первом «круге» не вышло найти оптимальное значение, то выйдет на втором, если же и тут решение не будет найдено, можно продолжать алгоритм столько раз, сколько нам потребуется. При этом, каждый раз начиная алгоритм с начала, предыдущие расчеты не сбрасываются, а значит, нулей будет еще больше, что в конечном итоге приведет к решению задачи.
Само же решение, по сути, уже дано изначально, мы лишь делаем необходимые операции для того, чтобы можно было это понять. Нас не интересует какие числа будут в ходе вычислений, все равно в конце мы найденное решение подставляем в исходную матрицу. Легче приводить все числа к нулю, и то, которое быстрее это сделает, и которое будет уникальным в строке-столбце и будет являться если не разгадкой, то направлением к этой же разгадке.
Потому что каждый шаг алгоритма двигает нас к тому, чтобы получить нули, и чем больше будет нулей, тем быстрее будет найден результат. Если на первом «круге» не вышло найти оптимальное значение, то выйдет на втором, если же и тут решение не будет найдено, можно продолжать алгоритм столько раз, сколько нам потребуется. При этом, каждый раз начиная алгоритм с начала, предыдущие расчеты не сбрасываются, а значит, нулей будет еще больше, что в конечном итоге приведет к решению задачи.
Само же решение, по сути, уже дано изначально, мы лишь делаем необходимые операции для того, чтобы можно было это понять. Нас не интересует какие числа будут в ходе вычислений, все равно в конце мы найденное решение подставляем в исходную матрицу. Легче приводить все числа к нулю, и то, которое быстрее это сделает, и которое будет уникальным в строке-столбце и будет являться если не разгадкой, то направлением к этой же разгадке.
В интернете(даже на той же Википедии) можно найти доскональное доказательство через графы, но оно не самое простое :)
Объяснение автора кажется мне слишком сумбурным, попробую прояснить вопрос.
1. Добавление константы к элементам одной строки (или столбца) матрицы не меняет оптимальное назначение. Т.е. в результате подобных преобразований суммарная оценка может измениться, но кого куда оптимальнее назначать — нет.
2. После спуска до 0 (так называется операция, выполняемая на первом шаге) мы имеем неотрицательную матрицу. Очевидно, что минимальным будет назначение с нулевыми оценками.
3. «Вычёркивание» нулей минимальным количеством линий — это на самом деле построение максимального паросочетания в двудольном графе, порождённом нулевыми элементами. Найти его можно с помощью алгоритма Куна. Он, помимо элементов максимального паросочетания, возвращает и вершинное покрытие графа (ещё его называют контрольным или контролирующим множеством) — т.е. те самые «вычёркивающие» линии.
4. В том случае, если с имеющимся набором нулевых элементов полное назначение не получается, матрица перестраивается. Разноцветные области из статьи, где элементы увеличиваются\уменьшаются\не меняются — это уже оптимизированная версия того, что происходит на самом деле. Но в такой версии не очевидно, почему подобные изменения матрицы не изменят решение задачи.
А происходит следующее. Мы определяем минимальный «невычеркнутый» элемент и вычитаем его из каждой «невычеркнутой» строки (поэлементно). Это гарантирует нам появление как минимум одного нового нуля, но есть проблема — элементы на пересечении «невычеркнутых» строк и «вычеркнутых» столбцов могут стать отрицательными. Для того, чтобы этого избежать, к «вычеркнутым» столбцам тот же самый минимальный элемент мы добавляем.
Пусть матрица была n*n, i — количество «вычеркнутых» строк, j — количество «вычеркнутых» столбцов. Очевидно, что i + j < n, т.к. иначе существовало бы полное назначение на нулевых элементах и задача была бы решена.
Пусть m — мининимальный элемент, который мы вычитаем. m > 0, т.к. матрица не отрицательна, а все нули «вычеркнуты» (минимальный элемент мы искали среди «невычеркнутых» элементов матрицы).
Мы вычитаем (n — i)*m и добавляем j*m. Добавление j*m — это вычитание -j*m. Таким образом, совокупно мы вычитаем (n — i — j)*m > 0.
Подобная модификация матрицы уменьшает целевую функцию на заведомо положительное число. Целевая функция ограничена снизу — значит, через конечное число шагов минимум будет достигнут.
1. Добавление константы к элементам одной строки (или столбца) матрицы не меняет оптимальное назначение. Т.е. в результате подобных преобразований суммарная оценка может измениться, но кого куда оптимальнее назначать — нет.
2. После спуска до 0 (так называется операция, выполняемая на первом шаге) мы имеем неотрицательную матрицу. Очевидно, что минимальным будет назначение с нулевыми оценками.
3. «Вычёркивание» нулей минимальным количеством линий — это на самом деле построение максимального паросочетания в двудольном графе, порождённом нулевыми элементами. Найти его можно с помощью алгоритма Куна. Он, помимо элементов максимального паросочетания, возвращает и вершинное покрытие графа (ещё его называют контрольным или контролирующим множеством) — т.е. те самые «вычёркивающие» линии.
4. В том случае, если с имеющимся набором нулевых элементов полное назначение не получается, матрица перестраивается. Разноцветные области из статьи, где элементы увеличиваются\уменьшаются\не меняются — это уже оптимизированная версия того, что происходит на самом деле. Но в такой версии не очевидно, почему подобные изменения матрицы не изменят решение задачи.
А происходит следующее. Мы определяем минимальный «невычеркнутый» элемент и вычитаем его из каждой «невычеркнутой» строки (поэлементно). Это гарантирует нам появление как минимум одного нового нуля, но есть проблема — элементы на пересечении «невычеркнутых» строк и «вычеркнутых» столбцов могут стать отрицательными. Для того, чтобы этого избежать, к «вычеркнутым» столбцам тот же самый минимальный элемент мы добавляем.
Пусть матрица была n*n, i — количество «вычеркнутых» строк, j — количество «вычеркнутых» столбцов. Очевидно, что i + j < n, т.к. иначе существовало бы полное назначение на нулевых элементах и задача была бы решена.
Пусть m — мининимальный элемент, который мы вычитаем. m > 0, т.к. матрица не отрицательна, а все нули «вычеркнуты» (минимальный элемент мы искали среди «невычеркнутых» элементов матрицы).
Мы вычитаем (n — i)*m и добавляем j*m. Добавление j*m — это вычитание -j*m. Таким образом, совокупно мы вычитаем (n — i — j)*m > 0.
Подобная модификация матрицы уменьшает целевую функцию на заведомо положительное число. Целевая функция ограничена снизу — значит, через конечное число шагов минимум будет достигнут.
Читал я и терзали меня смутные сомнения, что этот Венгерский алгоритм я уже где-то встречал.
Ба!!! Дык, он же применяется при нахождении приблизительного решения задачи коммивояжера!
Правда, толкового описания, почему этот метод работает для нахождения гамильтоновых циклов в Интернете не найти.
Вот и возникают вопросы:
1. Какая связь между задачей коммивояжера и задачей о назначениях?
2. Если решение задачи коммивояжера венгерским методом находится только приблизительное, то почему решение задачи о назначениях будет найдено точное?
Ба!!! Дык, он же применяется при нахождении приблизительного решения задачи коммивояжера!
Правда, толкового описания, почему этот метод работает для нахождения гамильтоновых циклов в Интернете не найти.
Вот и возникают вопросы:
1. Какая связь между задачей коммивояжера и задачей о назначениях?
2. Если решение задачи коммивояжера венгерским методом находится только приблизительное, то почему решение задачи о назначениях будет найдено точное?
1. Исходный вид матрицы который используется в задачах Коммивояжера практически идентичен тому, который используется в задачах о назначениях. Суть даже одна:
2. Вот на этот вопрос затрудняюсь ответить. Могу конечно предположить, что задача Коммивояжера тем точна, что во время расчетов мы размер матрицы постепенно уменьшаем, и те значения которые уже найдены мы во внимания не берем. Лишь в конце все складываем в единую картину.
А в Венгерском методе мы решение получаем сразу, и пока задача не решена полностью, мы не можем быть уверены в конечном результате. К примеру, если 4 из 5 нулей найдены, а последний нет, это не будет означать что на новом шаге все «уникальные» нули не изменят свой индекс.
- Если же в задачах о назначениях имена строк/столбцов матрицы содержат работы/работников, то в Коммивояжере и строки и столбцы содержат города (населенные пункты), а сама матрица заполняется либо расстояниями между городами, либо стоимостью.
- В задачах Коммивояжера матрица должна быть так же закрытого типа, и так же, чтобы были «уникальные» значения которые не повторяются в строках-столбце.
- Наверно, единственное отличие — что на главной диагонали матрицы задач Коммивояжера стоят бесконечности.
2. Вот на этот вопрос затрудняюсь ответить. Могу конечно предположить, что задача Коммивояжера тем точна, что во время расчетов мы размер матрицы постепенно уменьшаем, и те значения которые уже найдены мы во внимания не берем. Лишь в конце все складываем в единую картину.
А в Венгерском методе мы решение получаем сразу, и пока задача не решена полностью, мы не можем быть уверены в конечном результате. К примеру, если 4 из 5 нулей найдены, а последний нет, это не будет означать что на новом шаге все «уникальные» нули не изменят свой индекс.
Хорошей связи между задачей коммивояжера и задачей о назначениях нет… разве что если P=NP.
Наверно речь идет о Christofides algorithm. Есть два известных алгоритма приближенного решения задачи коммивояжера для графа, в котором веса ребер удовлетворяют неравенству треугольника
Простой: находим минимальное остовное дерево, проходим по нему и строим не очень сложным образом цикл. Если выполняется неравенство треугольника, то полученный цикл не более, чем в 2 раза хуже оптимального.
Сложный:
— Находим минимальное остовное дерево
— Находим на вершинах с нечетной степенью в найденном остовном дереве паросочетание наименьшего веса (здесь как раз решается задача о назначениях)
— Находим Эйлеров цикл и несложным образом превращаем его в гамильтонов.
Вуаля, оказывается, что такой алгоритм дает приближение, которое не более, чем в 1.5 хуже оптимального.
Подробнее можно посмотреть тут и тут.
Наверно речь идет о Christofides algorithm. Есть два известных алгоритма приближенного решения задачи коммивояжера для графа, в котором веса ребер удовлетворяют неравенству треугольника
Простой: находим минимальное остовное дерево, проходим по нему и строим не очень сложным образом цикл. Если выполняется неравенство треугольника, то полученный цикл не более, чем в 2 раза хуже оптимального.
Сложный:
— Находим минимальное остовное дерево
— Находим на вершинах с нечетной степенью в найденном остовном дереве паросочетание наименьшего веса (здесь как раз решается задача о назначениях)
— Находим Эйлеров цикл и несложным образом превращаем его в гамильтонов.
Вуаля, оказывается, что такой алгоритм дает приближение, которое не более, чем в 1.5 хуже оптимального.
Подробнее можно посмотреть тут и тут.
Нет… Алгоритм Кристофидеса — это модифицированный алгоритм Эйлера на основе построения минимального остовного дерева.
Он имеет самую лучшую верхнюю оценку для приблизительных методов за полиномиальное время, но существует немало других более простых методов, дающих очень неплохой результат, несмотря на худшую верхнюю оценку. Например, алгоритм Карга-Томпсона (эвристика ближайшей точки — не путать с жадным алгоритмом ближайшего соседа).
Временная сложность АКТ — O(n^3), но степень приближения — достаточно хорошая (хотя в худших случаях и уступает алгоритмам на основе остовного дерева).
Я имел в виду, что Венгерский метод (вычеркивания столбцов и строк) может применяться не только для решения задачи о назначениях, но и для приблизительного решения задачи коммивояжера. Встречал такое утверждение на просторах Интернета.
https://math.semestr.ru/kom/index.php
https://math.semestr.ru/kom/nazn.php
Он имеет самую лучшую верхнюю оценку для приблизительных методов за полиномиальное время, но существует немало других более простых методов, дающих очень неплохой результат, несмотря на худшую верхнюю оценку. Например, алгоритм Карга-Томпсона (эвристика ближайшей точки — не путать с жадным алгоритмом ближайшего соседа).
Временная сложность АКТ — O(n^3), но степень приближения — достаточно хорошая (хотя в худших случаях и уступает алгоритмам на основе остовного дерева).
Я имел в виду, что Венгерский метод (вычеркивания столбцов и строк) может применяться не только для решения задачи о назначениях, но и для приблизительного решения задачи коммивояжера. Встречал такое утверждение на просторах Интернета.
https://math.semestr.ru/kom/index.php
https://math.semestr.ru/kom/nazn.php
Наверно, единственное отличие — что на главной диагонали матрицы задач Коммивояжера стоят бесконечности.
Не только…
Задача коммивояжера (поиск гамильтонова цикла) задается на полносвязном графе (пусть даже веса некоторых ребер равны бесконечности), а задача о назначениях — на двудольном.
Т.е., в процессе конференции Иван, конечно, может соединиться с Марией, а Петр с Александрой и Ольгой. Но вот соединять настройку звука с организацией кофе-брейков будет как-то не совсем правильно.
Ну и в задаче коммивояжера мы получаем в результате замкнутый гамильтонов цикл, а в задаче о назначениях — набор несвязных ребер, объединяющий вершины разных долей — работников и работ.
+ в карму. Интересный алгоритм. Отличное объяснение, но не очень понятно, почему результат правильный.
Спасибо большое! :)
Непонятно почему результат получился именно таким?
Алгоритм считается решенным тогда, когда задействованы все строки и столбцы (ну или как я везде упоминал, найдены уникальные нули).
Быстро набросал картинки для понимания.
В этом случае — задача не решена еще, необходимо либо дальше продолжать алгоритм, либо по второму кругу считать:
А в этом случае — решение задачи найдено:
Всегда в алгоритме все внимание уделяется нулям. Если бы в первом случае вместо шести был ноль, тогда задача тоже считалась бы решенной. Потом мы индексы нулей (во втором случае где решение задачи найдено — это [2;1],[5;3],[1;4],[4;5];[3;2]) подставляем в самую-самую исходную матрицу, которая у нас была дана изначально с условием задачи. Визуально видим какой исполнитель делает какую работу, и с помощью индексов считаем оптимальное значение.
(Упс, помарочка вышла. Везде где писал «шестая строка»/«шестой столбец» конечно же имел ввиду «пятая строка»/«пятый столбец»)
Если помог разобраться — это супер! Если же нет, с радостью подскажу неясные моменты.
Непонятно почему результат получился именно таким?
Алгоритм считается решенным тогда, когда задействованы все строки и столбцы (ну или как я везде упоминал, найдены уникальные нули).
Быстро набросал картинки для понимания.
В этом случае — задача не решена еще, необходимо либо дальше продолжать алгоритм, либо по второму кругу считать:
А в этом случае — решение задачи найдено:
Всегда в алгоритме все внимание уделяется нулям. Если бы в первом случае вместо шести был ноль, тогда задача тоже считалась бы решенной. Потом мы индексы нулей (во втором случае где решение задачи найдено — это [2;1],[5;3],[1;4],[4;5];[3;2]) подставляем в самую-самую исходную матрицу, которая у нас была дана изначально с условием задачи. Визуально видим какой исполнитель делает какую работу, и с помощью индексов считаем оптимальное значение.
(Упс, помарочка вышла. Везде где писал «шестая строка»/«шестой столбец» конечно же имел ввиду «пятая строка»/«пятый столбец»)
Если помог разобраться — это супер! Если же нет, с радостью подскажу неясные моменты.
Если же нет, с радостью подскажу неясные моменты
Как-то не ясно, зачем 2 раза подряд проводить редукцию по строкам: один раз в самом начале, а второй раз сразу же после нее.
Понятно же, что последует именно это:
Т.к. все минимальные элементы – нулевые, то матрица не изменилась.
Т.е. вторая редукция при поиске максимума явно лишняя.
При поиске максимума вторая редукция по строкам, по сути, не нужна. Хоть и алгоритм подразумевает ее присутствие, но на деле ею можно пренебречь.
В статью я ее добавил чтобы можно было ссылаться на случай, если кто-либо будет решать задачу на минимум, ну и чтобы алгоритм был, так сказать, полноценным.
В статью я ее добавил чтобы можно было ссылаться на случай, если кто-либо будет решать задачу на минимум, ну и чтобы алгоритм был, так сказать, полноценным.
А нельзя ли решать эту задачу через теорию сравнительных преимуществ?
Попарные относительные преимущества относительно друг друга или такое решение неявно и сведется к данному алгоритму?
Попарные относительные преимущества относительно друг друга или такое решение неявно и сведется к данному алгоритму?
Правда, не интересовался теорией сравнительных преимуществ, поэтому не смогу ответить на Ваш вопрос
Сомнительно, т.к. попарные преимущества не учитывают остальные альтернативы. К примеру, некий Вася оказался чуть лучше Пети и мы отдали работу Васе. А потом выяснилось, что во всех остальных работах Петя — просто катастрофа, и оптимальным было бы назначить его вместо Васи, хотя тот и лучше справился бы.
Вообще, стоит ли изобретать велосипед? Это классическая оптимизационная задача, она хорошо изучена. Является частным случаем задачи линейного программирования, так что можно решать хоть симплекс-методом. Но когда есть простой алгоритм, работающий за O(n^3), им и стоит пользоваться. Особых надежд на что-то более быстрое практически нет.
Единственная проблема венгерского алгоритма — он не интуитивен. Совершаемые действия (пересчёт матрицы стоимости, уменьшающий значение целевой функции) математически обоснованны, но не имеют смысла в рамках предметной области.
Есть другой алгоритм для задачи о назначениях, аукционный. Как можно понять из названия, происходит что-то вроде аукционных торгов за лоты — распределяемые работы.
Работы рассматриваются по порядку. Для каждой определяется множество претендентов — людей, для которых эта работа является наиболее предпочтительной. Для каждого из претендентов вычисляется надбавка — разность между стоимостью данной работы и стоимостью второй по предпочтительности работы для этого претендента. В итоге работу получает претендент с наибольшей надбавкой.
Это несколько упрощённая версия алгоритма, она иногда может зацикливаться. Поэтому в полноценном алгоритме надбавки вычисляются с точностью до ε, удовлетворяющего некоторому условию.
Вообще, стоит ли изобретать велосипед? Это классическая оптимизационная задача, она хорошо изучена. Является частным случаем задачи линейного программирования, так что можно решать хоть симплекс-методом. Но когда есть простой алгоритм, работающий за O(n^3), им и стоит пользоваться. Особых надежд на что-то более быстрое практически нет.
Единственная проблема венгерского алгоритма — он не интуитивен. Совершаемые действия (пересчёт матрицы стоимости, уменьшающий значение целевой функции) математически обоснованны, но не имеют смысла в рамках предметной области.
Есть другой алгоритм для задачи о назначениях, аукционный. Как можно понять из названия, происходит что-то вроде аукционных торгов за лоты — распределяемые работы.
Работы рассматриваются по порядку. Для каждой определяется множество претендентов — людей, для которых эта работа является наиболее предпочтительной. Для каждого из претендентов вычисляется надбавка — разность между стоимостью данной работы и стоимостью второй по предпочтительности работы для этого претендента. В итоге работу получает претендент с наибольшей надбавкой.
Это несколько упрощённая версия алгоритма, она иногда может зацикливаться. Поэтому в полноценном алгоритме надбавки вычисляются с точностью до ε, удовлетворяющего некоторому условию.
Особых надежд на что-то более быстрое практически нет.
Вроде бы есть. Вообще задача о назначениях часто в научных статьях называется «задачей о паросочетании минимальной стоимости» (minimum cost bipartite matching problem), обычно рассматривается как подкласс задачи о потоке минимальной стоимости (minimum cost flow problem). По этим названиям можно поискать и найти кучу всего, что напридумывали.
Беглый поиск в goolge scholar выдал вот эту статью, судя по абстракту там лучше, чем n^3, но асимптотика содержит величины стоимостей. Скорее всего это не первый подобный алгоритм. Работают ли они быстрее на практике — другой вопрос. Опять же, кажется, что отдельно с задачей о назначениях особо не заморачиваются, штурмуют как минимум потоки.
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Венгерский алгоритм, или о том, как математика помогает в распределении назначений