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

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

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

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

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

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

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


distance algorithm mathematical-optimization minimum
person Björn Lindqvist    schedule 17.08.2011    source источник
comment
ИМХО, единственный способ - это грубая сила, как вы ее описываете. Есть ли какая-то связь между двумя наборами?   -  person Random Dev    schedule 17.08.2011
comment
Я не совсем понимаю, что такое правила. Вам разрешено выбирать только одно число из каждой строки и только одно число из каждого столбца, и вам нужно выбрать 4 числа, и вы хотите, чтобы сумма этих 4 чисел была минимизирована?   -  person robert king    schedule 17.08.2011
comment
Кенинг, мне было бы интересно узнать, почему вы не думаете, что есть решение. Я наткнулся на NP-сложную задачу?   -  person Björn Lindqvist    schedule 17.08.2011
comment
Я предполагаю, что часть, которую я не понимаю, заключается в том, чтобы сопоставить каждую букву с цифрой, чтобы общее расстояние решения было минимальным? конечно, вы бы просто сопоставили каждую букву с ближайшей цифрой? или вам разрешено использовать каждую цифру только один раз?   -  person robert king    schedule 17.08.2011
comment
Роберт Кинг, это точно. Думайте об этом, как когда вы стираете белье. Вы хотите подобрать к каждому из четырех правых носков наиболее похожий левый носок.   -  person Björn Lindqvist    schedule 17.08.2011
comment
Хорошо.. тогда то, что сказал yi_H :) получайте удовольствие   -  person robert king    schedule 17.08.2011

Ответы (2)


arrow_upward
9
arrow_downward

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

person Karoly Horvath    schedule 17.08.2011

arrow_upward
1
arrow_downward

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

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

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

person templatetypedef    schedule 17.08.2011