Беллман Р. Прикладные задачи динамического программирования (2013) (1246769), страница 36
Текст из файла (страница 36)
Для этих значений Ф и всех (Р!) иэ Р были вычислены стзти- Стяин Я,о(РР Рю) сто(РО Р!) = 707(Р4 Р ) ол (Ро Р!) Таблица 43 Значения Ф для Дт= 80 ОД 0,6 0,8 0,9 1,0 о,з 0,4 0.1 0,2 о,ь 40 40 27 40 27 18 40 40 40 40 18 40 40 40 29 Таблица 4.2 Значения 7", для Фяа 80 Р4 0.6 ОД 0,8 О,У о,ь ол од о,з !.о 6.283 Ь',928 5,204 4,408 злоо 6,072 3',450 5,748 5,143 48ИЗ 3,927 ЗЛ2О 6,497 6.298 5.837 5,243 4,619 з,азь г.бю 6,416 6.164 5,588 4.911 4,! 54 2,750 6,309 5.988 Ь,486 4',890 4,272 ЗРИЬ 2,0ЬО 8' 0 0,1 0,2 0,3 0,4 0,0 0,6 0,7 0,8 0,9 1,О о о,! 0,2 о.з О.4 о,'ь 0,7 о,'3 0 9 1,о 7 3 4 б 7 В 7 7 32 28 6,447 4,674 4,534 4,'ЗН 4.056 з,тз! З.'452 3,!60 2.706 1,715 7 7 10 В 7 8 38 38 37 3? 6,512 5.773 ЬЛОЗ 4,920 4,689 4,340 з,'488 г,48! 1,'3!5 7 8 10 9 40 40 40 39 39 6,539 б,'Нб 5,736 5,422 5,1Н 4,524 3,917 3,021 1',675 8 8 !2 10 40 40 40 40 8 10 14 40 40 21 40 8 1О 40 40 40 40 (ГЛ.
10 Таблица 4.3 мвтоды оптимального поиска Значения Фм для 77?=90 0,4 О,Ь 0,6 О,? 0,8 о,з О,1 0,9 1,О Таблица 44 Значения Р~г для У=90 0,2 о,з 0,4 О,1 6,432 6,236 6,1ОЗ 5,656 5,343 4,Т65 4001 3,529 З,ТГЮ 5.909 Ь,ОЛТ 32И9 5,272 4,156 4,068 При фиксированных р; функции 870(р„р,) почти постоянны относительно Ф (см. таблицу 4.5).
Была вычислена квадратичная регрессия на р, и р, по средним г и 5 (усреднение по М), т. е. по статистикам Т (Ро РТ)=21 7 ггг(ро> Рд 37 79 ! с~ 21 Л (4.36) о ол Ог о,з 0,4 О,'5 О,'6 О.Т 0,8 О,о Т,О 6,591 4,770 47%4 4.450 4, 153 3,867 3,'523 3,217 2,747 1,748 БД57 5,895 5,409 5,034 4,767 4,422 4,134 3'0541 2527 Т,ого 6.690 6.269 5,819 5,508 5,208 4,607 3,988 З,ОБТ 1,702 6,БВТ 6,634 6,437 6,436 Б,ОВЬ 5,943 3,'654 5,396 5,004 4,733 4,'87 1 8,9 1З 3.5 13 2,440 6,813 6.321 Ь,694 Ь,ОЗЗ 4,238 г,'ию 229 19) вычислитзльныв пяоцздувы Эти регрессии рваны (а) г= — 1 076+ 6014ро — 0594ро+ + 8,350р, — 3,43 !р,', о,= 0,956; (Ь) в= 1,017 0 869ро+ 0 013ро+ + 0,388р, — 0,764рЬ о =0,070.
(4.37) Тот факт, что дисперсия в (4,37, Ь) мала и свободный член близок к единице, позволяет нам заключить, что мы имеем очень точное выражение для регрессии. Таблица 45 в Л1О,В; О,11 лм10,Б; о,в1 ол10,2; О,О1 он (о, о1 Однако равенство (4.37, а) не столь удовлетворительно, ибо о, велико. Причина этого в том, что значения А, неустойчивы относительно ?тг прн фиксированных р„рн Вероятно, это частично объясняется тем, что, во-первых, может сушествовать несколько знзчений М, даюших очень близкие значения ?, и несовершенство метода вычислений не позволяет 79 80 81 82 83 84 85 86 8? 88 89 90 91 92 93 94 95 96 97 98 99 1,470 1,471 1,469 1,470 1,468 1,468 1,466 1,467 1,464 1,465 1,462 1,465 1,463 1,464 1,462 1,463 1,461 1,462 1,460 1,461 1,460 1,305 1,275 1,290 1,282 1,292 1,262 1,291 1,268 1,277 1,271 1,281 1,265 1,289 1,274 1,283 1,275 1,283 1,268 1,281 1,270 1,278 0,784 0,786 0,779 0,788 0,781 0,785 0,778 0,786 0,778 0,779 0,772 0,781 0,774 0,777 0,770 0,779 0,773 О,?73 0,767 0,776 0,770 0,570 0,566 0,57! 0,565 0,570 0,564 0,568 0,562 0,566 0,562 Олбб 0,561 0„563 0,561 0,557 0,559 0,555 0,558 0,556 0,557 0,553 230 МВТОДЫ ОПТИМАЛЬНОГО ПОИСКА [ГЛ, Ш выделить наилучшее из них; во-вгорых, может оказаться, что интерполяции, как уже было сказано, не дают удовлетворительного результатз на границах рн! = 1, ры! = 1 и а ' 1 ро!+р1Д= 1.
Первзя из этих неприятностей преодолевается а основными данными, при которых, для многих значениИ ро, рь два весьма далеких друг от друга значения 7а постоянно повторяются и одно из них, вероятно, является корректным. Примеры таких основных данных см. в таблице 4.6. Таблица 4.6 ~А 1О,З; О,З! ал, 1о,о; о,1! ал 1о,а1 о, И 20. РАССМОТРЕНИЕ С ПОМОЩЬЮ ТЕОРИИ ИНШОРМАЦИИ С помощью теории информации можно получить нижнюю границу ~м для вполне оптимзльнон политики. При одном взвешивании мы имеем три возможных исхода: равновесие и два исхода в случае неуравновешивания. Поэтому при таком взвешивании ожидаемая величина получаемой нами информации равна.не более чем ! единице= !оба 3.
79 80 81 82 83 84 85 86 87 88 89 90 9! 92 93 94 95 96 97 98 99 0,1392 О,!250 0,4938 0,134! О,! 325 0,5000 0,494! 0,1279 0,1264 0,5000 0,4944 0,5000 0,1538 0,5000 0,4946 0,5000 0,1368 0,5000 0,4948 0,1327 О,! 313 0,4810 0,4750 0,1 11! 0,4756 0,1084 0,4762 0,1059 0,4767 0,4828 0,4773 0,1124 О,! ! ! 1 0,1099 0,4783 0,1075 0,4787 0,4737 0,4792 0,4742 0,1!22 О,! 111 0,3544 0,4625 0,4691 0,4634 0,3614 0,4643 0,4766 0,4651 0,3678 0,4659 0,3596 0,4667 0,3956 0,4674 0,4624 0,4894 0,4632 0,3750 0,4639 0,4694 0,4646 20] вассчотивнит.
с помощью твовии инвовмации 281 Если фальшивых монег нет, <о знание эгого факта эквиваленпю — 1о6»р„единицам информации. Если имеется одна фзльшивая монетз, то ею может быть любая из АГ монет с вероятностью -'; отсюда суммарная информация, соответствующая определению каждой из этих возможностей, равна — !од»(р<!Аг), так что ожидаемое количество информации, соою<етствующей всем Аг возможностям, раино Р~< А< Р', ( — 1о8»Р — ' '= — Р,<од,Р— ' единиц. Аналогично информация, соответствующая случаю двух фальшивых монет, будет равна Р» Р» "6» А(А — Н Следовательно, нижней границеп для гч служит отношение ожидаемого количества информации к единице информации 1о8» 3: 2 А<(А< — 1) Р= — 1Р<1опар;+Р,1оп»А<+р»!од» 2, (438) »=0 Сравнение этого выражения с нашими результатами подтверждает утверждения (Ь) и (с) в 9 19, но еще раз подчеркивает,что несовершенство интерполяционной про<тедуры дает несколько заниженную оценку для значений уа, по крайней мере для Р»+Р, .
0,6. Например, в таблице 4,4 подчеркнутые значения У<я ниже границы Г, вычисленной по формуле (4.38). Тем не менее мы можем найти некоторсе утешение в том, что получен«ь<е значения у<я означают, что мы имеем хорошую субоптимальную политику, так как эти значения имеют тот же порядок, что и гч.
Из (4.38) можно также заключить, что !о8» Лг -ь (Р, — ' 2Р») 1оба 2, (4.39) что согласуется с утверждением (с) предыдущего параграфа. Когда Р,=!, то выражение обращается в 2 1оп»2=1,26 и, следовательно, утверждение, эквивалентное (а), должно для оптимальной политики принять вид ул<(0, О, 1)-ь 1,26!оп»А». 232 митоды оптимального поиска 1гл. гтг Накотгец, можно показзть, что минимум г при у»в+в»г+ +р, = 1 достигается, когда Рг !г» АГ АГ(А» — 1)12 ' откуда асимптотически р,=1, что подтверждает утверждение !Ь). КОММЕНТАРИИ И БИБЛИОГРАФИЯ Задача нахождения оптимальной процедуры поиска положения абсолютного максимума функции Аг переменных весьма трудна. Укажем, например, следующие статьи: А. Сг $ е а «оп, А веагсп ргоЫеш ап $$»е н-сиЬе, Ргос.
5ушрояа 1п Арр1. Ма!!г., чо1. 1О, 1960, рр. 175 — 178. Р. % о! 1е, ТЬе КАКО Зушров!нш оп Майегпаиса! Ргойгашгпгпп, Ыпеаг Ргойгашшгпй апб Кссеп! Ехгепяопв, ТЬе КАХ$3 Согрога$1оп, Коро«! К-351, !9о9. Далее, когда априори известно, что функция унимодальна, за- дача решена только для функций одной переменной.
Простейшие соображения по этому поводу см. в 9 22 гл. 1 книги «Динамиче- ское программирование», где мы следовали неопубаикованной ста- тье Джонсона. Ьолее серьезное рассмотрение можно найти в статье: Л. К$ е1е г, Зейиепйа1 пнпнпах веагсЬ $ог а шах$шпш, Ргос. Ашег. Май. Зос., чо1.
4, 1953, рр. 502 — 506, и дальнейшие результаты в статье: з. Кге1е г, Орцпннп вецнептга! веагсЬ ап«$ арргояшаггоп шейобв нпггег пнпгшшп гейн!ан1у аввпшрггоп«, й Зос. 1п«$нв!. Аррг. Май., чо1. 5, 1957, рр. 105 — 136. Результаты относительно положения корня монотонной функ- ции содержатся в работе: О.
С сов в апб 3. У ой ивов, Зеггпеп!га1 пнпнпах веагсЬ 1ог а хсго о$ а сопчех 1ппс$1оп, Ма!К. ТаЫев аггд Ойег А1бв то Согпрп!аиоп, чо!. 13, !959, рр, 44 — 5!. Укажем еще статьи: М. За п 6 е1! ив, Оп ап ортппа! веагсЬ ргосебнге, Агпег. Май. Моп!Ыу, чо!. 68, !961, рр. 133 — 134. Н. КоЬЫ па, Зогпе взрос!в о$ йе вецпепиа! беяйп о$ ехрег$- гпептв, Вн1!. Апгег. Ма!5. Зос., чо!. 58, 1952, рр.
527 — 536. А. Очогетгг«у, Оп втосйавггс арргохгша!гоп, Ргос. ТЫ«А Вег- $«е1еу Зушрояпш оп Майе!натка! Зтат!висл апб РгоЬаЬ»1!!у, $$пгчегяту о$ СаИогпга Ргевв, Вегг«е!еу, СаИогп!а, ъо1. 1, 1956, рр. 39 — 56. О. Е. Р. В о х, Ечогнт!опагу орегаггопв, а шетйод 1ог 1псгеашпй гп«$пвтпа! ргобнсичну, АРР1. Вйагч чо1. 6, 1957, рр. 3 — 23. 233 ДОПОЛНИТЕЛЬНАЯ ЛИТЕРАТУРА 1у. й Ы е сч ш а и, 1.осайпи йе псах!шип! ро1п! оп а пи!йода! лиг!асс, Но!ксэ о1 йс Ашсг.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
