В данной работе была рассмотрена многошаговая задача поиска неподвижного объекта, спрятанного среди n коробок, за k шагов, в которой обучающийся ищущий стремится минимизировать затраты ресурсов, требуемые на нахождение объекта при условии, что вероятность найти объект при просмотре верной коробки не равна единице. Обучаемость ищущего заключается в запоминании коробок, в которых уже был произведен поиск. Была рассмотрена математическая модель данной задачи для поиска объекта, находящегося в одной из n коробок, за k шагов, основанная на принципе оптимальности Беллмана и состоящая из k рекуррентных уравнений. После был реализован программный алгоритм решения данной задачи для случая n коробок и k шагов на языке программирования C#, после чего был произведен анализ некоторых решений.

Поиск различных объектов издревле представляет собой одну из ключевых сторон человеческой активности. В работе [1] процесс поиска определяется как целенаправленное обследование конкретной области пространства для обнаружения находящегося там объекта. Обнаружением объекта можно считать получение информации о его местоположении путем установления с ним прямого энергетического контакта. Это вполне естественная проблема, с которой мы сталкиваемся на ежедневной основе. К примеру, перед тем как уходить утром на работу, необходимо собрать определенный набор вещей (ключи, кошелек, документы), которые в свою очередь необходимо локализовать. Их местоположение многообразно, и есть потребность свести количество времени, затраченное на поиск, к минимуму. Отходя от подобных бытовых проблем, можно расширить список задач до локализации поврежденных файлов компьютера, разведки месторождений нефти или поиска заблудившегося в лесу человека.

Одним из путей исследования поиска является построение и анализ математических моделей, отображающих объективные закономерности поиска и позволяющие установить связь между условиями его выполнения и его результатами, с целью дальнейшего анализа критериев эффективности поиска.

Полное и систематическое изложение теории решения поисковых задач было приведено в работах [2,4]. Следует заметить, что в мировой литературе по теории игр существует очень много работ в этой области прикладной математики, однако все еще остаются нерешенными задачи даже в самых простых случаях. И здесь вопрос связан со сложностью решения уравнения Беллмана для задач большой размерности.

В данной работе речь пойдет о многошаговой задаче поиска неподвижного пассивного объекта в дискретной среде, идеей для рассмотрения которой послужила статья [3]. Многошаговость задачи обусловлена повторяющейся процедурой поиска.

Постановка задачи

Пусть дано дискретное множество местоположений объекта (в дальнейшем, коробок). Игрок H выбирает коробку и прячет в ней объект. Игрок S пытается обнаружить его. Событие, заключающееся в обнаружении объекта при просмотре верной коробки, не достоверное, т. е. объект может быть не найден, даже если он был в этой коробке. Каждый просмотр коробки требует затрат некоторых ресурсов (например, энергии или времени). Поиск продолжается до исчерпания числа попыток. При нахождении предмета игрок S вознаграждается. Игрок S стремится свести затраты своих ресурсов к минимуму.

В данной работе поставлены следующие задачи:

1. Составить теоретико-игровую модель рассматриваемой задачи с обучающимся ищущим, т. е. ищущий располагает информацией, в каких коробках уже был произведен поиск, и на основе этой информации осуществляет следующий шаг;
2. Обеспечить программную реализацию, способную решать данную задачу для k-шагового поиска объекта в N коробках;
3. Проанализировать решения некоторых задач.

Построение модели

Игрок H выбирает одну из N коробок, пронумерованных от 1 до N, и прячет в ней объект. Игрок S осуществляет поиск объекта в одной из них. Каждый просмотр i-й коробки, может быть осуществлен путем затрат ресурса . Также определим вероятность обнаружить объект в коробке i, при условии, что он в ней находится. Если игрок S находит объект, он получает вознаграждение в виде величины .

Обозначим за смешанную стратегию игрока H. Игрок S имеет представление о стратегии игрока H. Зная его, он стремится пройти через серию поисков с минимальными затратами. Обозначим за минимальные ожидаемые затраты игрока S на n-м шаге поиска и составим соответствующее нашим условиям уравнение Беллмана минимальных ожидаемых затрат :

(1)

где

Вектор отвечает за способность игрока S обучаться в процессе поиска. Осуществляя неудачный поиск в какой-либо коробке, игрок запоминает, что в этой коробке предмета найдено не было и, в связи с этим, меняет приоритеты поиска в сторону остальных коробок. Новые вероятности определяются в соответствии со следующими формулами:

(2)

Строго говоря, вектор являет собой апостериорную вероятность распределения объекта по коробкам при условии, что был произведен неудачный просмотр i-й коробки. Иными словами, вероятность того, что объект находится в i-й коробке после произведенного в ней неудачного поиска, уменьшится, в то время как вероятности нахождения объекта в остальных коробках увеличатся.

Пользуясь уравнениями (1), (2) можно определить минимальные потери игрока S на шаге n, в том случае, если он производил поиски по оптимальной последовательности коробок .

Программная реализация

Программная реализация поставленной задачи была произведена при помощи языка программирования C#. Основную сложность в процессе реализации составила способность к обучению игрока S, т. е. изменение вектора распределения объекта по коробкам в ходе игры. Вследствие этого возникает большое количество различных векторов . К примеру, в задаче поиска объекта среди трех коробок, уже на 3-м шаге будет 27 возможных вариантов выбора коробки (см. Рис. 1). В связи с этим, алгоритм программы оказался чрезвычайно ресурсоемким (запоминание и оперирование количеством переменных), что сильно ограничивает класс доступных решению задач, ввиду недостаточной мощности ЭВМ, на которой производились вычисления.

На вход программы подаются значения: N — число коробок, n — число шагов, t — затраты ресурсов, a — выигрыш игрока S, вектор вероятностей p и вектор x. На выходе получаем значения оптимальных затрат и оптимальный путь поиска по коробкам.

Рис. 1: Поиск среди 3-х коробок

Анализ численных примеров

Пример 1

Рассмотрим задачу за следующими условиями:

В результате работы программы получаем следующие значения:

Произведем вычисления функции минимальных затрат для значений и рассмотрим зависимость прироста функции минимальных затрат от количества шагов игры. Результаты приведены в таблице 1. Как можно видеть, значения функции прироста являются убывающей последовательностью, что говорит о том, что функция минимальных затрат предположительно может быть ограничена сверху, т. е. затраты ресурсов, необходимых на поиск, могут быть ограничены. К сожалению, установить дальнейшее поведение последовательности прироста не удалось, ввиду невозможности решать данную задачу для большего числа шагов (т. к. ресурсоемкость алгоритма превысила имеющуюся). Из имеющихся данных можно выдвинуть два предположения:

1. Функция прироста стремится к нулю, т. е. функция минимальных затрат имеет предел сверху;
2. Функция прироста может принимать отрицательные значения, т. е. функция минимальных затрат начинает убывать после некоторого n.

Пример 2

Рассмотрим задачу за следующими условиями:

В результате работы программы получаем следующие значения:

Отрицательные затраты на поиск будем называть выгодой игрока S. Аналогично примеру 1 произведем вычисления для . Из представленных результатов в таблице 2 можно сделать вывод о том, что игроку S выгодно искать объект дольше, т. к. его выгода от этого только лишь увеличится. Численно установить наличие ограниченности снизу у функции минимальных затрат не удалось ввиду превышения ресурсоемкости. Более того, функция прироста ведет себя неоднозначно (наличие скачков).

Таблица 1

Результаты примера 1

Таблица 2

Результаты примера 2

Пример 3

Рассмотрим задачу за следующими условиями:

В результате работы программы получаем следующие значения:

В данном примере игрок S знает, что объект наиболее вероятно расположен в 4-ой коробке (), однако найти его там довольно сложно (). В результате видно, что игроку S выгодно совсем не обыскивать 4-ю коробку, а отдать предпочтения другим коробкам.

Выводы

В результате анализа численных решений ряда задач были сделаны следующие выводы:

– Игроку S в процессе поисков порой выгодно вовсе игнорировать ту коробку, в которой объект наиболее вероятно находится;

– В данном классе задач существует подкласс, в котором игроку S выгодно искать объект как можно дольше, т. к. его выгода от этого только лишь увеличится. Численно установить наличие предела выгоды в подобных задачах не удалось ввиду недостатка ресурсоемкости ЭВМ;

– В данном классе задач существует подкласс, в котором прирост функции затрат игрока S с ростом шагов является убывающей последовательностью, т. е. затраты могут быть ограничены. Справедливость этого утверждения для большого числа шагов в данных задачах установить не удалось.

Литература:

1. Абчук В. А., Суздаль В. Г. Поиск объектов. М.: Сов. радио, 1977. 336 c.
2. Петросян Л. А, Гарнаев А. Ю. Игры поиска. СПб.: Изд-во СПбГУ, 1992. 216 c.
3. Gal S. A discrete search game // SIAM J. Appl. Math. 1974. Vol 27. No 4, P. 641–648.
4. Garnaev A. Search Games and Other Applications of Game Theory.Heidelberg, N-Y.: Springer, 2000. 145 c.