информационная безопасность
без паники и всерьез
 подробно о проектеRambler's Top100
Spanning Tree Protocol: недокументированное применениеЗа кого нас держат?
BugTraq.Ru
Русский BugTraq
 Анализ криптографических сетевых... 
 Модель надежности двухузлового... 
 Специальные марковские модели надежности... 
 Кавычки уличили Google в заимствовании... 
 Некоторые пароли от G Suite хранились... 
 Microsoft выпустила Windows Sandbox 
главная обзор RSN блог библиотека закон бред форум dnet о проекте
bugtraq.ru / форум / theory
Имя Пароль
ФОРУМ
если вы видите этот текст, отключите в настройках форума использование JavaScript
регистрация





Легенда:
  новое сообщение
  закрытая нитка
  новое сообщение
  в закрытой нитке
  старое сообщение
  • Напоминаю, что масса вопросов по функционированию форума снимается после прочтения его описания.
  • Новичкам также крайне полезно ознакомиться с данным документом.
Алгоритм (в смысле нужен) 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 - будет либо огромное кол-во итераций, и как следствие просто "угадывание" результата. Либо погрешность плюс/минус "лапоть".

Посмотри условия по-внимательней.
1






Rambler's Top100
Рейтинг@Mail.ru


  Copyright © 2001-2019 Dmitry Leonov   Page build time: 0 s   Design: Vadim Derkach