Я реализовал венгерский алгоритм, решение проблемы назначения, как описано в этой статье , но он не работает на нескольких процентах матриц случайных затрат.
Я потратил несколько недель на его отладку (я начал, когда задал этот вопрос , хотя и не полный рабочий день). Я взял матрицы случайных затрат, для которых алгоритм не работает, и выполнил алгоритм со старой доброй ручкой и бумагой, и сравнил это с моей реализацией, чтобы увидеть, что пошло не так. Это привело меня к нескольким ошибкам, которые я сейчас исправил, но я столкнулся с примером, для которого я не могу найти правильное решение, когда решаю его вручную. Для всех, кто заинтересован: стоимость матрицы этого примера равна {{0,6,4,3},{3,2,1,2},{0,7,6,4},{3,8,5,3}}, для которой правильное решение имеет сумму 9=4+2+0+3 (в этом порядке). В этом примере, в конечном итоге, есть совпадение не на подграфе равенства, и я думаю, что это невозможно, что указывает на то, что что-то не так.
Либо я не совсем понимаю решение, которое является приемлемым вариантом, либо чрезвычайно незначительная ошибка в представленном решении, которую я подробно опишу ниже.
Я понимаю, что должен ввести некоторую терминологию, но, поскольку это подробный вопрос, я не собираюсь объяснять все концепции во всех деталях, поскольку любой, кто нуждается в этом объяснении, вероятно, не сможет ответить на мой вопрос в любом случае.
- Входные данные задачи представляют собой взвешенный полный двудольный граф с
n узлами на каждом разбиении.
- Представленный метод указывает на
n расширение путей.
- Расширяющий путь - это альтернативный путь, начинающийся и заканчивающийся в несопоставленных узлах.
- Чередующийся путь - это путь, чередующийся между несоответствующими ребрами в подграфе равенства.
- Эти чередующиеся пути растут в ширину, останавливаясь только когда:
- Найден дополнительный путь или
- альтернативные пути не могут быть расширены дальше.
- И важный факт для возможной ошибки: алгоритм запоминает, с какими узлами столкнулись чередующиеся пути, что влияет на алгоритм в части, не относящейся к этому вопросу.
Когда расширенный путь найден, представленный метод говорит прекратить расти чередующиеся пути. Я считаю, что это неправильно. Я думаю, что все альтернативные пути должны быть увеличены до стоимости найденного расширенного пути. Обратите внимание, что чередующиеся пути сначала растут в ширину, так что это только увеличивает пути, стоимость которых может быть связана с найденным путем. Это небольшое изменение может привести к тому, что некоторые узлы будут помечены как «посещенные альтернативным путем», которые в противном случае не были бы отмечены, что в дальнейшем повлияет на алгоритм.
Актуальный вопрос:
Должен ли я рассмотреть альтернативные пути с затратами, равными затратам на расширенный путь (и начиная с того же узла), который исследуется? Это противоречит представленному методу, который говорит об остановке, как только будет найден расширенный путь, независимо от каких-либо связей затрат с другими путями.