Венгерский алгоритм, соответствующий одному набору

Question

Я ищу вариант венгерского алгоритма (я думаю), который соединит N людей с собой, исключая самопары и обратные пары, где N четно.

Например, учитывая N₀ - N₆ и матрицу C затрат для каждой пары, как я могу получить набор из 3 пар с наименьшей стоимостью?

C = [ [ - 5 6 1 9 4 ]
      [ 5 - 4 8 6 2 ]
      [ 6 4 - 3 7 6 ]
      [ 1 8 3 - 8 9 ]
      [ 9 6 7 8 - 5 ]
      [ 4 2 6 9 5 - ] ]

В этом примере результирующие пары будут:

N₀, N₃
N₁, N₄
N₂, N₅

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

Есть ли вариант венгерского, который работает на неквадратной матрице?

Или есть другой алгоритм, который решает эту проблему?

Answer 1

Увеличение значений нижней половины может привести к неверному решению. Вы можете видеть это, поскольку угловые координаты (в вашем примере с координатами 0,1 и 5,6) верхней половины всегда будут считаться находящимися в минимальных парах X, где X - размер матрицы.

Мое решение для поиска минимальных пар X

Взять стандартный венгерский алгоритм

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

1) Первый шаг стандартного алгоритма состоит в том, чтобы пройти каждую строку, а затем каждый столбец, уменьшив каждую строку и столбец в отдельности, так чтобы минимум каждой строки и столбца был равен нулю. Это без изменений.

Общий принцип этого решения заключается в отражении каждого последующего шага исходного алгоритма вокруг диагонали.

2) Следующим шагом алгоритма является выбор строк и столбцов, чтобы каждый ноль был включен в выбор, используя минимальное количество строк и столбцов. Мои изменения в алгоритме означают, что при выборе строки / столбца, также выберите столбец / строку, отраженную вокруг этой диагонали, но считайте его как одну строку или выбор столбца для всех целей, включая подсчет диагонали (которая будет пересечением этих зеркальные пары выбора строк / столбцов), которые выбираются только один раз.

3) Следующим шагом является проверка правильности решения, которое в стандартном алгоритме означает проверку того, равно ли количество выбранных строк и столбцов размеру матрицы, - в вашем примере, если выбрано шесть строк и столбцов, Однако для этого варианта при расчете времени окончания алгоритм обрабатывает каждую зеркальную пару строк / столбцов как один выбор строки или столбца. Если у вас есть правильное решение, тогда закончите алгоритм здесь.

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

Затем вернитесь к шагу 2 и повторяйте шаги 2-4, пока шаг 3 не покажет, что алгоритм завершен.

Это приведет к появлению пар зеркальных ответов (которые являются координатами - чтобы получить значение этих координат, относящихся к исходной матрице) - вы можете безопасно удалить половину каждой пары произвольно.

Чтобы изменить этот алгоритм, чтобы найти минимальное количество пар R, где R меньше размера матрицы, уменьшите точку остановки на шаге 3 до R. Это изменение необходимо для ответа на ваш вопрос.

Answer 2

Как @Niklas B, заявил, что вы решаете проблему взвешенного идеального соответствия, взгляните на это

вот часть документа, описывающая алгоритм Primal-dual для взвешенного идеального соответствия

Пожалуйста, прочитайте все и дайте мне знать, если это полезно для вас