Форум: "Основная";
Текущий архив: 2014.09.28;
Скачать: [xml.tar.bz2];
ВнизПоиск комбинации (оптимальный алгоритм) Найти похожие ветки
← →
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]
в гугле ДП упоминается почему-то только в виде рекурсий, в вики вроде бы что-то нашёл, но пока не разбирался, В целом ход ваших мыслей мне нравится =)
для набора лишней суммы максимальное количество слагаемых меньше, что резко уменьшает количество вариантов. За наводку большое спасибо, буду копать =)
← →
MBo © (2012-02-03 16:17) [11]>что резко уменьшает количество вариантов
Эээ... Каждому полезному варианту соответствует один набор лишних.
← →
tButton © (2012-02-03 16:22) [12]учитывая что пригодны варианты сходящиеся с точностью до 0.01%, а также отсечение бесперспективных направлений поиска не так уж и много )
← →
Sha © (2012-02-03 22:19) [13]Сто лет назад решал похожую задачу по определению оптимального набора записей на дорожки кассеты определенной длительности.
Был сильно удивлен результатом. Оказалось, что почти для любой длины дорожки (с шагом в секунду) существует набор записей с точно такой суммарной длительностью. Причем длительность исходных записей можно было менять (почти) как угодно, на результате это (почти) не сказывалось.
← →
Alex_C (2012-02-04 17:20) [14]
> Дали «на слабо» задачку
Не понятно почему ты эту задачу поставил здесь - это чисто математическая задача. Типа теоремы Ферма - ее надо на форумах математиков задавать. К программированию это мало относится.
Теперь конкретно по задаче:
> К решению задачи подошёл «в лоб»,
Ты сам ответил на свой вопрос: т.к. к условиям ОБЩЕЙ задачи не предъявляется никаких условий, то решить ее в ОБЩЕМ виде - нельзя. Опять же пример теоремы Ферма - в частных случаях ее решили очень быстро. Проблема была доказать общий случай. :)
Страницы: 1 вся ветка
Форум: "Основная";
Текущий архив: 2014.09.28;
Скачать: [xml.tar.bz2];
Память: 0.48 MB
Время: 0.002 c