Беллман Р. Прикладные задачи динамического программирования (2013) (1246769), страница 33
Текст из файла (страница 33)
207 полн ьгнкггин а<еж Нл гггочек. Пусть ̈́— целое число такое, что лгакспжальное значение функции Г (х) лгожевг быть всегда найдено с но,нощью вычисления Е(х) в и нточках и сравненпн этих значений. Пусть К„=юах Н„, (4.13) тогда (4.14) Г(о к аз а тел ь с г в о. Перенумеруем точки в неко~ором порядке числами 1, 2...
Н„. Прежде всего ясно, что К,=-1, К„=2, Ка=4. Возьмем теперь л)3 и предположим, что для й(п мы пмееьн т Кььг Вычислим Е(х) в точках х, и хе Как и при доказательстве теоремы 1, получаем, что х,==К„,+1, ̈́— х, К„н (4.15) откуда Н„( К, . — ' 1 + К„, = (Е„г — 1) + 1 + (Є— 1) = = ~л,г -',.- 1 (4.15) Эго максимальное значение достигается, если х,=Р„, и хя=гч„. Таким образом, мы доказали теорему 2 и получили оптимальную политику поиска. 7. НУЛИ ФУННЦИЙ Ингереспо исследовагь, применимы ли подобные иден для пострсения негода поиска нуля функции на некотором ингернале, если известно„ что онз монотонно убывает на этом ин~ериале.
Оказывается, что для того, чтобы коррекпю сформулировать эту задачу, необходиьга дополнительная информация. Обратимся к следуюшен задаче. лПусть У(х) — непрерывная выпуклая функция на интервале [О, Ц. Ничего более относительно е'(х) не известно. Однако она может быль вычислена в любой точке. Пусть также 7'(О)) О, 1 (Е)(О. фиксируем целое число и ) О. Как с наибольшей точностью определить корень функции у (х) в интервале (О, Е) 208 [гл, гн методы оптимального поиска за и шагов, если каждый шаг состоит в вычислении значения функции 1(х) в любой выбранной точке н сравнении этого значения с ранее полученными?» 8. ФУНКЦИОНАЛЬНЫЕ УРАВНЕНИЯ Уточним задачу, сформулировав ее следующим образом.
Миничизировагь максимальную длину интервала, относигельно козорого после и последовагельных наблюдений можно утверждать, чго он содержиг нуль. Не ограничивая общности, всегда можно рассмагривать кривую вида, изображенного на рис. 55. Здесь 1" (О) = 1, 1(1) = — У, У) О. Так как функция 1 выпукла, ее нуль должен нзходиться в промежугке [О, )г'[, где )й'= 1!(1-'- 1'). Если мы можем сделать ровно одно наблюдение (и= 1), мы выбираем точку х из (О, й') и вычисляем 1(х). Ниже мы покажем, как онтимальным образом выбрать х. Из простых соображений можгу 1 но заключнгь, что нег смысла наблюдать 1 вне интервала, внутри которого находигся нуль функции. Выбрав х и вычислив 1'(х), мы у имеем один из следуюгцих слуРис. 55.
чаев. (Случай, когда 1(х) = О, ко- нечно, наилучший из возможных.) Случай 1. Если 1(х)=е)0, то, соединяя прямой линией известные точки на графике 1, получаем вследсгвие выпуклости функции 7(х), что ее корень находится в интервале (о, %") (рис. 56). Случай 2. Если 1'(х)= — е'(О, то график будет аналогичен изображенному на рис. 57 и корень будет находиться в интервале (шах(0, о"), гй"'). Пусть о"= шах(0, о'). Если х — последняя испытуемая точка (т. е. л = 1), то в соответствии с нашей целью она выбирается так, чтобы минимизировать максимально возможное значение величины шах()й" — Ю, Уйл — о'), ~оп Функцио!Олы!ые уядяне!и!я 11режде чем вдаваться в алгебраические дегали решения для и=1, рассмотрим общий и-шаговыи процесс.
В каждом из случаев, показанных на рис. о5, 56, все существенные данные могуг быть выражены !ерез элементы основного треугольника, зависящие от двух параметров, следующим образом. Обращзясь к рис. 56, мы можем заключить, что графику лежиг выше отрезка п8 и ниже отрезка о%")' (здесь точки У Рис. 56.
Рис. 57. н значения х и Г(х) обозначены одинаковыми буквами). ГГроведем теперь отрезок ЯУ; он может пересекать, а может и не пересекать кривую у=у(х), но если он пересекает кривую в некоторои точке, например в точке Р, то мы можем, не теряя никакой информации, заменигь дугу кривой, лежащую ниже Р)', на РУ. Этот прием не нарушает условия выпуклости и включает худший из возможных случаев, что можно показать, исходя из простых соображении, основанных на наших сведениях о значениях функции на каждом шаге. Таким обрззом, все существенные данные могут быть выражены через элементы треугольника тьЯ)г. Так как задача инвариантна относительно изменения масштабов по горизонтали и вертикали, треугольник оЯУ можно заменить стандартным треугольником, определенным двумя параметрами т' и 8, каи показано на рис. 58. [ГЛ.
1Ч методы оптимального поиска Аналогично во втором случае (рнс. о7) график г' лежит выше о'в' и ниже 1Ж'вп'. Проведем отрезок прямой между 7 У и Я' и заменим часть графика функции г', лежащую ниже этой линии, отрезком прямой от 1 до точки пересечения. Это не повлияег нз выбор следующих знзчений х, так как все эти значения должны 11 быть выбраны из миннмзльных интервалов, содержащих корень функции, что очевидно. Такнч образом, во втором случзе после соответствующего изменения мзсштзРис.
58. ба мы приходим к другому представлению, показанному на рис. 58. Определим теперь функци1о двух переменных Я и Г. Рл(3, 1'1 — минимальная длина интервала, на котором мы можслг гарантировать наличие нуля любой выпуклой 4 уикцииУ,заданной на интервале [О, 1), причем У(О)= 1, (4.17) у 11) = — у( О, если известно, что корень больше 8 и мы должны вычислить функцию в и точках. Если п= О, то мы, очевидно, имеем: 1 Йо (К 1') = — — е 1+К (4.18) Далее, используя принцип оптимальнос1и и учитывзя изменения масштаба, получаем при п э О рекуррен гное соотношение Ал( 1) шах хй„г ',, в'), Шл — Гб 1 — 3 (1 — х) ~~ ~ (4.18) пп'и шах 1 3 х !+к шах О я<1-л11+ Г1 Верхнее и нижнее выражения в фигурных скобках относягся соответственно ко второму и первому случаям. Изменение масштаба производится элементарным образом из подобия треугольников, г!! сю пкппонлльпык хгтвнншя Области изменения переменных Я, 1'соогвегственно будут У)О, 0<" г(1,'(!+ У').
Чтобы привести выражение (4.19) к виду, удобному для вычислений на машине Джонниак, была сделана следующая замена переменных: у 2«(о 1г')=Й«(К 1), (4.20)' + 1.',« откуда я„(а г)=~„(~, Дополнительная замена переменных и и и' сводит систему к следующей; ;„(а )=к — ь; /г х шах !г' (1 — Г) 1Г(! — 1+« — ) гг' — х (1 — х) шах 1! — х ' к'(г' — к)! г' — к'л ) (4.21) 2„(8, Ф')= ш!п шах з«я«м Ф' ««(~' ~1 р.(ь»')= "„, где 0 =Яч-, (гт(1, Затем функции 2 (Я 1к) были вычислены для л=1 2 3, 4 с помощью дискретной аппроксимации с различными се~ками и линейной интерполяции. Минимизируюпгие значения х запоминались, так как они составляют основу нашей опт«мальвой политики, т. е.
ха = =х*(8, Щ есть точка, в которой мы вычисляем неизвестную функцию ~, если известно, что корень лежит в интервале (8, (ь) нашего основного треугольника и делается л вычис- лений нашей функции. Точка х*, конечно, сама находится в основном треугольнике. Чтобы сохранить общность, мы должны о~нес~и наши выклздки к исходному масштабу. Если р„(8, 'г') обозначает отношение, в котором точка х* делит расстояние между Я и 1т', то, очевидно, 1г,ч. ш 212 матовы оптнмхльпого поиска где гк = 1,1(1 †,' У). Теперь легко нычислпгь положение х„' в исходном масштабе и, таким образом, получить один цикл процесса, который мы коротко опишем ниже. Графики функции гс„(0, У) и р„(0, У) для и= 1, 2, 3, 4 читатель найдет ниже (рис.
69, 60). 9. ЧАСТНЫЙ СЛУЧАЙ я=1 Мы начнем настоягпий параграф с нескольких замечаний, пмеюпгих пелью прежде всего оправдание некоторых из предположений, явно или неявно сделанных при выводе написанных выше функциональных уравнений. Мы закончим настоящий параграф краткими пояснениями относительно частного случая и=1, 8=0, когорый может служить прекрасной проверкой правильности расчетов, проведенных па машине Джонниак.
Итак, переходим к замечаниям. 1. Предположим, что мы находимся на некоторой стадии оптимального последовательного минимаксного поиска; нам известны значения функции 1 в нескольких точках, и мы должны указать следующую точку. Пусть а и Ь обозначают ближайшие точки, соответственно справа и слева от минимального интервала (8, гь), который, как нам известно, содержит корень. Тогда при оптимальной процедуре х выбирается из интервала (а, Ь). Чтобы убедиться в этом, нам нужно только показать, что так как неизвестная функция г может быть кусочно-линейной (одна из возможностей) вне (а, Ь), то, очевидно, любое следующее ее вычисление в этой области не добавляет никакой информации относительно характера понедения г внутри (а, Ь), касающейся расположения ее корня, кроме информации, уже даннои величинами а, Ь, г (а), г (Ь), Я и Ж' или любым из предыдущих вычислений.
Аналогичными рассуждениями можно показать, что дальнейшие вычисления следует производить в интервале (8, %'). 2. При рассмотрении случая 2 молчаливо предполагалось, что У„ ( У или, иначе гонора, что прямая 8У имеет отрицательный наклон, как показано на рисунке. Снова на основании некоторых простых соображений можно показать, что наихудшая ситуапия будет в случае, когда ~ монотонна, т.
е. когда график у лежит выше прямой 8У. Именно этим условием определяются границы переменной в в верхней строке 213 слз ый л=1, Я=О 10) функпионзльного уравнения для )сгг Точно такие же сообраакения позволяк~т нам привести функциональное уравнение к довольно просгому виду и, таким образом, с помощью рекуррентных вычислений найти оптимальную «политику». Но тем не менее эти соображения не дают возможности получить оптимзльную процедуру непосредственно из уравнения.
3. По-видимому, функциональное уравнение для 1с„ может быть существенно упрощено, если мы предположим, что максимум в верхней строке уравнения всегда достигается на правом конце интервала изменения )с„(ЯУ). При л = 1 это справедливо. Однако для общего случая это утверждение не доказано и преобразованное уравнение для Фл было поставлено на Т(жонниак в его настоящем виде. Результаты вычислений подтвердили правильность высказанного предположения. 4, )с„(Я, У) — невозрастающая функпия по каждой из переменных 8 и У в отдельности. Чтобы убедиться в этом, например, для первой переменноИ 8, замечаем, что по определению )с„(8, У) при прочих равных условиях информация о том, что корень больше Я', содержится в информации о том, что он больше Я, если Ь"( 8. Тогда на основе дополнигель- ноИ информации при оптимальноИ процедуре мы гарантируем, что чем больше 8, тем короче окончательныИ интервал, т, е.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
