Многошаговые игры поиска

Введение 3
Постановка задачи 5
Глава 1. Теоретико-игровая модель простого поиска 6
1.1. Составление модели 6
1.2. Аналитическое решение случая 2 х 2 8
1.3. Программная реализация случая N х к 12
1.4. Результаты программной реализации 18
Глава 2. Теоретико-игровая модель множественного поиска 23
2.1. Единовременный поиск в двух коробках 23
2.2. Единовременный поиск в m коробках 25
2.3. Программная реализация множественного поиска 27
2.4. Результаты программной реализации 32
Выводы 37
Заключение 38
Список литературы 39
Приложение 40
Купить

Поиск различных объектов издревле представляет собой одну из ключевых сторон человеческой активности. В работе [1] процесс поиска определяется как целенаправленное обследование конкретной области пространства для обнаружения находящегося там объекта. Обнаружением объекта можно считать получение информации о его местоположении путем
установления с ним прямого энергетического контакта. Это вполне естественная проблема, с которой мы сталкиваемся на ежедневной основе. К
примеру, перед тем как уходить утром на работу, необходимо собрать определенный набор вещей (ключи, кошелек, документы), которые в свою очередь необходимо локализовать. Их местоположение многообразно, и есть
потребность свести количество времени, затраченное на поиск, к минимуму. Отходя от подобных бытовых проблем, можно расширить список задач
до локализации поврежденных файлов компьютера, разведки месторождений нефти или поиска заблудившегося в лесу человека.
Одним из путей исследования поиска является построение и анализ
математических моделей, отображающих объективные закономерности поиска и позволяющие установить связь между условиями его выполнения и
его результатами, с целью дальнейшего анализа критериев эффективности
поиска. Конечной целью теории поиска является установление оптимального способа ведения поисковых действий применительно к определенной
обстановке и условиям проведения поиска. Выбор оптимального способа
поиска основан на анализе математической модели, соответствующей поисковой ситуации, что позволяет локализовать объект поисков с минимальными затратами имеющихся ресурсов, ввиду их частой ограниченности.
В 1957 году в свет вышла работа Б. О. Купмана [7], в которой задачи поиска рассматривались как задачи оптимального распределения ре-
3сурсов, направленных на поиск, т.е. односторонние задачи оптимизации.
С момента выхода этой работы теория поиска получила широкое распространение, в результате чего появилось большое число публикаций, и стало
общепринятым проводить разделение задач поиска на два класса: поиск
неподвижного и поиск подвижного объектов. Также объект поиска может
рассматриваться как пассивный (не оказывает сопротивления собственному обнаружению) и активный (оказывает сопротивление). Полное и систематическое изложение теории решения поисковых задач было приведено
в работах [3, 6]. Проблематика оптимальности поиска затронута также в
работах [4, 8].
В данной работе речь пойдет о многошаговой задаче поиска неподвижного пассивного объекта в дискретной среде, идеей для рассмотрения
которой послужила статья [5]. Многошаговость задачи обусловлена повторяющейся процедурой поиска.

Купить