Поиск комбинации (оптимальный алгоритм)

← →
tButton © (2012-02-03 02:25) [0]

Дали «на слабо» задачку
Есть 88 целых чисел, которые в сумме дают некоторое число, известно, что некоторые из этих чисел лишние, сумма нужных чисел также известна.
Задача: отсеять лишние числа, найти все возможные комбинации.

К решению задачи подошёл «в лоб», т.е. последовательно перебираю варианты 88-битной маски и суммирую по ней элементы, сверяя с эталонным значением.

Однако, для выполнения полного перебора придётся проверить 2^88 комбинаций, скорость перебора около 40000 комбинаций в секунду, что означает, что перебор для 40 исходных чисел займёт приблизительно 318 дней. Срок абсолюно неприемлемый, для 88 исходных чисел время перебора сравнимо со временем существования солнечной системы =)

Потому вопрос: Есть ли алгоритмы оптимизации этой задачи?

← →
tButton © (2012-02-03 02:28) [1]

а, не ~245 * 10^12 лет =)

← →
Германн © (2012-02-03 03:04) [2]

А почему не в "Прочее" задал вопрос?

← →
MBo © (2012-02-03 05:33) [3]

Задача о наборе суммы (subset sum), решается динамическим программированием.

← →
tButton © (2012-02-03 11:32) [4]

[2]
Долго метался сюда или в «Прочее», но поскольку в прочем, слишком много отвлечённых от программирования тем решил всё-таки сюда кинуть)

[3]
Но кроме полного перебора никак?

Вообще насколько я понял, поставленую задачу из какого-то счёта выкинули какие-то позиции, ИЧСХ никто не знает сколько и какие =) известны только старая и новая суммы, задача — найти выкинутые позиции. Сейчас сужаем область поиска. Ну и в рукаве ещё два варианта:
1) Инверсная маска (начинаем с суммы всех позиций идём к сумме ниодной)
2) Рэндомная маска, что называется пальцем в небо.

← →
AV © (2012-02-03 11:39) [5]

т.е. задача такая

есть известные, наперед заданные числа
78, 2, 1, 23, 56, .. ,99 - всего 88 чисел.

Задается число S
и требуется выкинуть числа так, что бы сумма оставшихся была = S.

Все правильно?

← →
AV © (2012-02-03 11:48) [6]

> и требуется выкинуть числа так, что бы сумма оставшихся
> была = S.

разными способами

← →
Sha © (2012-02-03 12:06) [7]

> найти все возможные комбинации

Может достаточно найти количество?
У тебя не хватит места для вывода всех комбинаций.

← →
tButton © (2012-02-03 14:46) [8]

[5]
да

[6]
да =)

[7]
для всех возможных не хватит, для всех подходящих должно хватить

сумма по 88 позициям немного больше двух миллионов, нужно выбрать те, которые дадут миллион девятьсот с копейками, допустимое отклонение не более 0,5 (погрешность округления) на позицию т.е. в сумме не более 44-45

размер позиции колеблется от нескольких тысяч, до нескольких сот тысяч, но все меньше разницы =) так что отсеять можно только перерыв кучу документов, чем сейчас и занят озадачивший меня товарищ =)

← →
MBo © (2012-02-03 14:53) [9]

При таком раскладе при использовании ДП будет раз в 20 быстрее решить обратную задачу - о наборе лишней суммы (которая в пределах 100 тыс). Впрочем, и прямая задача ДП решается за секунды (если не считать все комбинации)

← →
tButton © (2012-02-03 15:25) [10]

[9]
в гугле ДП упоминается почему-то только в виде рекурсий, в вики вроде бы что-то нашёл, но пока не разбирался, В целом ход ваших мыслей мне нравится =)
для набора лишней суммы максимальное количество слагаемых меньше, что резко уменьшает количество вариантов. За наводку большое спасибо, буду копать =)

>что резко уменьшает количество вариантов
Эээ... Каждому полезному варианту соответствует один набор лишних.

учитывая что пригодны варианты сходящиеся с точностью до 0.01%, а также отсечение бесперспективных направлений поиска не так уж и много )

Сто лет назад решал похожую задачу по определению оптимального набора записей на дорожки кассеты определенной длительности.
Был сильно удивлен результатом. Оказалось, что почти для любой длины дорожки (с шагом в секунду) существует набор записей с точно такой суммарной длительностью. Причем длительность исходных записей можно было менять (почти) как угодно, на результате это (почти) не сказывалось.

← →
Alex_C (2012-02-04 17:20) [14]

> Дали «на слабо» задачку

Не понятно почему ты эту задачу поставил здесь - это чисто математическая задача. Типа теоремы Ферма - ее надо на форумах математиков задавать. К программированию это мало относится.

Теперь конкретно по задаче:

> К решению задачи подошёл «в лоб»,

Ты сам ответил на свой вопрос: т.к. к условиям ОБЩЕЙ задачи не предъявляется никаких условий, то решить ее в ОБЩЕМ виде - нельзя. Опять же пример теоремы Ферма - в частных случаях ее решили очень быстро. Проблема была доказать общий случай. :)

Поиск комбинации (оптимальный алгоритм) Найти похожие ветки