Беллман Р. Прикладные задачи динамического программирования (2013) (1246769), страница 34
Текст из файла (страница 34)
)с„(Я, У) ( )»„(8', У), если Ю ь 8'. Аналогичными рассуждениями можно показать, что )с„(8, ?') не возрастает и по У. 10. СЛУЧАЙ п =1, 5 = 0 Теперь мы вкратце изложим некоторые результаты, полученные для случая и = 1, Я= О. Мы избавим читателя от элементарных, хотя и громоздких алгебраических выкладок, а просто скажем, что определение Я,(0, У) сводится к подстановке А'» ( о 1 ) = 1 1 !+У в правую часть функционального уравнения, что при 8=0 дает относительно простую алгебраическую минимаксную задачу. Подстановка р=х(1+ У) при взятии минимакса дает следующее уравнение для оптимального значения отношения р 214 1гл. ~тг МЕТОДЫ ОПТИМАЛЬНОГО ПОИСКА и переменной У: (рт 2ра 5ра 2р+ 1) УЯ+ 2 (2ра ра Зр+.
1) У+. +(2р — 1)'=0 (4.22) при ограничениях У ) О, 0 ( р ( 1. Так как дискриминант этого квадратного уравнения относительно У равен 8ра, мы легко получаем следующую рациональную параметризацию кривой зависимости р и У: О~Г~га (4.23) У= 1 4т та' Чтобы определить значение Гм заметим, что при У-ьоп предельное полиномиальное уравнение получается, если приравнять к нулю старший коэффициент; р' — 2р' — 5р' — 2р+ 1 = О. (4.24) Это уравнение в интервале (О, 1) имев~ единственный корень, равный 1+2) 2 — У5+4) 2 0282 (425) Ь= 2 Из параметрического представления р получаем, что Га= 1 — ТГ~2Р О 250 Для контроля этого результата заметим, что значение Га является наименьшим положительным корнем знаменателя в параметрическом выражении для У. Графики й,(0, У) и р,(У), полученные в результаге ручного счета по приведенным формулам, хорошо согласуются с результатами, полученными на Джонниак.
К сожалению, однако, выбор недостаточно мелкон сетки из-за ограниченное~и памяти Лжонниак порождает накопленную ошибку, которая вызывает постепенное смешение вверх на концах кривой р. Это обстоятельство учтено, и приводимый здесь график согласуется с теорией. К счастью, кривая й оказалась совершенно нечувствительной к выбору шага сетки. 215 описание пгоцвссл Вычигленнй Заметим, что дополнительную проверку вычислений можно провести при помощи легко получающихся соотношений ~.Ж К')=О, ~.(8, 1)= —,„, которые окззались очень хорошо согласующимися с даннымн, полученными на мзшине )Тжонниак.
11. ОПИСАНИЕ ПРОЦЕССА ВЫЧИСЛЕНИЙ Опишем теперь один цикл вычислительной процедуры. Пусть нам известно, что т (а) = У,) О, у (Ь) = — ?'а, Уз) О, где а(Ь, корень больше 8, и мы можем сделать еще н вычислении функции. Тогдз мы можем утверждать, что корень находится в интервале (8, ?г'), где ?з'=а+(Ь вЂ” а) У Уа + Уа Если л=О, вычисления прекращаются и выписываются значения Я, Ю.
Если и ) О, вычисляется значение функции г(х) при х= 8 †' (11' — 8)р„~~ — ь . Затем, если У (х) = У„) О, полагаем а'= х, Ь' = Ь и 8' = х + (х — а) " . Если же «а Ук у(х)= — У„(0, полагаем а'=а, Ь'=х и, если У ) Ум полагаем 8'=Я, в противном случае Я'=шах(8, х — (Ь вЂ” х) У„ «а Уг! Наконец, ползгзем л'=л — 1. Теперь мы снова имеем ситуацию, когда известно, что ((а')= У„)0, г (Ь')= — Уьч Уа >О, где а'С, Ь', что корень больше Я', и можно сделать еще л' вычислений.
На этом заканчивается цикл вычислений (первоначально 8= а). В следующем параграфе мы на частном примере проиллюстрируем действие этой схемы. Зз меч зине. Приведенная процедурз служит аппроксимацией действительной минимаксиой процедуры. Теоретически 2!6 «гл. ш матовы оптимального поиска корректная процедура вместо выражения р„ †? в фор(Га\ а с8 — а Га> муле для х включала бы р„~ —, — ', функция р„(о, Г) а >Ь вЂ” и' Уа) определена выше. Так как окончательная ф>нкция мало чувствительна к величине о при выборе р„(о; «') в окрестности минимакса, приближение р„(О, Г) = ра(Я, Г) вполне оправдываесся, и мы полагаем р„(?') = — р„(0, Г).
Эта аппроксимация сводит задачу к более удобноп для машинного счета формуле. !2. ЧИСЛЕННЫЙ ПРИМЕР— СРАВНЕНИЕ С ВЫЧИСЛИТЕЛЬНЫМ МЕТОДОМ ДЕЛЕНИЯ ОТРЕЗНА ПОПОЛАМ Предположим, что нам желательно выделить интервал, содержащий нуль некоторой сложно вычисляемоя функссии7, определенной на интервале (О, 1). Нам известно, что У непрерывна, выпукла и что у'(0) = 1, У(1) = — 1. Однако, так как для получения значения эгон гипотетической функции в одноп точке требуется час машинного времени, мы игнорируем тот факт, что на самом деле в нашем примере она задается сравнительно безобидным выражением с (х)=шах ! — 1, (х — —,) ! — — 3 3 ) 1,2,'/' Пусть мы можем сделать три вычисления функции с (х).
ОбУа ращаясь к графику сса(0, Г) при Г= — '= 1, мы видим, что У,= можно найги интервал, содержащий корень и сосгавляющип О,О! длины первоначального интервала, т. е. ингервал длины 0,01. Однако, так как график представляет наихудший из возможных случаев, можно ожидать, чго мы получим гораздо большую точность, как и оказывается на самом деле. Перейдем к вычислениям. Цсскл 1. а=О, Ь=!, «;=1, Га —— 1, о=О, л=3, откуда по нашей формуле ?й"=0,5, и мы локализовали корень на интервале (О, 0,5).
Далее, х = 0+ (0,5 — 0) ра (1) = =0,5 ° 0,148=0,074, и находим, что У(0,074)=0,76839)0, 217 чпслеиныи пРимеР так что а'= 0,074, Ь'= 1, 5'=0,074+ 768 9 =031950 0,074 0,76839 Наконец и'= 2. Цикл 2. (Опускаем штрихи в обозначениях.) а= 0,074, Ь=1, Р;=0,76839, Уь=1, 8=0,31950, и=2, 0,926 0,76839 откуда по нашей формуле %'= 0,074 -'- — ' 1,76839 = 0,47636, и корень находится в интервале (0,31950, 0,47636). Далее х= 0,31950+ 0,15686р! ~ 75889) = 0,319оО+ 0,15686 )С К 0,198 = 0,3о066, и мы находим, что г (0,3о066)= — 004795(0, так что а'=0,074, Ь'=0,35066 и так как У„.( Уа, Наконец, и'= 1. Цпггл 3.
а = 0,074, Ь = 0,35066, У, = 0,76839, Уь —— =0,0479о, 5=0,31950, и=1, откуда по пашен формуле И' = 0,074 — ' ,'" О 76839 ' о 0479 — — 0,33441, «ор!.нь (0,35066 — 0,0741 0,76839 ходится в интервале (0,319оО, 0,3344!). Далее х= 0,31950+ +(0,33441 — 0,31950)р, ( '7,„.„) = 0,31950 + 0,01491 2( ~ р,(0 624) = О 32440, и мы имеем, что 2(0 32440) = О 02535) ) О, так что а'= О 32440, Ь'= О 35066, Ю'=О 32440--,' (0,32440 — О,О ! 41 0,02535 0,76839 — 0,02535 Цшгл 4. а = 0,32440, Ь= 0,35066, У,= 0,02535, Уь —— = 0,04795, 5= 0,33294, и= 0; следовательно, по формуле У'= 0,32'140 —, (0,35066 — 0,32440) 0,02585 0,33348, 0,02585 + 0,04795 и корень находится в интервале (0,33294, 0,33348).
Так как и = О, вычисления прекрашаготся. [гл. ш мятоды оптимального поиска 13. О 6СУЖ ДЕ Н И Е Так как метод нахождения корня путем деления промежутка не требует выпуклости функции, еще до начала вычислений ясно, что корень лежит на интервале (О, 1), после первого измерения — на интервале (О, 0,5), после двух вычисления — на интервале (0,25, 0,5) и, наконец, после третьего — на интервале (0,25, 0,375). Ллины этих интервалов Рис.
59. соответственно равны 1, 0,5, 0,25, 0,125. Сравнивая эти числа с полученными выше О,о, 0,15686, 0,01491, 0,00054, мы видим на этом примере, что наш метод имеет существенные преимущества. В действительности для выпуклой функции с теми же исходныии значениями, что и в нашем примере, мы можем гарантировать, что при трех вычислениях мы получим интервал длины не более чем 0,01, как уже говорили. Сравнение этого числа с 0,125 показывает преимугцество нашего метода (см. рис. 59 и 60), ив задача о вальшивой монвтв 14, 3АдАчА О ФАльшиВОЙ мОнете Широко известна следующая задача.
Среди Л) монет одинакового внешнего вида имеется одна фальшивая. Найти минимальное число взвешиваний на чашечных весах без гирь, достаточное для выделения этой фальшивой монеты. г Рис. 60. Существует много остроумных решении этон задачи, в том числе и имеющих в основе секвенциальные з) процедуры. Весьма странно, что эта задача в случае двух или более фальшивых монет не привлекла достаточного внимания. Значение же се велико, так как оно представляет собой один из простейших примеров секвенциальных задач испытания. Кроме того, эта задача насыщена как комбинаторными *) Си. примечание иа.стр. 2К (Прим. ред.) 220 [гл.
ш матоды оптимлльного поиска. трудностями, так и трудносзямш неизбежно связанными с понятием «информации». Лаже поверхностный анализ вскрывае~ громадную разинцу в уровне сложности задач с одной и двумя монетами. Если мы имеем Аг монет, среди которых, как нам известно, имеется одна фальшивая, и чашечные весы без гирь, то единственная возможная операция состоит яо взвешивании двух групп по л монет, выбранных из наших Аг монет.
Если эти группы уравновешиваются, мы заключаем, что фальшивая монега находится среди оставшихся М вЂ” 2л монет. Если же они не уравновешиваются, то фальшивая монета находится в одной из этих групп. В простейшем случае, когда нам извес~но, что фальшивая монета тяжелее подлинной, независимо от исхода перво~о испытания, мы оказываемся в первоначальной сигуа. ции с меньшим числом люнет.
Зта инвариантность позволяег нам довольно просто применить для решения этой задачи динамическое программирование. Если имеются две или более фальшивых монег, задачз становигся гораздо более сложной, так как после испытания мы не можем сделать столь определенного вывода. В следующем параграфе мы детально исследуем этот случай. Нашей целью будет выработать систематический метод применения динамического программирования для нахождения численного решения, определяющего оптимальную и субоптимальную политику испытаний.
Лля иллюстрации мы приведем несколько численных результатов, полученных на быстродействующей машине. !б. ЗАДАЧА С ДВУМЯ МОНЕТАМИ Перейдем к рассмогрению случая, когда среди г»г монет имеются две фальшивые и известно, что фальшивая монета тяжелее обычной. Рассмотрим возможности, которые могуг представиться при одном взвешивании двух наборов по й монет.
Если эти наборы уравновешиваются, то либо в кзждом из них имеется по фальшивой монете, тогда в группе оставшихся [У вЂ” 2л монет нет фальшивых, либо ни в одной из этих групп нет фальшивой монеты и обе они находятся среди оставшихся Аг — 2л монет. Если два набора по л монет не уравновешиваются, го либо один из них содержит фальшивую монету, тогда другая 16] аналити'паскля постлновкь задачи 22~ находится среди осгаишихся А! — 2л монет, либо один из наборов содержит обе фальшивые монеты и среди оставшихся монет нег фальшивых. Мы видим, что исходная информация развезвляется. При продолжении испытаний, если мы будем счигать допустимой любую возможную прогрзмму испытзний, это рззветвление рззрастзется с угрожзюшей скоростью.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
