В этой книге рассматриваются общие принципы и отдельные примеры рационального планирования и анализа экспериментов. Цель заключается в том, чтобы минимизировать экспериментальные и вычислительные затраты.
При всем различии постановок и путей решения таких задач, которые в литературе принято называть' задачами поиска, имеются, однако, и общие методы. Центральный метод, образующий стержень книги, основан на теоретико-информационном подходе, который состоит в том, чтобы ввести подходящее информационное количество и оценивать сверху прирост информации в среднем за один эксперимент или такт вычислений. Если, кроме того, удается построить процедуру, при которой средний прирост информации в точности или асимптотически совпадает с предыдущей верхней оценкой, то задачу можно считать решенной. Правда, такой подход не всегда позволяет получать окончательные результаты, и чтобы точнее оценить сложность задачи, привлекаются дополнительные, более специальные соображения.
Сравнительно элементарные первые две части книги (гл. 1—7) посвящены обзору комбинаторных проблем организации измерений, свободных от ошибок. Значительный интерес представляет систематическое изложение методов построения алфавитных кодов (гл. 4), до сих пор освещавшихся только в зарубежной журнальной литературе, а также содержательный, более современный, чем в третьем томе известной монографии Д. Кнута [91], обзор результатов, касающихся сортировки.
Эти разделы оттенены в третьей части (гл. 9, 10) при разборе аналогичных задач для экспериментов, возмущенных случайными ошибками. Предварительно в гл. 9 дается весьма нестандартное введение в теорию информации, интересное и для специалиста. Оно во многом основано на недавних работах Р. Альсведе, имеющего замечательные достижения в этой области. Следует также отметить исследование каналов с обратной связью и произвольно меняющихся каналов.
Очень интересна и последняя, четвертая часть книги (гл. И —13), где впервые опубликованы элегантные общие
результаты И. Вегенера, подводящие определенный итог развитию исследований по оптимальному распределению затрат при поиске объекта, который может находиться в одном из нескольких мест, когда заданы вероятностные характеристики эффективности поиска. Такими задачами очень много занимались за рубежом (в связи с некоторыми военными приложениями, поиском полезных ископаемых и др.). В литературе на русском языке это, по существу, первое систематическое изложение предмета.
Более скромно и схематично представлены в книге отдельные примеры планирования отсеивающих экспериментов {гл. 6, 7). Чтобы читатель мог составить более развернутое представление об этой важной и увлекательной области (кстати, тесно связанной с теоретико-информационными схемами, изучавшимися Р. Альсведе), было решено при переводе дополнить книгу, с согласия авторов, небольшим обзором полученных здесь результатов.
Отметим, что методы стохастической аппроксимации {гл. 8) в последние годы быстро развивались. Работы по этой теме указанные в книге, в основном относятся к пятидесятым годам, и в настоящее время можно изложить эти вопросы несколько лучше и проще (см., например, Невельсон М. Б. и Хасьмин-ский Р. 3. Стохастическая аппроксимация и рекуррентное оценивание.— М.: Наука, 1972). Однако всегда полезно изучать и классические работы, заложившие фундамент современных исследований.
По объему предполагаемых знаний первые семь глав доступны даже школьнику.- Остальные разделы требуют знакомства с теорией вероятностей в объеме втузовских курсов. Это однако не означает, что материал книги легко усвоить. Несмотря на тщательно продуманное изложение, плотность нового материала (доведенного обычно до численных алгоритмов) настолько велика, что читателю любой квалификации при изучении книги нужно будет затратить значительные усилия.
Книга будет ценным пособием для преподавания комбинаторики и статистики, а также послужит СТИМУЛОМ для развития их приложений,
М. Малютов
ПРЕДИСЛОВИЕ
В течение последних тридцати лет в журналах как теоретического, так и прикладного характера мы все чаще встречаемся с работами, относящимися к теме «поиск». Примечательно, что в качестве проблем поиска рассматриваются задачи самой разнообразной природы и что специалисты различных направлений часто очень слабо осведомлены о результатах, полученных в незнакомых им областях.
В нашей книге делается попытка изложить обширный материал по этой тематике таким образом, чтобы читатель поскорее вошел в круг рассматриваемых вопросов и получил о них возможно более широкое представление.
Наша цель заключается в том, чтобы по-новому взглянуть на наиболее значительные работы в этой области, никоим образом не претендуя, однако, на полноту из-за ограниченности объема книги. Поэтому даже в отношении некоторых работ, заслуживающих подробного рассмотрения, мы ограничились лишь изложением их результатоз. Заинтересованный читатель по прочтении книги окажется в состоянии самостоятельно разобраться в литературе. Специалистам эта книга может быть полезна как справочник.
Все же наша главная цель состоит в том, чтобы основные идеи, методы и результаты, не освещенные до сих пор в книгах, но по своему значению заслуживающие большего распространения, сделать доступными всякому читателю, обладающему готовностью и способностью к формальному мышлению. Вторая часть книги предназначена главным образом этому широкому кругу читателей. В качестве предварительной подготовки здесь требуется лишь основательное знание общего курса математики. Все доказательства проводятся весьма подробно.
Для понимания четвертой части необходимо знание элементарной теории вероятностей. В третьей части предполагается
ОГЛАВЛЕНИЕ
Предисловие редактора перевода ...... : ......... 5
Предисловие.............^.......... 7
г
ЧАСТЬ 1. ВВОДНЫЕ ЗАМЕЧАНИЯ И ОПРЕДЕЛЕНИЯ...... 9
Глава 1. Введение...................... 9
Глава 2, Пример модели поиска................ 12
ЧАСТЬ 2. ПРОБЛЕМА ПОИСКА ДЛЯ ТЕСТОВ, СВОБОДНЫХ ОТ
ОШИБОК..................... 16
Глава 3. Двоичная проблема поиска без ограничений на тесты..... 16
§ 1. Введение................... 16
§ 2. Статические стратспга и разделяющие системы..... 17
§ 3. Случайные статические стратегии.......... 19
§ 4. Последовательные стратегии и префиксные коды .... 23 § 5. Неравенство Крафта и теорема кодирования в отсутствие
шума............ ........ 25
§ б Алгоритм Хаффмана ...... . ...... 31
§ 7. Оптимальные стратегии в случае разномерного распределения на области поиска............ 36
Глава 4. Алфавитные коды и двоичные деревья поиска....... ЗЭ
§ 1. Введение.................. 39
§ 2. Минимизация длины поиска в наименее благоприятном
случае............. ...... 41
§ 3. Хорошие и оптимальные алфавитные коды...... 43
§ 4. Построение оптимальных двоичных деревьев поиска ... 54 § 5. Эффективное построение хороших двоичных деревьев поиска ......... .......... 62
§ 6. Нижние границы для стоимости оптимальных двоичных
деревьев.........- ........ 70
§ 7. Оптимальные двоичные деревья поиска и оптимальные алфавитные коды максимальной стоимости....... 77
Глава 5. Проблемы сортировки................. 83
§ 1. Введение................... 83
§ 2. Сортировка множества из различных элементов . ... 85 § 3. Сортировка множества, в котором не все элементы различны..................... 91
§ 4. Сортировка объединения пары непересекающихся упорядоченных множеств................. 95
§ 5. Проблема медианы.............. по
§ 6. Проблема выбора и проблема разделения.......' 114
§ 7. Гипотеза Яо.................' 117
§ 8. Массовое производство частичных порядков...... ]21
Глава 6. Задачи о взвешивании и геометрические проблемы..... 137
§ 1. Введение.................. . 127
• § 2. Отыскание фальшивой монеты с помощью рычажных весов ...................., 127
§ 3. Отыскание фальшивой монеты с помощью аналитических
весов...................... 130
§ 4. Разделяющая система из множеств не более чем с k элементами ................ .... 132
§ 5. Разделение монет различного веса..........137
Глава 7. Специальные проблемы поиска при использовании тестов, свободных от ошибок..................144
§ 1. Введение................... 144
§ 2. Одна медицинская проблема поиска ......... 144
§ 3. Теория вопросников................ 151
§ 4. Количество имеющихся в распоряжении стратегий . . . 153
ЧАСТЬ 3. ПРОБЛЕМЫ ПОИСКА ПРИ ИСПОЛЬЗОВАНИИ ТЕСТОВ
СО СЛУЧАЙНЫМИ ОШИБКАМИ............157
Глава 8. Стохастическая аппроксимация . -............157
§ 1. Введение................... 157
§ 2. Приближенное решение уравнений по методу Ньютона —
Рафсона............. ...... 158
§ 3. Итерационный метод Мизеса и ПоллачекаТайрингера . . 160
§ 4. Метод Роббинса — Монро стохастической аппроксимации 162
§ 5. Сходимость РМ-метода почти всюду......... 168
§ 6. Аппроксимация точки максимума функции регрессии . . 172
§ 7. Аппроксимационный метод Дворецкого ........ 174
§ 8. Оценки скорости сходимости РМ-процесса...... 182
§ 9. Последовательный минимаксный поиск точки максимума
унимодальной функции .............. 187
Глава 9. Проблема поиска с ответами, подверженными случайным ошибкам, и каналы с обратной связью .... .......392
§ 1. Введение...................I92
§ 2. Равносильная теоретико-информационная проблема , • .197
§ 3. Случай отсутствия ошибок...........• 200
§ 4. Теорема Шеннона о кодировании......... • 203
§ 5. Обратная связь не увеличивает пропускную способность
дискретных каналов без памяти..........205
§ 6." Один метод блокового кодирования; информация как редукция списков . . ..............20д
§ 7. Робастная модель . . ............ . - 2|Ь
§ 8. Байесовский метод ............... ^
§ 9. Одно широкое обобщение «теоремы кодирования в отсутствие шума» и шэнноновской теоремы кодирования;
последовательный метод.............*
§ 10. Гауссовские каналы с обратной связью и стохастическая аппроксимация . t , , ,........,.•**'
Глава 10. Проблемы идентификации и ранжирования ..,-.... 232
§ 1, Введение...................232
§ 2. Модель общей последовательной проблемы множественных решений..................237
§ 3. Верхние оценки для средних потерь ........ 239
§ 4. Условия конечности среднего числа наблюдений (ASN)
и его высших моментов .............242
§ 5. Нижняя оценка для среднего числа наблюдений (ASN)
в проблеме множественных решений........245
§ 6. Теорема о порядке...............247
§ 7. Проблема идентификации (ПИ) и ее алгебраическая
структура...................252
§ 8. Основная последовательная решающая стратегия .... 256
§ 9. Специальные проблемы идентификации.......260
§ 10. Последовательный метод Паульсона для выбора популяции с наибольшим математическим ожиданием среди k нормально распределенных популяций........263
ЧАСТЬ 4. ПРОБЛЕМЫ ПОИСКА С ПРОВЕРКАМИ........268
] Глава 11. Минимизация средней стоимости поиска.........268
( § 1. Введение................... 268
| § 2. Существование успешной стратегии с конечной средней
} стоимостью поиска . . ............. 274
\ § 3. Метод улучшения заданных стратегий........ 276
^ § 4. Существование и построение оптимальных стратегий . . 278
§ 5. Класс псевдостратегий............. . 285
§ 6. Построение почти оптимальных стратегий....... 289
Глава 12, Максимизация вероятности успеха при ограниченных ресурсах 2SO
§ 1. Введение...................290
§ 2. Существование оптимальной распределяющей функции . . 292 § 3. Существуют ли быстрые алгоритмы для решения проблемы? ....................293
§ 4. Оценки для максимальной вероятности успеха и разложение проблемы на подпроблемы...........295
§ 5. Алгоритм построения оптимальной распределяющей функции .....................300
§ 6. Анализ алгоритма................ 302
Глава 13. Обобщенная модель проблемы поиска с проверками.....306
§ 1. Введение...................306
§ 2. Почти-периодические стратегии..........306
§ 3. Оптимальные, стратегии локализации искомых объектов 309 § 4. Дискретные области поиска с бесконечным количеством
элементов...................310
§ 5. Непрерывные проблемы поиска с проверками ..... 310
§ 6. Поиск одного из многих объектов.........316
§ 7. Проблемы поиска со случайными параметрами .... 320
§ 8. Проблемы поиска и остановки...........320
§ 9. Проблема поиска с положительными транспортными затратами ...................326
§ 10. Поиск нестационарного объекта.........327
§ 11. Искать, стараясь не быть обнаруженным......329
§ 12. Поиск на прямых................331
Дололнение. О теоретико-информационных методах в задачах поиска . . 334 Литература........................355
