Измерение расстояния между двумя наборами, возможно, разного размера

У меня есть 2 набора целых чисел, A и B, не обязательно одинакового размера. Для моих нужд я беру расстояние между каждыми двумя элементами a и b (целые числа) равным всего abs(a-b).

Я определяю расстояние между двумя наборами следующим образом:

  1. Если множества имеют одинаковый размер, минимизируйте сумму расстояний всех пар [a,b] (a от A и b от B), минимизируя по всем возможным «парным разбиениям» (существует n! возможных разбиений).
  2. Если множества разного размера, скажем, A размера m и B размера n, где m ‹ n, то минимизируйте расстояние от (1) по всем подмножествам B размера m.

Мой вопрос в том, дает ли следующий алгоритм (просто интуитивное предположение) правильный ответ в соответствии с определением, написанным выше.

  • Построить матрицу D размера m X n с D(i,j) = abs(A(i)-B(j))
  • Найдите наименьший элемент D, накопите его и удалите строку и столбец этого элемента. Накопите следующую наименьшую запись и продолжайте накапливать, пока не будут удалены все строки и столбцы.

например, если A={0,1,4} и B={3,4}, то D будет (с элементами сверху и слева):

3 4

0 3 4

1 2 3

4 1 0

Расстояние равно 0 + 2 = 2, исходя из пары 4 с 4 и 3 с 1.


set distance algorithm
person Itamar Katz    schedule 14.12.2010    source источник

Ответы (4)


arrow_upward
5
arrow_downward

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

Чтобы решить эту проблему, вы можете использовать двудольное сопоставление минимального веса, которое требует времени O (n ^ 3).

Более того, вы можете достичь времени O(n^2) с дополнительной памятью O(n), используя простой алгоритм динамического программирования, приведенный ниже.

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

O(n^2) алгоритм динамического программирования:

if (size(B) > size(A))
  swap(A, B);
sort(A);
sort(B);
opt = array(size(B));
nopt = array(size(B));
for (i = 0; i < size(B); i++)
  opt[i] = abs(A[0] - B[i]);
for (i = 1; i < size(A); i++) {
  fill(nopt, infinity);
  for (j = 1; j < size(B); j++) {
    nopt[j] = min(nopt[j - 1], opt[j - 1] + abs(A[i] - B[j]));
  swap(opt, nopt);
}
return opt[size(B) - 1];

После каждой итерации i внешнего цикла for, описанного выше, opt[j] содержит оптимальное решение, соответствующее {A[0],..., A[i]} с использованием элементов {B[0],..., B[j]}.

Корректность этого алгоритма основана на том факте, что при любом оптимальном паросочетании, если a1 сопоставляется с b1, a2 сопоставляется с b2 и a1 ‹ a2, то b1 ‹= b2.

person jonderry    schedule 14.12.2010
comment
+1: приятно отметить, что проблема имеет структуру, отсутствующую в общем двудольном сопоставлении - person lijie; 15.12.2010
comment
Спасибо. Поскольку максимальный размер N в моем случае использования ограничен, я могу создать таблицу всех расстояний для всех возможных размеров между 0 и N и использовать ее во время выполнения (вместо того, чтобы вычислять ее во время выполнения). - person Itamar Katz; 15.12.2010
comment
В чем разница между двудольным сопоставлением минимального веса и проблемой назначения, упомянутой ниже @lijie? - person Itamar Katz; 15.12.2010
comment
насколько я знаю, они одинаковы (за исключением разве что терминологии). - person lijie; 15.12.2010
comment
Это два названия одной и той же проблемы. - person jonderry; 15.12.2010

arrow_upward
2
arrow_downward

Чтобы получить оптимум, решите задачу о назначениях на D.

Задача о назначениях находит идеальное паросочетание в двудольном графе, при котором общий вес ребра минимален, что идеально соответствует вашей задаче. Он есть и в П.

EDIT, чтобы объяснить, как проблема OP сопоставляется с заданием.

Для простоты объяснения расширите меньший набор специальными элементами e_k.

Пусть A — набор рабочих, а B — набор задач (содержимое — это просто метки).

Пусть стоимость будет расстоянием между элементами в A и B (т. е. записью D). Расстояние между e_k и чем угодно равно 0.

Затем мы хотим найти идеальное соответствие A и B (т. е. каждому работнику соответствует задача), чтобы затраты были минимальными. Это это задача о назначении.

person lijie    schedule 14.12.2010
comment
Я не могу понять отношение проблемы назначения к этому, не могли бы вы объяснить, чего хорошего можно достичь с помощью задачи назначения? Предлагаемый алгоритм OP выбирает идеальное паросочетание. если вы предполагаете, что A и B являются частями. Я предполагаю, что эта проблема NP, а если P, имеет сложный подход к динамическому программированию. - person Saeed Amiri; 14.12.2010
comment
Присваивание находит идеальное соответствие, при котором общий вес ребра минимален (а не любое идеальное соответствие). Другими словами, проблема OP также известна как задача о назначениях (которая имеет решение за полиномиальное время). - person lijie; 14.12.2010
comment
также, если проблема находится в P, она определенно находится и в NP (P является подмножеством NP). - person lijie; 14.12.2010
comment
Сначала я думал, что проблема присваивания заключается в поиске соответствия, но после того, как я увидел вики, я обнаружил, что ваша идея верна, но где я сказал, что P не находится в NP? а вы пытаетесь это сказать? по соглашению вместо NPC я сказал NP, это нормальное соглашение. - person Saeed Amiri; 14.12.2010
comment
вы не сказали, что P не входит в NP. Я неправильно понял. Я сказал, что это в P, и после этого вы сказали, что я думаю, что это проблема NP, и если... так что я был сбит с толку. - person lijie; 15.12.2010
comment
Поскольку мое общее расстояние представляет собой сумму расстояний, значит ли это, что моя задача соответствует задаче о линейном назначении? - person Itamar Katz; 15.12.2010
comment
Да, по сути, но решение jonderry лучше (потому что оно заточено под дополнительную структуру задачи) - person lijie; 15.12.2010

arrow_upward
1
arrow_downward

Нет. Это не лучший ответ, например: A: {3,7} и B:{0,4} вы выберете: {(3, 4),(0,7)} и расстояние равно 8, но вы должны выбрать {(3,0),(4,7)}, в этом случае расстояние равно 6.

person Saeed Amiri    schedule 14.12.2010

arrow_upward
0
arrow_downward

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

person MahlerFive    schedule 14.12.2010