|
Для решения рода многошаговых задач разработан соответствующий математический аппарат, который получил название динамическое программирование.
Метод динамического программирования был предложен и развит Р. Беллманом и его учениками в начале 50-х годов и состоит в нахождении оптимума целевой функции при ограничении общего вида на варьируемые параметры.
Характерным для динамического программирования является то, что переменные рассматриваются не вместе, а последовательно - одна за другой. При этом вычислительная схема строится таким образом, чтобы вместо одной задачи с n переменными решалась серия задач с небольшим числом, а чаще всего с одной переменной. Сам же вычислительный процесс производится на основе метода последовательных приближений в два этапа:
· от последнего шага к первому;
· от первого шага к последнему или же, наоборот, в зависимости от исходных данных.
На первом этапе ищется так называемое условное оптимальное решение. Оно выбирается так, чтобы все предыдущие шаги обеспечили максимальную эффективность последующего. Основу такого подхода составляет принцип оптимальности Беллмана, который формулируется следующим образом: нельзя получить оптимальное значение целевой функции i-шагового процесса, если для любого ui, выбранного на шаге I, значение целевой функции для оставшихся i-1 шагов не является оптимальным.
Такой процесс продолжается до тех пор, пока решение не потеряет свой условный характер, т.е. до первого шага или последнего. Для последнего шага решение однозначно оптимально. Поэтому второй этап начинают именно с этого шага и последовательно переходят от условных к оптимальным решениям, тем самым обеспечивая оптимальность операции в целом.
Процесс поиска начинается с последовательно пройденных этапов.
этап - Попадание в точку K одним способом - J, L, I.
этап - 3-мя способами - G, E, C.
этап - 4-мя способами - B, H.
этап - 10-тью способами - F, D.
этап - 15-тью способами - А.
Далее ищем оптимальные варианты.
Для данной дорожной сети найдено кратчайшее расстояние между двумя пунктами А и K (A - C - E - G - L - K) = 91.8 ед. Необходимо отметить, что оптимизация дорожной сети в «ручную» при большом объёме данных является долгим и трудоёмким процессом.
|
