Легенда:
 новое сообщение
 закрытая нитка
 новое сообщение
 в закрытой нитке
 старое сообщение
|
- Напоминаю, что масса вопросов по функционированию форума снимается после прочтения его описания.
- Новичкам также крайне полезно ознакомиться с данным документом.
Re: как код Грея тут прикручивается 05.09.06 12:48 Число просмотров: 2977
Автор: leo <Леонид Юрьев> Статус: Elderman
|
> Что-то я не совсем понял, как код Грея тут прикручивается,
> боюсь изобрести "велосипед", но уж точно не классический
> алгоритм, поскольку памяти тут не нужно.
Итерирование кодом Грея позволяет перебрать все комбинации, делая на каждом шаге одну операцию добавления или вычитания одного слагаемого.
Другими словами это очень удобный и быстрый способ итерирования, недостатка два:
- проверяются все комбинации, включая заведомо проигрышные варианты;
- если оперировать числами с плавающей точкой, то при большой разнице в слагаемых возможно накопление ошибок округления и/или потери точности;
С ускорением на два порядка я пожалуй поторопился. В первом варианте у меня была запара, из-за чего отсекались перспективные пути поиска решения. Т.е. поиск шел очень быстро, но не всегда находилось оптимальное решение. После переделки ускорение есть, но сильно зависит от качественного состава слагаемых. Оптимальный вариант - экспоненциальное увеличение номиналов. Время поиска между 2^N и 2^(N/2), реально в 4-16 раз быстрее перебора кодом Грея на наборе из 32 чисел.
> Задачку рекомендую разбить на поиск "ближайшего снизу" и
> "ближайшего сверху". Потом уже из двух выбрать наиболее
> ближайшее.
> Смысл в том, чтоб сначала упорядочить по убыванию (или
> возрастанию) числа. Если первое число больше требуемого, то
> суммы со всеми остальными не рассматриваются. Или если
> первое меньше, но сумма первых двух больше заданного, то к
> ним уже не имеет смысл добавлять последующие, продолжаем
> комбинировать первое с третьим и последующими, но уж точно
> без второго.
Именно так работает классический алгоритм на списках. Это хорошая тактика, беда в том, что нужно очень много памяти для хранения промежуточных результатов.
|
- Задачка - leo 31.08.06 11:31 [2226]
|
|
|
подробно о проекте
Анализ криптографических сетевых...
Re: как код Грея тут прикручивается - leo