Справочник функций

Ваш аккаунт

Войти через: 
Забыли пароль?
Регистрация
Информацию о новых материалах можно получать и без регистрации:

Последние темы форума

Показать новые сообщения »

Почтовая рассылка

Подписчиков: 6455
Последний выпуск: 19.06.2015

Задачка

69K
13 апреля 2011 года
hellcor
5 / / 13.04.2011
Даны 2 массива вещественный чисел - A и B длины N. Найти такую перестановку массива A, что

а) ∑|a_i - b_i|→min , i = 0,..,N-1
б) ∑|a_i - b_i|^2→min, i = 0,..,N-1

Интересны полиномиальные по N решения.
69K
13 апреля 2011 года
hellcor
5 / / 13.04.2011
Цитата: Alexander92

Как вариант решения - что-то типа сортировки выбором: для каждого элемента 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

263
13 апреля 2011 года
Alexander92
1.1K / / 04.08.2008
Я прошу прощения, я немного ошибся, поэтому и удалил свое сообщение. Сформулирую мысль окончательно и отпишусь. Я абсолютно согласен, что этот вариант не всегда работает.
263
13 апреля 2011 года
Alexander92
1.1K / / 04.08.2008
По большому счету, если речь идет о полиномиальной сложности, то почему вас не устраивает обычный перебор? Очевидно ведь, что в худшем случае он даст вам N^2 - N операций (это легко видно, если построить множество всех возможных разностей A - B[j], i = 0..N-1, j = 0..N-1).
69K
13 апреля 2011 года
hellcor
5 / / 13.04.2011
Цитата: Alexander92
По большому счету, если речь идет о полиномиальной сложности, то почему вас не устраивает обычный перебор? Очевидно ведь, что в худшем случае он даст вам N^2 - N операций (это легко видно, если построить множество всех возможных разностей A - B[j], i = 0..N-1, j = 0..N-1).


Полный перебор имеет экспоненциальную сложность - N! - количество перестановок на множестве из N элементов.

Если построить множество всевозможных разностей и представить их в виде матрицы (C[j] = |A - B[j]|) то задача получается эквивалентной выбору N элементов с минимальной суммой не лежащих в одном столбце/строке. Как это предлагается сделать за N^2?

71
13 апреля 2011 года
Kogrom
2.7K / / 02.02.2008
Цитата: hellcor
Даны 2 массива вещественный чисел - A и B длины N. Найти такую перестановку массива A, что
...
б) ∑|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 диапазона в массивах: наибольшие положительные пары, отсортированные по возрастанию, наименьшие отрицательные пары, так же отсортированные, и остатки (пары с разными знаками), отсортированные в разные стороны. Можно вначале отсортировать массивы, а потом из середины достать пары с противоположными знаками и пересортировать.

Как-то так. Вроде бы не намного сложнее, чем несколько сортировок. Но, правда, я мешаю оба массива.

69K
13 апреля 2011 года
hellcor
5 / / 13.04.2011
Цитата: Kogrom
А так придётся выделять 3 диапазона в массивах: наибольшие положительные пары, отсортированные по возрастанию, наименьшие отрицательные пары, так же отсортированные, и остатки (пары с разными знаками), отсортированные в разные стороны. Можно вначале отсортировать массивы, а потом из середины достать пары с противоположными знаками и пересортировать.



Достаточно найти минимальный элемент в обоих массивах и если он меньше нуля то увеличить все A и B на него. На сумму это не повлияет.

71
13 апреля 2011 года
Kogrom
2.7K / / 02.02.2008
Цитата: hellcor
Достаточно найти минимальный элемент в обоих массивах и если он меньше нуля то увеличить все A и B на него. На сумму это не повлияет.


Почему не повлияет? На произведение же влияет:
(a + t) * (b + t) = a*b + a*t + b*t + t * t;
то есть ∑a_i*b_i изменится. Но добавку можно учесть.

Но если так, то можно вообще тупо отсортировать 2 массива по возрастанию, так? Или я уже не соображаю под вечер...

69K
13 апреля 2011 года
hellcor
5 / / 13.04.2011
Цитата: Kogrom
Почему не повлияет? На произведение же влияет:
(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

71
13 апреля 2011 года
Kogrom
2.7K / / 02.02.2008
Цитата: hellcor
Я про сумму из формулировки: ∑|a_i - b_i|^2 = ∑|(a_i +T) - (b_i + T)|^2→min



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

263
13 апреля 2011 года
Alexander92
1.1K / / 04.08.2008
Прошу всех меня извинить за глюк с перебором, это меня перемкнуло.

Kogrom, hellcor говорит о том, что если добавить минимальный отрицательный элемент, то ВСЕ элементы станут неотрицательными, и тогда спокойно можно сортировать по возрастанию / убыванию.
71
13 апреля 2011 года
Kogrom
2.7K / / 02.02.2008
Цитата: Alexander92
Kogrom, hellcor говорит о том, что если добавить минимальный отрицательный элемент, то ВСЕ элементы станут неотрицательными, и тогда спокойно можно сортировать по возрастанию / убыванию.



И без прибавления можно сортировать. В чём проблема?

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

263
13 апреля 2011 года
Alexander92
1.1K / / 04.08.2008
Цитата: Kogrom
И без прибавления можно сортировать. В чём проблема?

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



Речь о том, что если прибавить некую величину T ко всем элементам обоих массивов, то сумма не изменится, а проблема, о которой вы говорите, пропадет, все величины станут неотрицательными.

71
14 апреля 2011 года
Kogrom
2.7K / / 02.02.2008
Цитата: Kogrom
Но если так, то можно вообще тупо отсортировать 2 массива по возрастанию, так? Или я уже не соображаю под вечер...


Решил проверить на примере:

Код:
import random

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

Тут проверил с сортировкой и с тупым перебором. Ответы совпали. В примере вышло, что достаточно тупой сортировки: никаких добавок или дополнительных сортировок не потребовалось.
71
14 апреля 2011 года
Kogrom
2.7K / / 02.02.2008
Ну и с первой задачкой опыт показал, что тупая сортировка выдает оптимальную сумму. Осталось теоретически выявить зависимость минимума суммы модулей от минимума суммы квадратов :)

Знаете кого-то, кто может ответить? Поделитесь с ним ссылкой.

Ваш ответ

Реклама на сайте | Обмен ссылками | Ссылки | Экспорт (RSS) | Контакты
Добавить статью | Добавить исходник | Добавить хостинг-провайдера | Добавить сайт в каталог