Для решения таких задач метод динамического программирования применить нельзя.

Например, если в качестве оценки пути принята немонотонная функция суммы шаговых затрат. Или, например, сумма произведений шаговых затрат S_i на двух последних шагах,

S₁ S₂ + S₂ S₃ +…+ S_k-1 S_k , где k- число шагов, которое в задаче с сеткой равно m + n.

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

Объём вычислений резко возрастает при возрастании размерности задачи ( это число шаговых вариантов или в конечном итоге размер сетки). В нашей задаче из одного состояния ( узла ) можно перейти не более, чем в два других.

В реальных задачах таких переходов может быть существен-но больше (рис.2). Например, поиск оптимального пути на трёх-мерной сетке принципиально ничем не отличается от двумерной, но число переходов существенно возрастает. Важно и число возможных состояний и число возможных переходов (шагов).

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

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

В частности, можно ли применять метод, если некоторые переходы изначально запрещены, или количественная оценка пути является более сложной функцией (даются конкретные функции), чем сумма шаговых затрат. Для понимания сущности метода представляется интересным вопрос о его применимости, если в той же задаче с сеткой в качестве количественной оценки пути принять не просто сумму затрат, но и количество изменений направления, умноженное на заданное число (штраф за “извили-стость” пути).

Программа считает, что в этом случае алгоритм динамичес-кого программирования применить нельзя. Однако речь идёт об алгоритме, реализованном в данной программе, в котором сос-тояние – это узел. Если же принять, что состояние это отрезок, соединяющий два узла, то можно реализовать несколько более сложный алгоритм, но всё того же метода динамического прог-раммирования.

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

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

В реальных задачах оптимизации, которые не сводятся к по-иску оптимального пути на двумерной сетке, могут быть локаль-ные минимумы, для которых количественные оценки искомого решения (значения целевой функции ) не совпадают.

Наличие локальных минимумов (иначе говоря многоэкстре-мальность задачи ) является серьёзным препятствием для применения многих методов оптимизации [4].

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

В некоторых практических задачах оптимизации для приме-нения метода динамического програмирования приходится искусственно вводить дискретность перебора. Если речь идёт о поиске непрерывной оптимальной траектории, то эта траектория представляется ломаной линией из – за введённой дискретности.

В этом случае точность решения задачи тем выше, чем меньший дискрет используется (например, меньше размер ячеек двумерной сетки).