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

Многие задачи динамического программирования не поддаются аналитическому решению. В этих случаях применяются численные методы, часто требующие использования вычислительных машин. Принцип вложения позволяет преодолеть серьезный недостаток численных методов, а именно отсутствие общности. При применении указанного метода достигается общность, присущая аналитическим методам, за счет получения спектров решений. [c.18]

Принципиальный недостаток метода динамического программирования заключается в трудности подхода к многомерным задачам. При очень большом числе переменных решение задачи методом динамического программирования даже на больших вычислительных машинах ограничивается памятью и быстродействием машины. Для лучшего понимания этого сошлемся на часто применяемый метод оптимизации с помощью поиска на сетке переменных. Если в интересующей нас области для каждой переменной используется по 10 дискретных значений, то, очевидно, двумерная задача потребует исследования 100 узлов, трехмерная —1000 и т. д. Если, однако, 10 значений дают слишком грубую сетку, то должно быть выбрано большее число дискретных значений, что, конечно, увели- [c.23]

Обычный метод решения задач динамического программирования состоит в построении сетки в пространстве переменных. Каждый узел сетки представляет собой набор численных значений переменных. Поисковым методом обследуются различные узлы сетки с целью отыскания оптимального узла. Преимуществом этого способа является то, что для него без труда составляется программа, а недостаток состоит в том, что он требует большой затраты машинного времени и достаточного объема памяти, если сетка густая, а число переменных больше, например, четырех. [c.178]

Размерность задачи, определяемая числом управляющих переменных и фазовых координат, часто требует рассмотрения сеток большой размерности. Это существенный недостаток метода. Как при увеличении размерности сетки, так и при уменьшении шага сетки быстродействие и объем памяти машины становятся недостаточными. Задачам большой размерности уделялось много внимания, и было потрачено много усилий для их решения. Если бы нам в настоящее время нужно было указать пример принципиального ограничения применимости динамического программирования, мы, без сомнения, назвали бы задачи большой размерности. В этой главе будут рассмотрены некоторые приемы и способы сокращения размерности. [c.179]

Описанные методы динамического программирования достаточно эффективны, требуют не больше порядка N, Nj операций для решения задачи выравнивания, однако им присущ серьезный недостаток - они требуют для своей работы большой емкости памяти для запоминания карты обратных переходов (помнить всю матрицу F не обязательно, поскольку на каждом шаге используется только предыдущая строка этой матрицы). Так, для выравнивания двух последовательностей по 10 букв требуется память порядка одного мегабайта. Оперативная память такого размера редко встречается в персональных компьютерах, и для реализации методов динамического программирования приходится использовать внешнюю память на магнитных дисках, что приводит к заметному увеличению времени работы программы. [c.27]

Другой недостаток АВМ состоит в необходимости априорного определения возможного диапазона изменения зависимых переменных. Масштабирование зависимых математических переменных считается одним из наиболее ответственных и сложных этапов программирования так как динамический диапазон АВМ невелик. Неправильное масштаби- рование может привести или к выходу электрических напряжений из линейного рабочего диапазона (обычно 100 В) или, наоборот, к настолько малым значениям машинной переменной, когда она оказывается соизмеримой с погрешностями операционных блоков АВМ, И в том, и в другом случае решение задачи будет сопряжено с большой потерей точности. Для ОЗТ трудности масштабирования зависимых переменных становятся значительными, поскольку необходимо еще до моделирования задачи априори оценить максимальные значения масштабных переменных. Если при решении прямых задач теплопроводности такая оценка сравнительно легко осуществима на базе принципа максимума (наибольшие значения величин температурного поля не могут превышать по абсолютной величине известные краевые функции), то в случае обратных задач прогнозирование наибольших величин переменных до решения задачи весьма затруднительно. Поэтому может потребоваться длительный экспериментальный подбор масштабов, обеспечивающих приемлемую точность воспроизведения результатов [c.245]