[url=http://e-science.ru/forum/index.php?showtopic=28701]http://e-science.ru/forum/index.php?showtopic=28701[/url]
Была такая кривая тема, которая косвенно имеет прямое отношение...
Не могли бы Вы немного уделить внимания этой частной проблеме?
Что вы всегда хотели узнать, но боялись спросить
Что вы всегда хотели узнать, но боялись спросить
Последний раз редактировалось Andrew58 28 ноя 2019, 15:08, всего редактировалось 1 раз.
Причина: test
Причина: test
Что вы всегда хотели узнать, но боялись спросить
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]
Была такая кривая тема, которая косвенно имеет прямое отношение...
Не могли бы Вы немного уделить внимания этой частной проблеме?
первую страницу прочитала
нечто подобное читала, но не поняла, потому что
Разбиралась с общими концепциями динамического программирования по книжке Беллман Р., Калаба Р. "Динамическое программирование и современная теория управления".
В ДП используется моя любимая дискретная модель пространства состояний. Мунин, помнится, его называл "фазовым пространством". А у Беллмана всё это обобщалось на непрерывный случай :blink:
но я это даже не пыталась понять, см. козьму пруткова.
Последний раз редактировалось Swetlana 28 ноя 2019, 15:08, всего редактировалось 1 раз.
Причина: test
Причина: test
Что вы всегда хотели узнать, но боялись спросить
Видимо такая же: множество значений ЦФ содержит один элемент, поэтому и задача распознавания будет фактически не параметризованной и всего одна. Т.е. смысла мало, но формально должно быть верно.Swetlana писал(а):Source of the post ага, интересно, давайте разбираться
с точки зрения математического программирования, оптимизация бывает условной или безусловной, в принципе, нам тут без разницы
далее, целевая функция либо максимизируется, либо минимизируется
но не равна константе
иначе набор заданного веса B превращается в оптимизацию
а какая тогда у него будет задача распознавания?
Не, я не очень хорошо помню, но точно помню, что нам эти задачи приводили как эквивалентные. В частности, вроде можно было использовать ЗЛП для проверки множества на непустоту (это тоже точно помню). Могу в лекциях посмотреть.
Последний раз редактировалось Sonic86 28 ноя 2019, 15:08, всего редактировалось 1 раз.
Причина: test
Причина: test
Что вы всегда хотели узнать, но боялись спросить
вернёмся всё-таки к обсуждению задачи "Сумма размеров"
Буду делать по старинке, как я понимаю оптимизацию и распознавание.
Это задача распознавания, у которой нет оптимизационной пары. Или мы можем точно набрать число , или не можем.
Возвращаемся к реальным производственным задачам. Предположим, что набор данных (индивидуальная задача) таковы, что задача имеет ответ "нет", то есть число точно не набирается. Попробуем сформулировать "непарную" оптимизационную задачу.
Условие. Заданы набор целых положительных слагаемых и число .
Вопрос. Здесь есть варианты.
В задаче однокритериальной оптимизации должен быть задан один критерий. Можно минимизировать отклонение с недостатком, можно с избытком, можно по модулю.
Для случая малой размерности (число слагаемых ) задача во всех вариантах эффективно решается алгоритмом с возвратом.
1. Заводим переменные и и запоминаем в текущую оптимальную сумму с недостатком/избытком/по модулю, а в соответствующий оптимальный набор.
2. Как только сгенерирован набор лучший, чем текущий оптимум, и переписываются.
3. не забываем про отсечения, ускоряющие работу алгоритма, чтобы не генерировать заведомо неоптимальные решения.
Вывод. при алгоритм с возвратом эффективно решает все 4 варианта задачи.
Буду делать по старинке, как я понимаю оптимизацию и распознавание.
Это задача распознавания, у которой нет оптимизационной пары. Или мы можем точно набрать число , или не можем.
Возвращаемся к реальным производственным задачам. Предположим, что набор данных (индивидуальная задача) таковы, что задача имеет ответ "нет", то есть число точно не набирается. Попробуем сформулировать "непарную" оптимизационную задачу.
Условие. Заданы набор целых положительных слагаемых и число .
Вопрос. Здесь есть варианты.
В задаче однокритериальной оптимизации должен быть задан один критерий. Можно минимизировать отклонение с недостатком, можно с избытком, можно по модулю.
Для случая малой размерности (число слагаемых ) задача во всех вариантах эффективно решается алгоритмом с возвратом.
1. Заводим переменные и и запоминаем в текущую оптимальную сумму с недостатком/избытком/по модулю, а в соответствующий оптимальный набор.
2. Как только сгенерирован набор лучший, чем текущий оптимум, и переписываются.
3. не забываем про отсечения, ускоряющие работу алгоритма, чтобы не генерировать заведомо неоптимальные решения.
Вывод. при алгоритм с возвратом эффективно решает все 4 варианта задачи.
Последний раз редактировалось Swetlana 28 ноя 2019, 15:08, всего редактировалось 1 раз.
Причина: test
Причина: test
Что вы всегда хотели узнать, но боялись спросить
Видимо такая же: множество значений ЦФ содержит один элемент
Соник, вот это место ещё раз.
Что у нас ЦФ в задаче о наборе веса? Почему у неё только одно значение?
ЦФ - вес, который мы набрали. Если слагаемых , то ЦФ может имееть различных возможных значений. Одно значение будет при .
Последний раз редактировалось Swetlana 28 ноя 2019, 15:08, всего редактировалось 1 раз.
Причина: test
Причина: test
Что вы всегда хотели узнать, но боялись спросить
Swetlana писал(а):Source of the post
Вывод. при алгоритм с возвратом эффективно решает все 4 варианта задачи.
Я совсем тупой, поэтому спрошу прямо - а при чего-то не решается?
Последний раз редактировалось Andrew58 28 ноя 2019, 15:08, всего редактировалось 1 раз.
Причина: test
Причина: test
Что вы всегда хотели узнать, но боялись спросить
Andrew58 писал(а):Source of the post Я совсем тупой, поэтому спрошу прямо - а при чего-то не решается?
Так написано, что для всё решается.
Значит и для тоже всё ок.
Другое дело для -- ?
Последний раз редактировалось NT 28 ноя 2019, 15:08, всего редактировалось 1 раз.
Причина: test
Причина: test
Что вы всегда хотели узнать, но боялись спросить
если решений много, экспоненциально, нет смысла их печатать для n>= 20 - запрашиваем информацию большую, чем можем обработать
если нужны не все решения, а любое произвольное, то для "средней размерности", такой, чтобы nB не было слишком большим числом, пользуемся динамическим программированием
есть ли псевдополиномиальные алгоритмы помимо динамического программирования?
Гэри-Джонсон в 1982г. не знали, мне тоже неизвестно
далее будем решать "Сумму размеров" ДП
если нужны не все решения, а любое произвольное, то для "средней размерности", такой, чтобы nB не было слишком большим числом, пользуемся динамическим программированием
есть ли псевдополиномиальные алгоритмы помимо динамического программирования?
Гэри-Джонсон в 1982г. не знали, мне тоже неизвестно
далее будем решать "Сумму размеров" ДП
Последний раз редактировалось Swetlana 28 ноя 2019, 15:08, всего редактировалось 1 раз.
Причина: test
Причина: test
Что вы всегда хотели узнать, но боялись спросить
Sonic86 писал(а):Source of the postВидимо такая же: множество значений ЦФ содержит один элемент, поэтому и задача распознавания будет фактически не параметризованной и всего одна. Т.е. смысла мало, но формально должно быть верно.Swetlana писал(а):Source of the post ага, интересно, давайте разбираться
с точки зрения математического программирования, оптимизация бывает условной или безусловной, в принципе, нам тут без разницы
далее, целевая функция либо максимизируется, либо минимизируется
но не равна константе
иначе набор заданного веса B превращается в оптимизацию
а какая тогда у него будет задача распознавания?
Не, я не очень хорошо помню, но точно помню, что нам эти задачи приводили как эквивалентные. В частности, вроде можно было использовать ЗЛП для проверки множества на непустоту (это тоже точно помню). Могу в лекциях посмотреть.
Соник, смотрите лекции. Или будем в июне с Палычем вчетвером обсуждать
Открыла М.Мину "Математическое программирование"
Глава 7 "Целочисленное программирование"
У нас "гирь" с весами , каждую либо берём, либо не берём в набор веса . Вводим соответствующие переменные ,
записываем задачу целочисленного линейного программирования
,
,
Далее в Мину написано, введём условие, что что политоп ограничен и не пуст.
У нас если задача имеет ответ нет, то политоп как раз пуст.
не ставится у меня "Сумма размеров" как оптимизационная задача ЦЛП
Последний раз редактировалось Swetlana 28 ноя 2019, 15:08, всего редактировалось 1 раз.
Причина: test
Причина: test
Что вы всегда хотели узнать, но боялись спросить
Swetlana писал(а):Source of the post
не ставится у меня "Сумма размеров" как оптимизационная задача ЦЛП
Минимизируйте абсолютную разность полученной суммы и целевой суммы.
Последний раз редактировалось zykov 28 ноя 2019, 15:08, всего редактировалось 1 раз.
Причина: test
Причина: test
Вернуться в «Computer Science»
Кто сейчас на форуме
Количество пользователей, которые сейчас просматривают этот форум: нет зарегистрированных пользователей и 19 гостей