Задачка
а) ∑|a_i - b_i|→min , i = 0,..,N-1
б) ∑|a_i - b_i|^2→min, i = 0,..,N-1
Интересны полиномиальные по N решения.
Как вариант решения - что-то типа сортировки выбором: для каждого элемента B_i находить элемент A_j, который отличается от него меньше всего, и размещать B_i на j-й позиции. Очевидно, сложность алгоритма имеет порядок O(N^2).
Если я правильно понял, речь идет о жадном алгоритме. Увы, он не всегда работает. Пример:
А={0, 1}
B={0.3, -1}
Жадный алгоритм в таком случае не будет переставлять элементы массивов (Ближайший к A[0]=0 элемент действительно B[0]=0.3). В таком случае ∑=2.3. Оптимальным же является решение A={1,0}, B={0.3,-1}. Тут ∑=1.7
Полный перебор имеет экспоненциальную сложность - N! - количество перестановок на множестве из N элементов.
Если построить множество всевозможных разностей и представить их в виде матрицы (C[j] = |A - B[j]|) то задача получается эквивалентной выбору N элементов с минимальной суммой не лежащих в одном столбце/строке. Как это предлагается сделать за N^2?
...
б) ∑|a_i - b_i|^2→min, i = 0,..,N-1
На счёт первой задачи не знаю, а тут вроде бы есть зацепки, хоть и не очень красивые.
∑|a_i - b_i|^2 = ∑a_i^2 + ∑b_i^2 - 2*∑a_i*b_i
то есть надо найти ∑a_i*b_i максимальное.
Если бы все элементы были положительны, то можно было бы просто отсортировать 2 массива по возрастанию, что дало бы наибольшую сумму. А так придётся выделять 3 диапазона в массивах: наибольшие положительные пары, отсортированные по возрастанию, наименьшие отрицательные пары, так же отсортированные, и остатки (пары с разными знаками), отсортированные в разные стороны. Можно вначале отсортировать массивы, а потом из середины достать пары с противоположными знаками и пересортировать.
Как-то так. Вроде бы не намного сложнее, чем несколько сортировок. Но, правда, я мешаю оба массива.
Достаточно найти минимальный элемент в обоих массивах и если он меньше нуля то увеличить все A и B на него. На сумму это не повлияет.
Почему не повлияет? На произведение же влияет:
(a + t) * (b + t) = a*b + a*t + b*t + t * t;
то есть ∑a_i*b_i изменится. Но добавку можно учесть.
Но если так, то можно вообще тупо отсортировать 2 массива по возрастанию, так? Или я уже не соображаю под вечер...
(a + t) * (b + t) = a*b + a*t + b*t + t * t;
то есть ∑a_i*b_i изменится. Но добавку можно учесть.
Я про сумму из формулировки: ∑|a_i - b_i|^2 = ∑|(a_i +T) - (b_i + T)|^2→min
Это - да. Но боюсь, что массивы будут не совсем верно отсортированы, если в них будет не одинаковое количество положительных и отрицательных элементов. Но пока это интуитивное утверждение. Возможно, ошибаюсь.
Kogrom, hellcor говорит о том, что если добавить минимальный отрицательный элемент, то ВСЕ элементы станут неотрицательными, и тогда спокойно можно сортировать по возрастанию / убыванию.
И без прибавления можно сортировать. В чём проблема?
Но есть такая штука: если перемножаем числа с одинаковыми знаками, то произведение будет положительным, если с разными - то отрицательным. А для максимальной суммы произведений надо подобрать наибольшие положительные произведения и наименьшие отрицательные. Вот я думаю, что с наименьшими отрицательными будет проблема, если "спокойно сортировать".
Но есть такая штука: если перемножаем числа с одинаковыми знаками, то произведение будет положительным, если с разными - то отрицательным. А для максимальной суммы произведений надо подобрать наибольшие положительные произведения и наименьшие отрицательные. Вот я думаю, что с наименьшими отрицательными будет проблема, если "спокойно сортировать".
Речь о том, что если прибавить некую величину T ко всем элементам обоих массивов, то сумма не изменится, а проблема, о которой вы говорите, пропадет, все величины станут неотрицательными.
Решил проверить на примере:
def get_square_sum(a, b):
return sum((a_i-b_i)**2 for a_i, b_i in zip(a, b))
a = [-1.0, -2.5, -3.0, 0.3, 0.9, 1.5, 2.0, 3.5]
b = [-1.5, -2.0, -3.5, -0.4, -0.8, 1.0, 2.5, 3.0]
random.shuffle(a)
random.shuffle(b)
print get_square_sum(a, b)
a.sort()
b.sort()
print "quick sum:", get_square_sum(a, b)
import itertools
slow = min(get_square_sum(c, b) for c in itertools.permutations(a, len(a)))
print "slow sum:", slow
Тут проверил с сортировкой и с тупым перебором. Ответы совпали. В примере вышло, что достаточно тупой сортировки: никаких добавок или дополнительных сортировок не потребовалось.