Алгоритм нахождения глобального минимального расстояния между парами предметов

Question

Элементы a-d должны быть в паре с элементами 0-3 таким образом, чтобы общее расстояние между всеми парами элементов было минимальным. Например, эта матрица может описывать расстояние между каждым элементом в первой группе и элементом в его группе партнеров:

[[2, 2, 4, 9],
 [4, 7, 1, 1],
 [3, 3, 8, 3],
 [6, 1, 7, 8]]

Предполагается, что это означает, что расстояние «a» -> «0» равно 2, «a» -> «1» равно 2, «a» -> «2» равно 4, «a» - > «3» равно 9. Из «b» -> «0» это 4 и так далее.

Существует ли алгоритм, который может сопоставить каждую букву с цифрой, чтобы общее расстояние было минимальным? E.g.:

[('a', 1), ('b', 3), ('c', 0), ('d', 2)]

Было бы легальным решением с общим расстоянием: 2 + 1 + 3 + 7 = 13. Грубое принуждение и проверка всех возможных комбинаций невозможны, так как в реальном мире есть группы с более чем четырьмя предметами.

Answer 1

Это классическая задача оптимизации для двудольных графов, которую можно решить с помощью Венгерского алгоритма / метода .

Answer 2

Эту проблему можно решить, рассматривая ее как пример взвешенной проблемы двойного соответствия.Идея состоит в том, чтобы рассматривать элементы ad и 0-3 как узлы на графике, где каждый буквенный узел связан с каждым пронумерованным узлом с ребром, вес которого определяется матрицей.Получив этот график, вы захотите найти набор ребер, соответствующих буквам и числам таким образом, чтобы каждый узел был связан только с одним ребром.Такой набор ребер называется сопоставлением , и поскольку вы хотите минимизировать расстояние, которое вы ищете для сопоставления с минимальными затратами.

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

Эту проблему стоит запомнить, поскольку она возникает во многих обстоятельствах.Каждый раз, когда вам нужно назначить элементы в одной группе для элементов в другой, проверьте, можете ли вы свести проблему к двустороннему сопоставлению.Если это так, вы почти наверняка нашли быстрое решение начальной проблемы.