Беллман Р. Прикладные задачи динамического программирования (2013) (1246769), страница 35
Текст из файла (страница 35)
Ззметим, что множество возможных испытаний гораздо шире, чем в простейшем случае с одной фальшивой монетой. После первого взвешивания мы могли бы выделить из кзждой из трех групп по л, й и А! — 2л монет некоторые подмножества и затем сравнить этот набор с аналогичным набором. Хотя большинство таких испытаний неэффективно и мажорируется более простыми политиками, нелегко определить условия, которые вычеркивали бы такие испытания из числз допустимых, не приводя при этом к чрезмерной громоздкости. Кроме того, априори не ясно, почему некоторые из подобных испытаний не могут окзза|ься полезными. Палее, однзко, чтобы упростить исследование и ускорить вычисления, мы не будем допускать смешанных испытаний, подобных описанному выше. Мы будем предполагазь, что информация, полученная при испытании какой-либо группы монет, может быть использована при опытах над другими группами. 16.
АНАЛИТИЧЕСКАЯ ПОСТАНОВНА ЗАДАЧИ Из сказанного выше следует, что независимо от того, какой информацией мы располагаем перед взвешиванием и каков результат о~дельного взвешивания, мы оказываемся перед лицом нескольких альтернатив. Лопустн» с самого начала, что нам задано начальное распределение вероятностей Р = ]ро р! Рз] где р; — вероятность того, что в наборе из А! монет имеезся точно ! фальшивых, !=О, 1, 2, Допуская, что эти фальшивые монеты распределены равномерно среди А! монет, мы можем непосредственно вычислить соответствуюшие вероятности для любой группы по л монет, взятой из основного набора.
Мы будем рассматривать только политики следующего типа. Из данного набора в А! монет, с которым связано вероятностное распределение р= [рм р„ р,], случайным 222 [гл. ш матоды оптимального пояска образом выбираются две группы по л монет и кладутся на разные чзшки весов. Если они уравновешиваются (это означает, что в каждой из этих групп не более одной фальшивой монеты), то исследуется одна из эгих групп. Если в ней нег фальшивой монеты, то другая группа из д монет также состоит из правильных монет, а остается исследовать группу из (т' — 2л монет. Если в первой группе найдена фальшивая монета, то вторая должна находиться в другой группе из Й монет и нет надобности исследовать М вЂ” 2л оставшихся монет.
Если две первонзчзльные группы не урзвновешивзются, переходим к поискам фальшивой моне~ы в более тяжелой группе. Если в ней обнаружи~ся одна фальшивая монега, то вторая группа не имеет фальшивых монет и мы переходим к поискам второй фальшивой монеты среди Ф вЂ” 2л моне г. Если в первой группе обнаружатся две фальшивые монеты, нет надобности исследовать остальные группы. Прежде чем выписывагь функциональное уравнение, которое мы используем для нахождения оптимального значения К введем следуюшие обозначения: Ул(ра рь ря) — ожидаемое число взвешиваний, требуемых для нахождения всех фальшивых монет среди ЛГ монез при использовании оптимальной политики и заданных р„ рь р„; дл(рм рб л) — вероятность того, что две группы по л монет уравновесягся; Ра(0) — вероятность того, что среди взвешиваемых групп нет фальшивых монег, при условии, что группы уравновесилисгк Ра(!) — вероятность того, что в ка кдой из групп по.л монет имеется по одной фальшивой, при условии, что группы уравновесились; Рп(1) — вероятность того, что в одной из первонзчальных групп из л монет имеегся одна фальшивая, а в другой нет фальшивых, если известно, что группы не уравновеси.
лись; Ргг(2) — вероятность того, что в одной группе две фальшивые монеты, а в другой — ни одной, при условии, что группы не урзвновесились; р(г; а; Г) — вероятность того, что в первой группе из л монет имеется г фальшивых, во вгорой группе из л монет )Л) осповнов ьтнюгпонлльног. и лвпвнив 223 имеется з фальшивых, а среди остальных Лl — 2)г монет, не подвергавшихся взвешиванию, 8 фальшивых; .г'лг(0 р~ р)— = ~~(0, рь ро)— = ая(рь ро)— = дл (ро), Ум(ро, Ро 0)— = )ол (Ро Рь О)= — )ом(ро, Ро): — Лл(ро), Угг(О, 1, О) =— (м(О, 1, О) = (м. 17.
ЗНАЧЕНИЯ ФУННЦИИ Р (г; а; Г) Для по.чучения основного рекуррентного соотнош лезно составнаь таблины значении функции р(г; о; ения по- г) р(1; 1; О)=,, ро 2до 2)о )М вЂ” 2а) р(1; О; 1)= 1Л (Аà — 2)о) в(О; 1; й(л — !) р(2; О; О)=, рь й (й — 1) р(О; 2; О)=, р,, (М вЂ” 2)г) (Лà — 2)о — 1) р(О; О; 2)=, рь (4.26) р(О; 1; О)= — рн л р(1; 0; О)=--рь л М вЂ” 2л Р (О; О; 1) = Ро, р(0; 0; 0)=р,. 18.
ОСНОВНОЕ ФУНКЦИОНАЛЬНОЕ УРАВНЕНИЕ 11рименяя обычным образом принцип оптимальности, получаем основное уравнение для нахождения политики 1го(ра ро ро) =ш)п (1+дую(ро рб 1о) ()оо(ро))+ + г в(о) гл' — ао (Ри Рь Ро ') +)зв (1) о(а) + + (1 — рм (Ро) РЛ Ю) Йа (Р)о)) + Рп (1) йм аа (р 4>)1)о (427) [гл. т 224 мг толы оптин ) ль ног о по(шк х (Л( — 2))) (Л( — 2)г — 1) ~(~ 1(Л(--2)г) (М вЂ” 2Гг — 1)+ 2а-") ~ +р) ( -) р()) — 1 рп) (1, (лг — 2а) (л' — 2а) ())( — 2)( — 1) ~ (Л) — 2)г) (Л( — 2)г — 1) ! +р л(л-1) р(а) 1 р(т) р(а) (,а) = О, [ Р) Л( + Р' Л'(Л вЂ” 1) К Р' Л (4а (л( — 2а) + га (а — 1) )1 +р. ЛГ(И вЂ” 1) (з) 2)((а 1) Д 2а (4)) (М вЂ” 2й) + 2й (а — 1) р'л)(л' — 1)! ')р)и р", п(л) — ц (т) 2(г /[ 2а ~ 4)г (Л( — 2а) )чЛ'/[~" Л' ' РЯ Л)(Л вЂ” 1) [' р(, ) — 1 — р(, р((' = О.
Также Чл(Ро Р)1 И=Ро 'г Р) д + (Л( — 2))) [ (Л'--2)г) (М вЂ” юг — 1) + 2АЯ ~ +"' [ л'(л' — )) (4.30) где ро) — условные вероя)нос)и нрн разлншых возможных результатах взвешивания двух групп по А монет и ~~ р(0= ! при всех у. (4.28) ( Верхний индекс (1) соответствует уравновешиванию двух групп по )г монет. Верхний индекс (2) соответствует случаю, когда известно, что фальшивые монеты находятся среди Л( — 2(т монет. Индекс (3) относится к случаю, когда начальные группы по )( монет не уравновешиваются и (4) — к предпоследнему из случаев, описанных в 3 16. Величины р(О задаются выражениями 19! вычислитвльныв пвоцвдгвы ,(0) =р<н, Р,(1) =рп1, 2А 4А (Лг — 2Л) ' и(') "' Л+РО У(М вЂ” 1) (4.31) Уравнения для О(лч Лл(ре) и О,"л (р,) являются частныии случаяхш уравнения (4.27), именно Лà — 2Л, 2Л Оел =Ш1П ~ 1 + Л, О(Л-2О ~ ЛГ Г(О~ ООЛ(ре) = !П1П (1+ 27Х(ре, 1 — ре, Й) l!Лт 2О(ре ') +(1 — О7,(ре, 1 — рм Д))ЛО ] (4.
32) ул (р|) = ш1 и (1 + дм (О Р 0 А) (ЛО (Рен) + Рл (О) Км — 2О фп) + + Рв(1) О1О] 1 (1 Оуч(0 рр А)) [ЕО(~ФО~)+ Рц(1) ЛЛ 2О(фм)]]. (4.33) !9. ВЫЧИСЛИТЕЛЬНЫЕ ПРОЦЕДУРЫ С помощью уравнении (4.27), (4.32) и (4.33) были получены приближенные значения для Ум и минимизирующие значения /г для Х=1, 2,..., 99 и значении рв взятых с точностью до 0,1. Вычисления проводились итеративным методом на машине Уннвак 1105. Ограниченность обьема памяти вычислительных ООашин, размерность задачи и ограниченность машинного времени сделали несовершенным метод вычисления, так что полученные результаты дают ~олько приближенное представление о природе точного решения. Однако некоторые выводы все же можно сделать. Тот же метод позволи~ нам получить более точные решения при более точных значениях рл когда появятся машины с большим объемом памяти.
Несовершенство результатов имеет ту причину, что сами р'Л принимают континуум значений в интервале (О, 1) при различных значениях р,, ри рм А и (ч'. Иначе говоря, р',л, вычисленные с помощью уравнения (18.3), не равны точно 0,0; 0,1; 0,2; ...; 0,9 или 1,О, а принимают промежуточные 8 Р, Беллмен, С, дреавте мгтоды оптимлльного поиска !гл. щ знзчения, для когорых цриближенныс функциональные иыраже. ния у,(р171, р',», р',и) следует искать интерполяцией из первона- чально полученных выражений для функций У(Р, Р, Р.) где Ро, р!, р,' при имают значения О,о; 0,1; ...; 0,9; 1,0 Эти одиннадцать величин мы далее будел~ именовазь мно- жеством Р и обозначать череа Р(д и Р!д последовзтельные ! Г элементы этого множества, между которыми лежит Р',.н В том случае, когда Р1д+Р1д 3 1, интерполяционная формула для У,(р1т1,Р',д) (здесь Р1д опущено, так как Р1д — '- -1 — Р'Д-'-Р111= 1) имеет вид У.(рм Р)=00'(Ра — Ря)У,(рм Р)+(р — Ря)7.(Р РМ вЂ” Рд+ +001(ро — Ро)1,(|~а Рь)+(Ря — Ра)У,(ра Р~)(Р~ — Р~) (4З4) ж когда Р10+ры=1,1, интерполяционнука формулу сле- дует изменить, оставив только у„(Ра Р~) Уг(ра Р~) и Л(ря Р~).
Очевидно, что приращение 0,1 велико, что порождает неточ- ность вычислений. Однако тот факт, что для получения ум все величины г,(рм Р,), г ( Дг должны хРанитьсЯ в памЯти, делает невозможными вычисления с меньшим интервзлом. Интуитивные соображения подсказываюз также, чго функции у и соответствующие им минимизирующие значения (будем обо- значить их через лм) должны быть разрывны на границах р171 = 1 и Р10+ Р10 = 1, что снова является препятствием к ис- пользованию интерполяционных формул.
Так как количество вычисленных значений Уж(ря, Р,) превышает 6000, то печатающее устройство не может выдазь полностью как эти аначения, так и соответствующие значе- ния лл. В качестве примера полученных данных мы поме- шаем таблицы 4.1 — 4.4, вычисленные для И=80 н 90. Из этих результатов очевидно следующее: (а) Ум (О, О, 1) = 1од, Х, 1 (Ь) 7л (О, О, 1) =шах)м(рм ри Ря), Ул (Р Р Р.) (с) , стремится к некоторому пределу 1оя, Дг пРи Х со и фиксиРованных Р,,рврв Справедливость последнего вывода подтверждается статистическим анализом, проведенным для утГ= 79 —: 99. Мы выбрзли именно эти значения Дг для того, чтобы иметь возможность говорить об зсимптотике функции и одновременно 19! вычислительные НРоцедуРЫ иметь достзточно дзнных для определения тенденции.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
