Легенда:
 новое сообщение
 закрытая нитка
 новое сообщение
 в закрытой нитке
 старое сообщение
|
- Напоминаю, что масса вопросов по функционированию форума снимается после прочтения его описания.
- Новичкам также крайне полезно ознакомиться с данным документом.
Я нашел способ сильно ускорить поиск :) 03.09.06 00:12 Число просмотров: 2393
Автор: leo <Леонид Юрьев> Статус: Elderman
Отредактировано 03.09.06 00:13 Количество правок: 1
|
Сегодня придумал способ скомбинировать два алгоритма, классический на списках и мой на коде Грея. Ускорение более чем в 100 раз :). На текущем тестовом примере из 32 чисел:
- классический алгоритм на списках = в глубоком отпаде, не хватает памяти;
- алгоритм на коде Грея = 39 сек + ~1 кбайт памяти;
- новый алгоритм = 0.2 сек + ~1 мбайт памяти;
Всё это для поиска ближайшей суммы (по модулю разности).
> А то, что то мне эта задачка уж сильно напомнила "1d bin
> packing problem" в народе еще именуюемую задачей
> оптимальной раскройки одномерного профиля.
Да, всё это варианты задачи "укладки ранца".
Но если придерживаться реалий, то нужно максимально не приближенное решение, и желательно несколько из top-списка.
[...]
> Время полиномиальное (насколько я понимаю O(N^2) для
> BFD-решения). Количество наборов не превышает 11/9 OPT + 4
> (где OPT - оптимальное количество)
>
> Тут http://en.wikipedia.org/wiki/Bin_packing говорят, что
> существуют приближенные методы, вычисляющие разбивку С
> ЛЮБОЙ заданной точностью (процентом от оптимального
> решения). В частности PTAS
> (http://en.wikipedia.org/wiki/Polynomial-time_approximation
> _scheme)
Сейчас гляну, может еще что-нибудь придумаю :)
|
- Задачка - leo 31.08.06 11:31 [2133]
|
|
|
подробно о проекте
Анализ криптографических сетевых...
