Легенда:
 новое сообщение
 закрытая нитка
 новое сообщение
 в закрытой нитке
 старое сообщение
|
- Напоминаю, что масса вопросов по функционированию форума снимается после прочтения его описания.
- Новичкам также крайне полезно ознакомиться с данным документом.
| |
супер! то, что ты сочинил за 10 мин... 02.11.01 13:50 Число просмотров: 2184
Автор: Nike Статус: Незарегистрированный пользователь
|
называется методом Монте-Карло для задач оптимизации.
он действительно быстрее всех дает максимально приближенное к оптимальному решению интерполяцию. а для NP-полных задач, к которым относится и данная - единственный способ найти оптимальное решение - полный перебор.
|
|
<theory>
|
Алгоритм (в смысле нужен) 31.10.01 23:25
Автор: leo <Леонид Юрьев> Статус: Elderman
|
Извиняюсь за offtipic, но в programming только всякаяерунда
Помните задачку из учебников/олимпиад когда надо минимальным количеством монет набрать нужную сумму. На первый взгляд в том-же духе...
Так вот (по взрослому):
1) имеем толстый кошелек с монетами, при этом для каждой монеты задан ее возраст (коэффициент новизны);
2) пользователем задан массив вещественных коэффициентов;
3) нужно разложить монеты в кучки (по количеству заданных коэффициентов), так чтобы суммы в кучках относились между собой также как и коэффициенты в массиве, с минимальной ошибкой;
4) при раскладке монет нужно очень постараться разложить их так, чтобы в каждой кучке было хотя бы по одной «новой» монете. Другими словами если у нас пять кучек, то по одной из пяти самых новых монет должно лежать в каждой кучке;
Мне нужно было сделать быстро, за день-два (вместе с «прикладной» частью), поэтому я сделал «в лоб» перебором с «кружевами». Но вот может кто из обладателей классического образования, что-нибудь толковое скажет :-)
Известные мне алгоритмы ломаются на том, что нужно найти именно оптимальное решение для нескольких сумм, а не просто "подобрать монеты".
Задача не придумана, а является реальной (распределение ресурсов).
Ну и как-бы совсем offtopic (еще раз прошу прощенья):
Я работу ищу (в Москве), программирование всякое, а-ля драйвера для W2K/XP/Linux, и НЕ генераторы отчетов. Может кто что посоветует. Резюме есть на http://leo-yuriev.narod.ru
Удачи.
|
|
Я бы попробовал применить тут генетические алгоритмы... 03.11.01 11:41
Автор: SerpentFly <Vadim Smirnov> Статус: Member
|
|
Для некоторых задач из NP-полноты они вполне эффективны, хотя и невсегда дают результат. В конце концов можно попробовать на определенном количестве примеров, если в большинстве случаев алгоритм будет сходиться, то ....
|
| |
Генетические алгоритмы? 11.12.01 09:24
Автор: qwerty Статус: Незарегистрированный пользователь
|
А можно поподробнее насчет 'генетических' алгоритмов?
Я что-то читал по поводу того, что был предложен метод параллельного обсчета вариантов ключей DES с помощью цепочек ДНК, где определенные сочетанные структуры (выпуклости) на цепочках служили своего рода памятью для работы алгоритма. Более конкретно сказать не могу.
Поделитесь информацией, если есть?
Может быть существуют программные эммуляторы 'генетических' алгоритмов, а то с пробирками-то особо не поработаешь :)))
|
| | |
Генетические алгоритмы? 11.12.01 12:15
Автор: zelych Статус: Member
|
> А можно поподробнее насчет 'генетических' алгоритмов?
> Я что-то читал по поводу того, что был предложен метод
> параллельного обсчета вариантов ключей DES с помощью
> цепочек ДНК, где определенные сочетанные структуры
> (выпуклости) на цепочках служили своего рода памятью для
> работы алгоритма. Более конкретно сказать не могу.
> Поделитесь информацией, если есть?
> Может быть существуют программные эммуляторы 'генетических'
> алгоритмов, а то с пробирками-то особо не поработаешь :)))
вобще-то, пробирки тут вовсе непричём, генетические алгоритмы - они не потому генетические, что там гены всякие..
просто некоторое состояние системы изменяется по законам, похожим на изменение генетического кода при рождении новой особи..
(правда мудрёно??)
а если проще, имеется некоторое состояние системы (ключ), которое посредством генетического алгоритма должно принять некоторые свойства (открывать шифртекст)..
первоначальное состояние в общем случае случайное, из этого состояния генерируются другие, немного изменённые состояния (мутация)..
затем полученные 'мутанты' проверяются на соответствие требуемым свойствам (открывают или нет) - тот, который больше всех подходит выбирается в качестве следующего состояния.. (и так далее).
не думаю что всё это подойдёт для вскрытия каких-либо шифров, потому как при небольших изменениях ключа генерируемый шифртекст изменится весьма значительно, соответственно отобрать из нескольких ключей наиболее подходящий весьма трудно..
вот так..
|
| |
Попробовал генетику, результат в целом хуже 23.11.01 15:14
Автор: leo <Леонид Юрьев> Статус: Elderman
|
В простых случаях мой перебор с "бантиками" всегда в 2-5 раз быстрее.
В сложных случаях, генетика сильно зависит от угадывания. Иногда быстрее перебора, иногда в 10 раз меделенее. В среднем перебор оказался быстрее и более предсказуем.
|
|
Не знаю классических решений 01.11.01 13:12
Автор: PS <PS> Статус: Elderman
|
просто хочу предложить то, что пришло в голову.
Итак есть:
1. L - кол-во куч
2. wi - коэфициент (вес) iой монеты.
3. V=vi...vL массив заданый пользователем
4. Tij = vi/vj, где j=i+1
5. Wi - вес кучи = Sum w
6. Dij = Wi/Wj, где j=i+1
1. Выбераем базу B состоящую из монет наибольшего w.Bпока менять не будем.
1.1 Случайным образом распределим оставшиеся монеты по кучам.
1.2 Проверим условие выполнения задачи
1.3 Найдем MAX Dij и MIN Dmn
1.4 Переместим монету с MIN w из кучи i в кучу m.
1.5 Перейдем на 1.2
Может получиться, что после 1.4 Dij станет минимальной, а Dmn-максимальной. Т.е. вечный цикл. На вскидку пути решения: 1. Перейти к п1.1, или не трогать Dij и Dmn, а распределять для других куч.
2. Если вBвсе w равны - закончить. Если нет,то:
2.1 переставить кучи так, что бы базовые элементы с разным w оказались на других местах.
2.2 повторить алгоритм с п1.1
2.3 Повторить п2.1 пока не переберутся все возможные варианты вB
2.4 Выбрать оптимальный.
Т.е. это что-то типа множества весов( две чашки на палке :) ), которые необходимо сбалансировать.
Ногами не пинать, придумал за 10минут :)))
> Извиняюсь за offtipic, но в programming только всякая
>ерунда
>
> Помните задачку из учебников/олимпиад когда надо
> минимальным количеством монет набрать нужную сумму. На
> первый взгляд в том-же духе...
>
> Так вот (по взрослому):
> 1) имеем толстый кошелек с монетами, при этом для каждой
> монеты задан ее возраст (коэффициент новизны);
> 2) пользователем задан массив вещественных коэффициентов;
> 3) нужно разложить монеты в кучки (по количеству заданных
> коэффициентов), так чтобы суммы в кучках относились между
> собой также как и коэффициенты в массиве, с минимальной
> ошибкой;
> 4) при раскладке монет нужно очень постараться разложить их
> так, чтобы в каждой кучке было хотя бы по одной «новой»
> монете. Другими словами если у нас пять кучек, то по одной
> из пяти самых новых монет должно лежать в каждой кучке;
>
> Мне нужно было сделать быстро, за день-два (вместе с
> «прикладной» частью), поэтому я сделал «в лоб» перебором с
> «кружевами». Но вот может кто из обладателей классического
> образования, что-нибудь толковое скажет :-)
>
> Известные мне алгоритмы ломаются на том, что нужно найти
> именно оптимальное решение для нескольких сумм, а не просто
> "подобрать монеты".
>
> Задача не придумана, а является реальной (распределение
> ресурсов).
>
> Ну и как-бы совсем offtopic (еще раз прошу прощенья):
> Я работу ищу (в Москве), программирование всякое, а-ля
> драйвера для W2K/XP/Linux, и НЕ генераторы отчетов. Может
> кто что посоветует. Резюме есть на
> http://leo-yuriev.narod.ru
>
> Удачи.
|
| |
супер! то, что ты сочинил за 10 мин... 02.11.01 13:50
Автор: Nike Статус: Незарегистрированный пользователь
|
называется методом Монте-Карло для задач оптимизации.
он действительно быстрее всех дает максимально приближенное к оптимальному решению интерполяцию. а для NP-полных задач, к которым относится и данная - единственный способ найти оптимальное решение - полный перебор.
|
| | |
супер! то, что ты сочинил за 10 мин... 03.11.01 03:28
Автор: leo <Леонид Юрьев> Статус: Elderman
|
> называется методом Монте-Карло для задач оптимизации.
> он действительно быстрее всех дает максимально приближенное
> к оптимальному решению интерполяцию. а для NP-полных задач,
> к которым относится и данная - единственный способ найти
> оптимальное решение - полный перебор.
Я не могу считать себя большим спецом по части применения Мотне-Карло, но IMHO здесь не тот случай. Опять же IMHO - будет либо огромное кол-во итераций, и как следствие просто "угадывание" результата. Либо погрешность плюс/минус "лапоть".
Посмотри условия по-внимательней.
|
|
|
подробно о проекте
Анализ криптографических сетевых...
