Ф.П. Васильев - Численные методы решения экстремальных задач (1125247), страница 119
Текст из файла (страница 119)
Опишем порядок работы с этими соотношениями в предположении, что каждая из шкал состояний Н, состоит из конечного числа точек р< (»=О, 1, ... ..., Л1). Заметим, что в этом случае в (6) вместо ш1 можно писать шш. Функция Сз(х) = Ф(х), хж Н„нам известна.
Для вычисления Сз-,(х) с помощью элементарных операций соединим попарно все точки шкал Нз, и Н . Сравнивая рз- рз величин М,(х, у)+Ф(у) при всевозможных х»НН; о у»ИН, найдем ш1п (Мн — »(х, у) + Ф(У)) = СА -»(х), а также точку РИНА у у,(х)»ИН„, х»ЕН „на которой этот минимум достигается. Коли С+,(х) и у=у»+»(х)»н Н+„х»ИН+, уже известны, то для вычисления С,(х), х»ЕН», соединим элементарными операциями всевозможные пары точек шкал Н, и Н,+,. Перебором р„р„+, величин М, (х, у)+ С,+, (у) при всех х я Н„у»и Н„+, найдем шш (М»(х,у) + Сд+»(у)), а также точку у=у»(х)»и ин Нд+» ~Н„+и х~ Н„, на которой этот минимум достигается, и т.
д. для всех й=Л, Н вЂ” 1, ..., 1, О. На вычисление всех С,(х) в у = у,(х), х ы Н„(й = О, 1, ..., Н вЂ” 1), понадобится переоор к-1 ~ лл+» величин. НаконеЦ, нахоДим х, ее Н, из УсловиЯ » О»»+» Сд(х») = (п1 С,(х) — для этого нужно перебрать еще р, вели"ннз чин, и определяем последовательно точки х, = у» (х,), х, = = У» (х»), ° ° ., хй = Ун-» (хн»). Путь, проходящий через найден»' » ные точки х„х„...,хн, будет кратчайшим среди всех путеи, соединяющих крайние шкалы Н„Н . В самом деле, по определени»о у„(х) (й=О, 1, ..., Л вЂ” 1) и хденН» (й= 0,1,,,Х) имеем Сд (хд) = Мд (хд, хдед) + Сд+» (хд+»), й = О, 1,..., Х вЂ” 1. (8) Возьмем произвольный путь, соединяющий шкалы Н, и Н» и проходящий через точки х„х„..., х„, х»»и Н, (» = О, 1, ..., Л).
Так как х„+,»ИН»+„то согласно (6) будем иметь С»(х»)< ~М»(х», х,+,)+С,+,(х,+,). Отсюда и из (8) тогда следует Мд(хд,хд+») + С»+»(хд+») — Сд(хд) = 0~(М»(хд,хд+»)+ + Сд+»(хд+д) — Сд(хд) (й= О, 1, ..., Н вЂ” 1). Просуммируем это СХЕМА МОИСЕЕВА 509 неравенство по к от нуля до У вЂ” 1. Получим Н-1 ~х~1 Мь (хь, хь+,) + Сн (хй) — Сз (х, ) ( А=-О ~~ ~ МА (ХА, ха+ 1) + Се (хн) — Сз (хз). Н-1 поэтому ~2~ Мь (ХА хз+1) + А=о НО С,1 (хз) = 1Е1 С„(х) ~ (С,1 (х,), »ннз И-1 + Ф (х») ( 2~ Мь (хь, ха+1) +. Ф (хн) для любых путей, сое- А-з диняющнх шкалы Н, и Н». Таким образом, путь, проходящий через точки х„х„..., хй в самом деле кратчайший.
Если » » и1 (2) и х1 (8) (й ~ 2 ( й+,) представляют собой то управле- ние и соответствующую траекторию, на которых приближенно реализуется элементарная операция (1) — (4) при х = х1, р = = х;+„то в качестве приближенного решения исходной задачи (1.1) — (1.4) можно взять управление и*(2) = и1(2) и траекторию х»(2) = х1 (8) (21ч 2~~21+1, 1= 0,1, ...,А1 — 1).
Аналогично доказывается, что путь, проходящий через точки » » 2 В~ » / * хь= хе= Ны хь+ = уз(хь) ЕБ На+1,...,ХЕ = у» 1(хн 1) ~НЕ, является кратчайшим между точкой Х~Н„и шкалой Н». Это означает, что функция ра(х) дает нам приближенное решение проблемы синтеза для задачи (1 1) — (1.4). Заметим, что определение кратчайшего пути между шкала- Ю-1 ми Н, и Н» по описанной схеме потребовало перебора 2~ р1р1+1+ 1-о + р, величин, в то время как полный перебор всех путей, как нетрудно видеть, потребовал бы сравнения р,р,...р» величин.
Таким образом, уже при не слишком больших р; перебор с по- мощью соотношений (6) по сравнению с полным перебором дает существенную экономию памяти ЭВМ и машинного време- ни. Такая экономия достигается за счет того, что при вычис- лении С„(х) из (6) рассматриваются лишь пути, проходящие через всевозможные точки х 1н Н„и у 1и Нз+1 и соединяющие точ- ки ушН,~1 со шкалой Н кратчайшим образом, и тем самым все некратчайшие пути, соединяющие у 1ЕН1+1 со шкалой Н», из рассмотрения полностью исключаются. 4.
Для получения более точного решения задачи (1 1) — (1.4) необходимо взять более густую сетку точек на шкалах и уве- личить число шкал. Однако при этом число перебираемых ве- личин даже при использовании описанной выше схемы перебора катастрофически быстро растет, и уже при небольших размер- динлмнчкскон пгоггьммиРОВАние [Гл. т 510 ностях векторов х, и становится невозможным решить задачу о кратчайшем пути за разумное время с помощью самых лучших современных ЭВМ.
В этом случае часто используют прием, известный под названием метода блуждающих трубок [3261. Суть этого приема заключается в следующем. Сначала берут небольшое число шкал с небольшим количеством точек на них, и по описанной выше схеме поиска находят кратчайший путь 1„соединяющий крайние шкалы Н, и Н . Затем уменьшают шаг сетки на каждой шкале, путь 7, окружают некоторой «трубкой» из путей, проходящих вблизи 1, по точкам новой сетки.
Для построения трубки вокруг 1, на каждой шкале обычно берут небольшие окрестности точки, через которую проходит 70 и рассматривают пути, проходящие через выбранные точки. С помощью описанной выше схемы перебора находят кратчайший путь в полученной трубке; все пути вне этой трубки в переборе пока не участвуют. Таким образом, получают новый улучшенный путь 1„длина которого не превышает длину 1,.
Далее, сохраняя прежние шкалы и точки на них, окружают путь 1, новой трубной и находят следующее приближение 1, и т.д., продолжая процесс до тех пор, пока трубка не перестает «блуждать» и впервые не получится равенство 7. = 1,+о После этого измельчают сетку на каждой шкале, окружают путь 7. новой трубкой и продолжают поиск кратчайшего пути описанным приемом блуждающих трубок. Процесс измельчения сетки на шкалах и поиска кратчайшего пути указанным способом повторяют, пока дза кратчайших пути, полученные после двух последовательных измельчаний сетки, не совпадают с удовлетворительной точностью.
Затем увеличивают число шкал, т. е. сгущают сетку по времени, и повторяют процесс поиска методом блуждающих трубок с постепенным измельчением сетки на шкалах состояний до удовлетворительного совпадения двух последовательных приближений. Попеременно измельчая сетку на шкалах состояния и сетку по времени, поиск с помощью блуждающих трубок продолжают до получения приближенного решения исходной задачи с достаточной точностью.
Изменение шагов сеток на шкалах состояния и по времени должно быть согласованным; например, в случае равномерных сеток эти шаги должны удовлетворять соотношению 1Лх! =о(61) [2171. Оказывается, метод блуждающих трубок во многих случаях существенно сокращает перебор. В то же время следует заметить, что метод блуждающих трубок позволяет определить, вообще говоря, лишь локально кратчайший путь между крайними шкалами при фиксированной сетке, поскольку на каждом шаге в переборе участвуют лишь пути, попавшие в трубку. 5. Другой подход к поиску кратчайшего пути между шкалами дает метод локальна»х вариаций [$4, 217, 326]. Этот метод СХЕМА МОИСЕЕВА Рис.
73 предполагает, что какой-то путь 1„соединяющий шкалы Н, и Н», уже известен. Для определения следующего более короткого пути последовательно просматриваются шкалы Н„Н„... *, Н». Допустим, что шкалы Н„..., Н2, уже просмотрены и получен путь )с~ „соединяющий шкалу Н, и Н». Пусть л<(1,)— точка пути 1о лежащая на шкале Н,. Выберем на шкале Н~ некоторов количество точек, расположенных близко к точке л2(),), и переберем пути, проходящие через эти выбранные точки шкалы Не а в остальном совпадающие с путем )с~-о Если среди перебираемых путей найдется путь, имеющий меньшую длину, чвм путь )с,-ь то его обоаначаем через )и и просмотр шкалы Н< на этом заканчиваем.
Если же длины всех перебираемых путей оказались не меньше длины )с, „то полагаем )я = = )с~,. После определения пути )и переходим к просмотру следующей шкалы Н<+, и т. д. Такой перебор всех шкал Н„Н„... , Н» закончится получением пути )~» = )2.
Если длина пути )» меньше длины )е то для пути ), повторяют описанный выше просмотр шкал Н„Н„..., Н, и находят следующий путь к т. д. Если же окажется, что ), )о т. е. путь ), улучшить не удалось, то на шкалах берут густую сетку точек, а также при необходимости измельчают сетку по времени, и снова просматривают шкалы и т. д. Метод локальных вариаций описан. Нетрудно видеть, что этот метод является аналогом метода покоординатного спуска.
Поскольку здесь в переборе участвуют гораздо меньше путей, чем в методе, основанном на соотношениях (6), или методе блуждающих трубок, то ясно, что метод локальных вариаций гораздо экономичнее и поэзо-, 1, 1 ляет увеличить размерность решаемых задач. С другой стороны, нетрудно привести при- 1 1 меры задач, когда этим методом не удается найти даже локально кратчайший путь меж- б2 ду шкалами.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
