Динамическое программирование

Статья посвящена описанию процедур экономико-математического моделирования тенденций в области жилищного строительства с учетом особенностей различных стран постсоветского пространства. Приведены результаты анализа известных научных публикаций по вопросам прогнозирования динамики индикаторов рынка жилья. Показано, что большинство отечественных и зарубежных ученых в качестве наиболее результативных методов моделирования данных индикаторов рассматривают методы анализа временных тенденций, в которых для аппроксимации имеющихся ретроспективных данных используются полиномы высокого (в ряде случаев до четвертой степени) порядка. Другими распространенными подходами к решению рассматриваемой задачи являются применение краткосрочного прогнозирования на основе алгоритмов построения скользящей средней, а также использование модели SARIMA, которая учитывает тренд и сезонную волну. В статье показано, что данные методы не позволяют в полной мере учесть глубокие изменения в строительных комплексах постсоветских государств, вызванных существенной структурной трансформацией их социально-экономических систем. Авторами предложено для моделирования основных индикаторов жилищного строительства использовать эконометрические модели на основе регрессий с фиктивными переменными, учитывающие сложную структуру внешней и внутренней среды национальных строительных комплексов. Показано, что в значительном числе практических ситуаций достаточно простым, но результативным способом учета составляющих временного ряда рассматриваемых индикаторов в рамках одной комплексной модели является применение модели «изменения роста (падения)» при выборе в качестве характеристической точки времени начала (окончания) кризисной ситуации. Результаты моделирования основных индикаторов жилищного строительства для различных стран постсоветского пространства показали, что предложенная модель при построении среднесрочного прогноза позволяет учесть ситуационную составляющую анализируемого временного ряда.

В данной книге систематизирован материал по одному из методов проектирования алгоритмов в информатике – динамическому программированию. Предлагаемые задачи решаются фактически по одной схеме, основанной на данном методе, однако понять, что задача решается этим методом, очень непросто. Для этого кроме знаний требуется усилие подготовленного к решению таких задач интеллекта. Именно этому способствуют содержание книги и стиль изложения материала в ней. Разобраны задачи, предлагавшиеся школьникам на всероссийских олимпиадах по информатике разных лет, а также на турнирах и конкурсах. Для учащихся старших классов, студентов и преподавателей информатики.

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

Глубокое обучение с подкреплением (Reinforcement Learning) – самое популярное и перспективное направление искусственного интеллекта. Практическое изучение RL на Python поможет освоить не только базовые, но и передовые алгоритмы глубокого обучения с подкреплением. Вы начнете с основных принципов обучения с подкреплением, OpenAI Gym и TensorFlow, познакомитесь с марковскими цепями, методом Монте-Карло и динамическим программированием, так что «страшные» аббревиатуры DQN, DRQN, A3C, PPO и TRPO вскоре перестанут вас пугать. Вы узнаете об агентах, которые учатся на человеческих предпочтениях, DQfD, HER и многих других последних достижениях RL. Прочитав книгу, вы приобретете знания и опыт, необходимые для реализации обучения с подкреплением и глубокого обучения с подкреплением в реальных проектах, и войдете в мир искусственного интеллекта. После покупки предоставляется дополнительная возможность скачать книгу в формате epub.

Настоящее учебное пособие посвящено задачам линейного и динамического программирования. Содержит постановки основных задач линейного и динамического программирования и основные методы их решения. Издание предназначается студентам, обучающимся по всем направлениям подготовки и специальностям.

Изложен принцип оптимальности и базирующийся на нем метод динамического программирования решения задач управления многошаговыми процессами, разобран ряд примеров решения типовых задач экономического содержания, рассмотрены обобщения классического принципа оптимальности и метода динамического программирования на случай задач из теории графов. Контрольные вопросы и задачи позволят закрепить полученные знания теоретического материала и обрести навык самостоятельного решения задач, дадут возможность использовать пособие для работы на практических занятиях. Для студентов экономических специальностей вузов, а также для студентов технических специальностей, изучающих соответствующий раздел математического программирования.

В книге рассматриваются теоретические основы линейного, нелинейного и динамического программирования. По каждому из трех разделов приводятся контрольные вопросы и задачи, на большинство из них в приложениях даны ответы и решения. Разбираются также практические задачи из различных областей, решенные методами линейного, нелинейного и динамического программирования. Книга содержит сведения о специально разработанных обучающих компьютерных программах и рекомендации по их применению. Используемый математический аппарат сведен к минимуму и поясняется в тексте, что обеспечивает понимание методов оптимизации при наличии математической подготовки в объеме программы обычного технического вуза. В основу книги положены курс лекций автора в Московском институте радиотехники, электроники и автоматики (МИРЭА) и практический опыт разработки программных средств для решения задач оптимизации большой размерности в рамках САПР. Книга может быть полезна студентам и аспирантам, изучающим методы оптимизации, а также специалистам, сталкивающимся с проблемами выработки оптимальных решений в различных областях деятельности.

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

Рассматриваются линейное, дискретное, выпуклое, нелинейное и динамическое программирование, транспортные и потоковые задачи, оптимизационные задачи на графах и матроидах, теория полиноминальной сводимости и NP-полноты. Для студентов экономических и инженерно-технических специальностей вузов. Будет полезно также магистрантам, аспирантам и преподавателям вузов.

Настоящая книга предназначена в качестве учебного пособия для студентов факультетов прикладной математики, факультетов по переподготовке специалистов в области использования вычислительной техники, а также для учащихся математических техникумов. В ней излагается методика составления оптимизационных моделей в прикладных задачах, общие принципы линейного, нелинейного и динамического программирования, приводится обзор основных методов численного анализа для задач отыскания экстремумов функций.

В данной статье задачи оптимизации трасс, возникающие в САПР линейных сооружений, классифицируются как вариационные и сводятся к минимизации функционалов при наличии ряда ограничений на вид и параметры искомой экстремали. Искомое проектное решение независимо от вида сооружения (железные и автомобильные дороги, трубопроводы различного назначения, каналы оросительной сети и др.) представляет собой сплайн, то есть плоскую кривую, состоящую из элементов заданного вида. В отличие от задач, рассматриваемых в теории сплайнов, возможные границы элементов и даже их число не известно. Проектируемый сплайн обладает рядом других особенностей, что не позволяет использовать методы нелинейного программирования. В импортных САПР линейных сооружений и их российских аналогах проектные решения тем или иным способом назначаются проектировщиками. Предложенный отечественными исследователями альтернативный подход, принятый в данной статье, состоит в переходе к компьютерной выработке проектных решений на основе математических моделей, алгоритмов оптимизации и проектирующих программ. Излагается новый алгоритм аппроксимации последовательности точек на плоскости сплайном, состоящим из отрезков прямых, клотоид и окружностей, как это требуется при проектировании трасс дорог и других линейных сооружений.

В данной статье рассматриваются прикладные задачи, для решения которых ранее предлагался метод динамического программирования, разработанный Р. Беллманом в середине прошлого века. Этот метод, основанный на принципе оптимальности и вытекающих из него рекуррентных уравнениях, позволил свести решение многих сложных прикладных задач к решению последовательности более простых однотипных задач. К настоящему времени с помощью динамического программирования решены многие практически важные задачи. Однако при решении задач большой размерности, особенно при разработке систем, в которых алгоритм динамического программирования встроен в многократно повторяющийся цикл расчётов, время счёта оказывается неприемлемо велико даже с учётом мощностей современных компьютеров. Проблема повышения эффективности динамического программирования продолжает оставаться актуальной. В этом состоит цель настоящей работы. Установлено, что возможны различные реализации динамического программирования при решении одних и тех же прикладных задач. В статье анализируются возможности повышения эффективности применения динамического программирования при детальном учёте специфических особенностей прикладных задач, из которых некоторые допускают получение рекуррентных формул для вычисления оптимальной траектории на основе принципа оптимальности Р. Беллмана без перебора вариантов. Показано, что многие прикладные задачи, для решения которых предлагался метод динамического программирования с отбраковкой вариантов путей, приводящих в конкретное состояние, допускают дополнительно и отбраковку бесперспективных состояний в процессе счёта. Это резко повышает эффективность динамического программирования как с точки зрения используемого объёма памяти, так и с точки зрения времени счёта. Это утверждение основано на использовании специально разработанных экспериментальных программ для выполнения расчётов с целью оценки эффективности нового алгоритма применительно к решению практических задач как однокритериальных, так и двухкритериальных. Приводятся примеры таких задач и соответствующий алгоритм их решения.