| Форумы
ЧАТ |
Орешник |
|
| Форумы -» | Основная («Начинающим»)/ Базы / WinAPI / Компоненты / Сети / Media / Игры / Corba и COM / KOL / FreePascal / .Net / Прочее / RSDN.ORG |
|
| ||
|
|
Новости |
Поиск |
FAQ |
Статьи |
Книги |
Новости VCL
| | Форумы ЧАТ |
Орешник |
|
| |||
| |||
| |||
« предыдущая ветвь | форум | следующая ветвь »
Поиск комбинации (оптимальный алгоритм)
tButton © (2012-02-03 02:25:00)Дали «на слабо» задачку
Есть 88 целых чисел, которые в сумме дают некоторое число, известно, что некоторые из этих чисел лишние, сумма нужных чисел также известна.
Задача: отсеять лишние числа, найти все возможные комбинации.
К решению задачи подошёл «в лоб», т.е. последовательно перебираю варианты 88-битной маски и суммирую по ней элементы, сверяя с эталонным значением.
Однако, для выполнения полного перебора придётся проверить 2^88 комбинаций, скорость перебора около 40000 комбинаций в секунду, что означает, что перебор для 40 исходных чисел займёт приблизительно 318 дней. Срок абсолюно неприемлемый, для 88 исходных чисел время перебора сравнимо со временем существования солнечной системы =)
Потому вопрос: Есть ли алгоритмы оптимизации этой задачи?
Alex_C (2012-02-04 17:20:00) [1]
> Дали «на слабо» задачку
Не понятно почему ты эту задачу поставил здесь - это чисто математическая задача. Типа теоремы Ферма - ее надо на форумах математиков задавать. К программированию это мало относится.
Теперь конкретно по задаче:
> К решению задачи подошёл «в лоб»,
Ты сам ответил на свой вопрос: т.к. к условиям ОБЩЕЙ задачи не предъявляется никаких условий, то решить ее в ОБЩЕМ виде - нельзя. Опять же пример теоремы Ферма - в частных случаях ее решили очень быстро. Проблема была доказать общий случай. :)
Sha (2012-02-03 22:19:00) [2]Сто лет назад решал похожую задачу по определению оптимального набора записей на дорожки кассеты определенной длительности.
Был сильно удивлен результатом. Оказалось, что почти для любой длины дорожки (с шагом в секунду) существует набор записей с точно такой суммарной длительностью. Причем длительность исходных записей можно было менять (почти) как угодно, на результате это (почти) не сказывалось.
tButton (2012-02-03 16:22:00) [3]учитывая что пригодны варианты сходящиеся с точностью до 0.01%, а также отсечение бесперспективных направлений поиска не так уж и много )
MBo (2012-02-03 16:17:00) [4]>что резко уменьшает количество вариантов
Эээ... Каждому полезному варианту соответствует один набор лишних.
tButton (2012-02-03 15:25:00) [5][9]
в гугле ДП упоминается почему-то только в виде рекурсий, в вики вроде бы что-то нашёл, но пока не разбирался, В целом ход ваших мыслей мне нравится =)
для набора лишней суммы максимальное количество слагаемых меньше, что резко уменьшает количество вариантов. За наводку большое спасибо, буду копать =)
MBo (2012-02-03 14:53:00) [6]При таком раскладе при использовании ДП будет раз в 20 быстрее решить обратную задачу - о наборе лишней суммы (которая в пределах 100 тыс). Впрочем, и прямая задача ДП решается за секунды (если не считать все комбинации)
tButton (2012-02-03 14:46:00) [7][5]
да
[6]
да =)
[7]
для всех возможных не хватит, для всех подходящих должно хватить
сумма по 88 позициям немного больше двух миллионов, нужно выбрать те, которые дадут миллион девятьсот с копейками, допустимое отклонение не более 0,5 (погрешность округления) на позицию т.е. в сумме не более 44-45
размер позиции колеблется от нескольких тысяч, до нескольких сот тысяч, но все меньше разницы =) так что отсеять можно только перерыв кучу документов, чем сейчас и занят озадачивший меня товарищ =)
Sha (2012-02-03 12:06:00) [8]> найти все возможные комбинации
Может достаточно найти количество?
У тебя не хватит места для вывода всех комбинаций.
AV (2012-02-03 11:48:00) [9]
> и требуется выкинуть числа так, что бы сумма оставшихся
> была = S.
разными способами
AV (2012-02-03 11:39:00) [10]т.е. задача такая
есть известные, наперед заданные числа
78, 2, 1, 23, 56, .. ,99 - всего 88 чисел.
Задается число S
и требуется выкинуть числа так, что бы сумма оставшихся была = S.
Все правильно?
tButton (2012-02-03 11:32:00) [11][2]
Долго метался сюда или в «Прочее», но поскольку в прочем, слишком много отвлечённых от программирования тем решил всё-таки сюда кинуть)
[3]
Но кроме полного перебора никак?
Вообще насколько я понял, поставленую задачу из какого-то счёта выкинули какие-то позиции, ИЧСХ никто не знает сколько и какие =) известны только старая и новая суммы, задача — найти выкинутые позиции. Сейчас сужаем область поиска. Ну и в рукаве ещё два варианта:
1) Инверсная маска (начинаем с суммы всех позиций идём к сумме ниодной)
2) Рэндомная маска, что называется пальцем в небо.
MBo (2012-02-03 05:33:00) [12]Задача о наборе суммы (subset sum), решается динамическим программированием.
Германн (2012-02-03 03:04:00) [13]А почему не в "Прочее" задал вопрос?
tButton (2012-02-03 02:28:00) [14]а, не ~245 * 10^12 лет =)
| |
