Что вы всегда хотели узнать, но боялись спросить

Andrew58 · Сообщение **Andrew58** » 08 янв 2013, 20:32

[url=http://e-science.ru/forum/index.php?showtopic=28701]http://e-science.ru/forum/index.php?showtopic=28701[/url]
Была такая кривая тема, которая косвенно имеет прямое отношение...
Не могли бы Вы немного уделить внимания этой частной проблеме?

Swetlana · Сообщение **Swetlana** » 08 янв 2013, 20:49

Andrew58 писал(а):Source of the post
[url=http://e-science.ru/forum/index.php?showtopic=28701]http://e-science.ru/forum/index.php?showtopic=28701[/url]
Была такая кривая тема, которая косвенно имеет прямое отношение...
Не могли бы Вы немного уделить внимания этой частной проблеме?

первую страницу прочитала

нечто подобное читала, но не поняла, потому что ~~было в лом~~ не занимаюсь непрерывной оптимизацией, только дискретной - Специалист подобен флюсу: $$NP$$

- полнота его односторонняя (К. Прутков).
Разбиралась с общими концепциями динамического программирования по книжке Беллман Р., Калаба Р. "Динамическое программирование и современная теория управления".
В ДП используется моя любимая дискретная модель пространства состояний. Мунин, помнится, его называл "фазовым пространством". А у Беллмана всё это обобщалось на непрерывный случай :blink:
но я это даже не пыталась понять, см. козьму пруткова.

Sonic86 · Сообщение **Sonic86** » 09 янв 2013, 07:22

Swetlana писал(а):Source of the post ага, интересно, давайте разбираться
с точки зрения математического программирования, оптимизация бывает условной или безусловной, в принципе, нам тут без разницы
далее, целевая функция либо максимизируется, либо минимизируется
но не равна константе
иначе набор заданного веса B превращается в оптимизацию
а какая тогда у него будет задача распознавания?

Видимо такая же: множество значений ЦФ содержит один элемент, поэтому и задача распознавания будет фактически не параметризованной и всего одна. Т.е. смысла мало, но формально должно быть верно.

Не, я не очень хорошо помню, но точно помню, что нам эти задачи приводили как эквивалентные. В частности, вроде можно было использовать ЗЛП для проверки множества на непустоту (это тоже точно помню). Могу в лекциях посмотреть.

Swetlana · Сообщение **Swetlana** » 09 янв 2013, 10:18

вернёмся всё-таки к обсуждению задачи "Сумма размеров"

Буду делать по старинке, как я понимаю оптимизацию и распознавание.
Это задача распознавания, у которой нет оптимизационной пары. Или мы можем точно набрать число $$B$$

, или не можем.

Возвращаемся к реальным производственным задачам. Предположим, что набор данных (индивидуальная задача) таковы, что задача имеет ответ "нет", то есть число $$B$$

точно не набирается. Попробуем сформулировать "непарную" оптимизационную задачу.
Условие. Заданы набор целых положительных слагаемых и число $B \in Z^+$ .
Вопрос. Здесь есть варианты.

В задаче однокритериальной оптимизации должен быть задан один критерий. Можно минимизировать отклонение с недостатком, можно с избытком, можно по модулю.
Для случая малой размерности (число слагаемых $n \leq 20$ ) задача во всех вариантах эффективно решается алгоритмом с возвратом.
1. Заводим переменные $$OptSol$$

и

и запоминаем в $$OptB$$

текущую оптимальную сумму с недостатком/избытком/по модулю, а в $$OptSol$$

соответствующий оптимальный набор.
2. Как только сгенерирован набор лучший, чем текущий оптимум, $$OptSol$$

и

переписываются.
3. не забываем про отсечения, ускоряющие работу алгоритма, чтобы не генерировать заведомо неоптимальные решения.

Вывод. при $n \leq 20$ алгоритм с возвратом эффективно решает все 4 варианта задачи.

Swetlana · Сообщение **Swetlana** » 09 янв 2013, 18:02

Видимо такая же: множество значений ЦФ содержит один элемент

Соник, вот это место ещё раз.

Что у нас ЦФ в задаче о наборе веса? Почему у неё только одно значение?
ЦФ - вес, который мы набрали. Если слагаемых $$n$$

, то ЦФ может имееть $$2^n$$

различных возможных значений. Одно значение будет при $$n=1$$

.

Andrew58 · Сообщение **Andrew58** » 09 янв 2013, 22:32

Swetlana писал(а):Source of the post
Вывод. при $n \leq 20$ алгоритм с возвратом эффективно решает все 4 варианта задачи.

Я совсем тупой, поэтому спрошу прямо - а при $n \leq 19$ чего-то не решается?

NT · Сообщение NT » 09 янв 2013, 23:38

Andrew58 писал(а):Source of the post Я совсем тупой, поэтому спрошу прямо - а при $n \leq 19$ чего-то не решается?

Так написано, что для $n \leq 20$ всё решается.
Значит и для $$ n=19$$

тоже всё ок.
Другое дело для $$ n=21$$

-- ?

Swetlana · Сообщение **Swetlana** » 10 янв 2013, 21:56

если решений много, экспоненциально, нет смысла их печатать для n>= 20 - запрашиваем информацию большую, чем можем обработать
если нужны не все решения, а любое произвольное, то для "средней размерности", такой, чтобы nB не было слишком большим числом, пользуемся динамическим программированием
есть ли псевдополиномиальные алгоритмы помимо динамического программирования?
Гэри-Джонсон в 1982г. не знали, мне тоже неизвестно
далее будем решать "Сумму размеров" ДП

Swetlana · Сообщение **Swetlana** » 11 янв 2013, 16:33

Sonic86 писал(а):Source of the post
Swetlana писал(а):Source of the post ага, интересно, давайте разбираться
с точки зрения математического программирования, оптимизация бывает условной или безусловной, в принципе, нам тут без разницы
далее, целевая функция либо максимизируется, либо минимизируется
но не равна константе
иначе набор заданного веса B превращается в оптимизацию
а какая тогда у него будет задача распознавания?
Видимо такая же: множество значений ЦФ содержит один элемент, поэтому и задача распознавания будет фактически не параметризованной и всего одна. Т.е. смысла мало, но формально должно быть верно.

Не, я не очень хорошо помню, но точно помню, что нам эти задачи приводили как эквивалентные. В частности, вроде можно было использовать ЗЛП для проверки множества на непустоту (это тоже точно помню). Могу в лекциях посмотреть.

Соник, смотрите лекции. Или будем в июне с Палычем вчетвером обсуждать

Открыла М.Мину "Математическое программирование"
Глава 7 "Целочисленное программирование"

У нас $$n$$

"гирь" с весами $$c_i$$

, каждую либо берём, либо не берём в набор веса $$B$$

. Вводим соответствующие переменные $x_1, \ x_2, \dots , \ x_n$ , $x_i \in \{0, \ 1\}, \ i = 1 \dots n.$

записываем задачу целочисленного линейного программирования
$z = cx \rightarrow min$ ,
$$cx = B$$

,
$x \in \{0, \ 1\}.$

Далее в Мину написано, введём условие, что что политоп $$cx = B$$

ограничен и не пуст.
У нас если задача имеет ответ нет, то политоп как раз пуст.
не ставится у меня "Сумма размеров" как оптимизационная задача ЦЛП

zykov · Сообщение **zykov** » 15 янв 2013, 00:30

Swetlana писал(а):Source of the post
не ставится у меня "Сумма размеров" как оптимизационная задача ЦЛП

Минимизируйте абсолютную разность полученной суммы и целевой суммы.

yourdomain.com