автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.18, диссертация на тему:Необходимые условия разрешимости задач гарантированного поиска

МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ им. М. В. ЛОМОНОСОВА ФАКУЛЬТЕТ ВЫЧИСЛИТЕЛЬНОЙ МАТЕМАТИКИ И КИБЕРНЕТИКИ

НЕОБХОДИМЫЕ УСЛОВИЯ РАЗРЕШИМОСТИ ЗАДАЧ ГАРАНТИРОВАННОГО ПОИСКА

05.13.18 — математическое моделирование, численные методы и комплексы программ

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата физико-математических наук

На правах рукописи УДК 517.97

ЛАРИН Петр Михайлович

Москва 2004 г.

ОБЯЗАТЕЛЬНЫЙ I БЕСПЛАТНЫЙ ЭКЗЕМПЛЯР

БЕСПЛАТНЫЙ

Работа выполнена на кафедре общей математики факультета вычислительной математики и кибернетики Московского государственного университета им. М. В. Ломоносова.

Научный руководитель: доктор физико-математических наук,

профессор Е. В. Шикин

Официальные оппоненты: доктор физико-математических наук,

профессор А. П. Фаворский

кандидат физико-математических наук, доцент И. А. Смольникова

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

развития атомной энергетики РАН

Защита диссертации состоится « »..................2004 г. в........

на заседании диссертационного совета К 501.001.07 при Московском государственном университете им. М. В. Ломоносова по адресу: 119992, Москва, Ленинские горы, МГУ, факультет вычислительной математики и кибернетики, ауд..........

С диссертацией можно ознакомиться в библиотеке факультета ВМиК МГУ.

Автореферат разослан « »...................2004 г.

Ученый секретарь диссертационного совета

В. М. Говоров

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность темы. Теория поиска занимается формализацией ясного на интуитивно-бытовом уровне понятия 4поиск» и разработкой соответствующих математических моделей. Приложения этой теории весьма разнообразны: поиск статических объектов (полезных ископаемых, неисправностей), динамических объектов (небесных тел, пропавших людей, электронных сигналов) и т. п. Теория поиска — молодая математическая дисциплина. Первые исследования по поиску были проведены во время Второй мировой войны для военных приложений. Основоположником теории поиска считается американский ученый Б. О. Купман, работавший во время войны в группе по исследованию операций Военно-морского флота США.

В работах Купмана, а также в более поздних работах таких исследователей, как Р. Айзеке, Д. П. Ким, Л. А. Петросян, Н. А. Зенкевич, А. Ю. Гар-наев, О. Хеллман, Ш. Гал и др. прослеживается общий подход, связанный с активным применением в моделировании поискового процесса теории вероятностей. Основным критерием успешности поиска выступает, как правило, вероятность обнаружения, а типичной поисковой задачей является максимизация этой вероятности. Использование теории вероятностей хорошо подходит для описания таких характерных явлений, сопутствующих поисковому процессу, как несовершенство прибора-детектора, не обеспечивающего обнаружения в 100% случаев, или недостаток информации о возможном местоположении разыскиваемого объекта, или повторяемость поисковой ситуации и задача обеспечения успешного поиска в определенной доле повторений. Подобное 4вероятностное» моделирование подходит для значительного числа приложений, однако не исчерпывает их всех.

Альтернативой вероятностному поиску является гарантированный поиск, модель которого и рассматривается в диссертации. Элементы гарантированного поиска встречаются уже у Купмана и Айзекса, но пристальное внимание исследователей он привлек лишь в сравнительно недавнее время.

Рассматриваемая в диссертации модель гарантированного поиска состоит в следующем. Точечные участники поискового процесса, ищущий 5 и уклоняющийся Н, перемещаются по траекториям 5(1) и И@) соответственно. На эти траектории налагаются следующие ограничения:

\Siti)- (1)

I РОС НАЦИОНАЛЬНА»

3 I БИБЛИОТЕКА

1 ;5гяуья£

№)-#(ii)K«>|i2-fil. (2)

О < w < 1 (w = const). (3)

Уклоняющийся считается обнаруженным, если в некоторый момент t* выполняется неравенство

\S(f)-H(t')\^r, (4)

причем радиус обнаружения г является ненулевым (и фиксированным),

г > 0 (г = const). (5)

Последние два условия говорят о том, что с ищущим связан круг обнаружения радиуса г.

Ищущий и уклоняющийся перемещаются в пределах поискового множества Q0, в качестве которого в диссертации рассматриваются в основном евклидова плоскость и ее подмножества. Перед ищущим ставится определенная поисковая задача, например патрулирование некоторого подмножества Q С Qo- Ключевая предпосылка модели гарантированного поиска состоит в том, что эта поисковая задача должна быть решена ищущим при помощи единственной траектории, не зависящей от действий уклоняющегося, при том лишь условии, что траектория уклоняющегося содержится во множестве Л — множестве траекторий-нарушителей. То есть, поставленная задача имеет решение, если

3 S*(t): Vtf(i) en3t*= t*{H): |S*(f) - H(t*)\ s$ r. (6)

Конкретный вид множества зависит от поставленной перед ищущим задачи. Если решается задача патрулирования подмножества Q С Qo, то И состоит из всех траекторий вида (2), проходящих через Q.

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

То, что одной-единственной траекторией-решением S*{t) обнаружение гарантируется для любой траектории уклоняющегося, можно перефразировать

следующим образом: ищущий никак не корректирует свои действия в зависимости от движения уклоняющегося. Напротив, уклоняющийся может использовать какую угодно информацию об ищущем (включая положение и скорость ищущего в текущий и даже будущие моменты времени) и как угодно корректировать свое поведение, пытаться противодействовать обнаружению, но это ему все равно не поможет. Это можно суммировать следующим образом: в модели гарантированного поиска ищущий является полностью неинформированным о действиях уклоняющегося, а уклоняющийся — полностью информированным о действиях ищущего.

Гарантированному поиску можно дать и следующую интерпретацию: в поисковом процессе участвует не один, а несколько уклоняющихся, возможно, бесконечное их число. Можно даже считать, что в каждой точке имеется по уклоняющемуся. Тем не менее ищущий одной траекторией-решением должен обнаружить их всех.

В начале 1990-х для решения задач гарантированного поиска Е. В. Шикин, С. М. Губайдуллин и А. Г. Чхартишвили предложили наглядно-геометрический метод, основанный на использовании переменных информационных множеств. Применяя данный метод, упомянутые исследователи, а также А. А. Скворцов, С. Б. Березин и др. получили целый ряд интересных результатов. Постановки, рассмотренные в их работах, весьма разнообразны, при этом общее направление работ можно охарактеризовать как построение конкретных поисковых траекторий для определенных классов поисковых множеств. В этих работах формулировались достаточные условия разрешимости задач гарантированного поиска, при этом обоснованием достаточных условий выступали построенные траектории.

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

• отсеивать заведомо неразрешимые задачи;

• сравнивать разрывы между необходимыми и имеющимися достаточными условиями.

в) г)

Ряс. 1

Однако, что более важно, необходимые условия связаны с действиями уклоняющегося. Здесь прослеживается прямая аналогия с упомянутой выше связью между достаточными условиями и действиями ищущего. Действительно, пусть выполнены достаточные условия разрешимости. Это означает, что существует траектория 0, гарантирующая обнаружение независимо от траектории уклоняющегося (рис. 1а). При этом действия уклоняющегося остаются в тени. Поэтому отыскание достаточных условий сосредоточивает наше внимание на действиях ищущего и сродни «игре» на его стороне. В случае, когда достаточные условия не выполнены, а необходимые — выполнены, мы ничего не можем сказать об исходе поиска (рис. 16). Пусть теперь необходимые условия не выполнены (рис. 1 в, г). Мы можем выразить этот факт через отрицание утверждения (б):

УЯ ЗЯ(5) € Н : V« - Н{Ь)\ > г. (7)

Как видно, здесь фигурирует функция Н(5), сопоставляющая каждой траектории ищущего 5 траекторию Н уклонения от 5. На рис. 1в показана некоторая траектория ищущего 81 и соответствующая траектория уклонения Б(8\)1 а на рис. 1 г — другая траектория ищущего 5Л и траектория уклоне-

ния от нее И(82). Поскольку уклонение возможно от любой траектории, в тени остаются действия ищущего, а акцент переходит на действия уклоняющегося. Таким образом, отыскание необходимых условий сродни «игре» за уклоняющегося.

Цель работы: получение содержательных необходимых условий разрешимости задач гарантированного поиска. При этом необходимые условия должны быть достаточно общими, т. е. применимыми к широкому классу задач.

Основные результаты.

• Наглядно-геометрический метод, ранее применяемый в основном для получения достаточных условий разрешимости, адаптирован для отыскания необходимых условий. Тем самым подтверждена эффективность данного метода и его потенциал.

• Получены содержательные необходимые условия разрешимости широкого класса задач гарантированного поиска. Указан алгоритм построения траектории уклонения от произвольной траектории ищущего в случае невыполнения данных условий.

• Полученные условия применены к некоторым конкретным поисковым множествам и проведено сравнение с достаточными условиями разрешимости, полученными ранее другими исследователями. На рис. 2 приведен пример подобного сравнения для поиска на единичной сфере. Сравнение производится для значений параметров w и г. Область Л является областью выполнения достаточных условий, полученных А. Г. Чхарти-швили и Е. В. Шикиным. Область С является областью невыполнения необходимых условий, полученных в диссертации. Для области В вопрос остается открытым.

• Построена дискретная модель поискового процесса. При том, что эта модель в основном использовалась как средство доказательства, указано на ее самостоятельную ценность, в особенности в качестве средства моделирования и визуализации поискового процесса на ЭВМ.

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

0.5 1

Рис.2

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

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

Методы исследования. Основным методом исследования является наглядно-геометрический подход, основанный на представлении информации, накапливаемой в процессе поиска, в виде переменных информационных множеств. Использованы также методы математического анализа, вариационного исчисления и геометрии.

Научная новизна. Впервые сформулированы общие необходимые условия разрешимости задач гарантированного поиска.

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

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

Апробация работы. Результаты работы докладывались на семинаре «Задачи динамического поиска» под руководством профессора Е. В. Шикина (факультет ВМиК МГУ), семинаре кафедры оптимального управления под руководством профессоров Н. Л. Григоренко и М. С. Никольского (факультет ВМиК МГУ), семинаре «Геометрия в целом» под руководством профессора И. X. Сабитова, старшего научного сотрудника Э. Р. Розендорна и профессора Е. В. Шикина (мехмат МГУ).

Публикации. Основные результаты диссертации опубликованы в работах

[1-5].

Структура и объем диссертации. Диссертация состоит из вводной главы, двух основных глав и приложения. Общий объем диссертации — 129 страниц. Список литературы включает 38 наименований. В диссертации содержатся 42 иллюстрации. К диссертации прилагается компакт-диск с программным обеспечением.

СОДЕРЖАНИЕ РАБОТЫ

Диссертация состоит из вводной главы, двух основных глав и приложения. Во вводной главе содержится краткий обзор работ и полученных ранее результатов по теме диссертации, описывается используемый математический аппарат и формулируется цель работы.

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

1. Задача патрулирования множества ф С фо состоит в том, что уклоняющийся должен быть гарантированно обнаружен при попадании в Q. При этом игроки могут перемещаться по всей плоскости (ф = №?). Таким образом, множество траекторий-нарушителей состоит из всех траекторий, проходящих через Q и удовлетворяющих условию (2).

2. Задача обнаружения в ограниченном множестве Qo состоит в том, что уклоняющийся, находящийся в Qo, должен быть гарантированно обнаружен. (При этом, согласно определению множества Qo, игроки движутся только в его пределах.) Здесь множество траекторий-нарушителей Н состоит из всех траекторий, лежащих в Qo и удовлетворяющих условию (2).

3. Обобщенная задача патрулирования множества ф С <Зо отличается от задачи патрулирования тем, что Qo представляет собой не всю плоскость, а произвольное плоское множество. Множество траекторий-нарушителей Н состоит из всех траекторий, лежащих в Qo, проходящих через Q и удовлетворяющих условию (2).

Далее во вводной главе излагается аппарат наглядно-геометрического метода. Ключевыми здесь являются понятия упреждающей, остаточной и следящей областей.

Определение. Упреждающей областьюдля траектории ищущего S(t) в момент времени t называется информационное множество, состоящее из всех точек множества Qo, обладающих следующим свойством: если уклоняющийся находится в этой точке, то независимо от его траектории Щ(^ он

обязательно будет обнаружен ищущим в некоторый момент %* = ^ t

при условии, что ищущий будет двигаться по траектории 8^):

.4(5;*) = {хе<2о: УН: НЦ) = 1301: |5(Г) -Я(Г)| <г}. (8)

Определение. Остаточной-областью для траектории ищущего

8^) в момент времени t называется информационное множество, состоящее из всех точек множества Qol обладающих следующим свойством: если уклоняющийся находится в этой точке, то независимо от его траектории И($ он обязательно был обнаружен ищущим в некоторый момент при

условии, что ищущий двигался по траектории 8^):

ЩБ] 1) = {хеС)й'.ЧН-. НЦ) = - Я(Г)| ^ г}. (9)

Определение. Следящей областью называется объединение упре-

ждающей и остаточной областей:

Следящая область представляет собой «полное запретное» множество: находящийся в ней уклоняющийся либо был, либо будет гарантированно обнаружен.

Данные определения позволяют сформулировать следующие критерии разрешимости.

Лемма 1. Траектория S*(t) является решением (обобщенной) задачи патрулирования с параметрами QQ, Q, W, Г тогда и только тогда, когда условие

выполнено в течение всего промежутка времени, на котором требуется обеспечить патрулирование.

Лемма 2. Следующие пять утверждений эквивалентны:

1. Траектория «?*(£), í € [та, тъ], являетсярешениемзадачиобнаружения спараметрамиС^о, го, г;

(10)

(11)

2. Г(5*;4) = Оа V»;

3. в некоторый момент Ц

I -4(S';r0) = Qo. 5. K(S'-,n) = Qo

Во второй главе строятся и обосновываются необходимые условия разрешимости сформулированных во вводной главе задач. Основная идея состоит в том, чтобы показать, что при определенных условиях на параметры задач следящая область, независимо от траектории поиска, не может заполнить все множество Q или QQ (В зависимости от постановки), что согласно приведенным критериям означает неразрешимость поисковой задачи. Т. е. ищутся достаточные условия неразрешимости, отрицание которых даст необходимые условия разрешимости. Из-за неконструктивности приведенного определения следящей области и, как следствие, невозможности работать с ней напрямую сначала строится промежуточное множество T\(S; t) D T(S; t), которое определяется как следящая область траектории в рамках вспомогательной дискретной модели поиска.

Определение. Дискретной моделью поиска называется модель, в которой обнаружение возможно только в фиксированные моменты времени

in = io + пХ, п 6 1

А > 0.

(12)

В остальные моменты обнаружения не происходит, как бы близко ни находились игроки.

Все параметры базовой модели (кроме г), р0, Q, W, переносятся в дискретную модель. Радиус обнаружения в дискретной модели обозначается через р.

Лемма 3. Рассмотрим задачу гарантированного поиска в рамках базовой модели с параметрами ((¿(¡^¡у), г) и задачу того оке типа в рамках дис-кретноймодели с параметрами (<2о) <3> У, р, А). Если выполнено неравенство

(13)

то для произвольной траектории S(^

Ах(5; *) ЭЛ(5;(), Кх(8-,1) Э ЩБ'Л Тл(5; *) Э Тф г) (14) для всех t.

В дальнейшем р полагается равным правой части (13). Данная лемма позволяет переключиться на рассмотрение следящей области в дискретной модели, для которой приводится алгоритм построения. Таким образом, требуется найти условия на параметры задачи, при выполнении которых следящая область произвольной траектории ищущего в дискретной модели не сможет заполнить все множество Q ИЛИ Q.

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

Обозначим через площадь остаточной области некоторой траектории в дискретной модели. В работе строится общая рекуррентная оценка вида

(15)

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

область в базовой модели поиска.

Окончательный результат для задачи патрулирования выглядит следующим образом.

Теорема1. Если площадь Qпревышает величину

/*(«», г)

■ — яг2,

(16)

то задача патрулирования с параметрами Q, w, неразрешима. Здесь и далее

^(го, г) = 2г |ш(7т - агссозш) + л/1 — ги2|. (17)

Соответствующие результаты для задачи обнаружения и обобщенной задачи патрулирования используют новую конструкцию — функцию периметра множества.

Определение. Здесь и далее П обозначает класс плоских множеств с кусочно-гладкой границей. Пусть дано плоское множество Qa ДЛЯ произвольного С (¿о эффективной границей Q называется множество дС} \ д(2о,

а эффективным периметром РЕ{О) множества Q — длина эффективной границы: Ре{0) = \dQ\dQo\. Далее, пусть ц обозначает площадь ОО, конечную или бесконечную. Функция периметра о! множества (2(2 определяется на [0, /х] как

= (18)

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

Теорема 2. Пусть хотя бы для одного элемента 2Ит множества выполнено неравенство Zm > 7гг . Тогда задача обнаружения с параметрами <2о, и>, г, где С?о € П, неразрешима, если

та(19) Теорема 3. Пусть Р((2о; 2) либо неограниченна, либо

£ирР(до;2)>£^). (20)

Тогда, если площадь С} превышает величину

р(СЭо-,г) > г > жг2} - (21)

то обобщенная задача патрулирования с параметрами (¡о, <5, и, г неразрешима (при условии, что указанное множество непусто).

Замечание. В случае существования у Р(С}о; 2) обратной функции хотя бы в некоторой окрестности Р = Р(и),г)/ь) выражение (21) можно заменить на

2 Р

-1 Г£КИ

\ V)

при условии, что

} - 1ГГ2, (22)

(23)

Далее в этой главе показано, во что для конкретных поисковых множеств переходят полученные общие условия. Один из рассмотренных примеров — поиск в круговой области радиуса а.

1. Для разрешимости задачи патрулирования необходимо, чтобы

Я(ц),г)

— г®.

2я-2ш2

2. Для разрешимости задачи обнаружения необходимо, чтобы

^(ад, г)

2ш

(25)

3. Для рассмотрения обобщенной задачи патрулирования нужно задать дополнительный параметр — множество 00, В пределах которого происходит перемещение игроков; пусть это будет плоский угол величины в. Необходимое условие разрешимости имеет вид:

(26)

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

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

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

Теорема 4. Пусть фо 6 П, (}а выпуклое и |(?о| = Пусть {£п} —последовательность многоугольников, вписанных в 00, такая, что

|<2о| — |£„| —> 0, тах тш |х — у\ —> 0. хедЬ„ \edQo

Тогда

НШР(1П;2) = Р(<?о;2), (28)

причем длялюбого £ > 0 сходимость будет равномерной на [е, ц — е].

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

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

Среди рассмотренных в этой главе выводов упомянем о возможности использования одного из инструментов доказательства — дискретной модели поиска — вне контекста диссертации, в частности, для моделирования и визуализации поискового процесса на ЭВМ. В данной главе приводятся рекомендации, связанные с подобным моделированием.

В главе проведено распространение полученных результатов на следующие задачи поиска.

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

2. Поиск в трехмерном пространстве. Используемый метод применен к трехмерному пространству. Рассмотрены все три типа задач и сформулированы необходимые условия разрешимости, подобные

теоремам 1-3. На примере поиска в единичном круге и единичном шаре проведено сравнение необходимых условия поиска в двух- и трехмерном случае и сделан вывод о снижении возможности эффективности поиска при росте размерности.

3. Поиск на сфере. Используемый метод применен к поиску на сфере. Рассмотрены задачи, в которых Qo представляет собой всю сферу: задача патрулирования подмножества Q сферы и задача обнаружения на -всей сфере. Аналоги задачи обнаружения и обобщенной задачи патрулирования, в которых Qo представляло бы подмножество сферы, не рассматривались.

Для полученных результатов было проведено сравнение с имеющимися достаточными условиями разрешимости задачи обнаружения, полученными А. Г. Чхартишвили и Е. В. Шикиным (см. рис. 2). Был сделан вывод, что уже в простейшем случае сферы получение аналитического выражения для правой части общей оценки (15) оказывается чрезвычайно трудоемким, а само выражение — весьма громоздким. В случае использования данного метода для других поверхностей, по-видимому, понадобятся упрощения и загрубления использованного метода, а также программы символьной математики для ЭВМ. Приведены указания по программированию полученных громоздких выражений на ЭВМ. Эти указания связаны с тем, что программирование только па основе формул, без учета ограниченности представления в ЭВМ чисел с плавающей точкой, приводит к неприемлемой потере точности.

Приложением к диссертации является программное обеспечение на компакт-диске и соответствующая документация в тексте работы. Программное обеспечение состоит из двух частей:

• Библиотеки Search па языке программирования C + + , реализующей основные формулы (функции периметра и т. п.) из основной части диссертации, а также алгоритм построения функции периметра выпуклых многоугольников;

• Программы «Периметр» для MS Windows, обеспечивающей построение функции периметра выпуклых многоугольников в интерактивном режиме и графическое представление результатов. Программа использует

библиотеку Search и является пользовательским интерфейсом к ее классам. На рис. 3 показан вид окна программы при вводе многоугольника. Также на рисунке показано, что программа находит и выводит кратчайшую кривую, делящую множество на две части с равными площадями.

* * *

Автор выражает глубокую благодарность своему научному руководителю профессору Е. В. Шикину за постоянное внимание к работе и поддержку, без которых работа вряд ли была бы написана, а также участникам семинара «Задачи динамического поиска» за многочисленные ценные замечания.

РисЗ

РАБОТЫ АВТОРА ПО ТЕМЕ ДИССЕРТАЦИИ

[1] Ларин, П. М. Упреждающая область, порождаемая парой ищущих, и ее визуализация. — МГУ им. М. В. Ломоносова. — М.: 1995. — Деп. в ВИНИТИ 01.11.1995, ДО 291О-В1995. - 44 с.

[2] Ларин, П. М. Следящая область пары отрезков // Фундаментальная и прикладная математика. — 1998. — Т. 4, ДО 2. — С. 559-566.

[3] Ларин, П. М. О невозможности гарантированного поиска в достаточно большой области. — МГУ им. М. В. Ломоносова. — М.: 1998. — Деп. в ВИНИТИ 26.05.1998,ДО 1629-В1998. - 38 с.

[4] Ларин, П. М. О неразрешимости задач гарантированного поиска в достаточно большой области // Вестник Московского университета. Серия 15. Вычислительная математика и кибернетика. — 2000. — ДО 1. — С. 44-47.

[5] Ларин, П. М. Функция периметра выпуклых множеств. — МГУ им. М. В. Ломоносова. - М.: 2004. - Деп. в ВИНИТИ 09.04.2004, ДО 594-В2004. -22 с.

»«газ

Издательство 000 "МАКС Пресс". Лицензия ИД № 00510 от 01.12.99 г. Подписано к печати 22.04.2004 г. Формат 60x90 1/16. Усл.печ.л. 1,0. Тираж 80 экз. Заказ 476. Тел. 939-3890,939-3891,928-1042. Тел./факс 939-3891. 119992, ГСП-2, Москва, Ленинские горы, МГУ им. М.В.Ломоносова.

1. Айзеке Р. Дифференциальные игры. — Пер. с англ. В. И. Аркина и Э. Н. Симаковой. Под ред. М. И. Зеликина. С предисл. Л. С. Понтрягина. — М.: Мир, 1967. — 479 с.

2. Березин С. В. Теоретико-множественные операции в задаче визуализации переменных информационных множеств. — МГУ им. М. В. Ломоносова. М.: 2000. - Деп. в ВИНИТИ 24.01.2000, № 127-В2000. -24 с.

3. Березин С. Б. Информационные множества в задаче динамического поиска объектов с несколькими ищущими // Вестник Московского университета. Серия 15. Вычислительная математика и кибернетика. — 2001. — № 3. — С. 14-18.

4. Березин С. Б. Решение задач динамического поиска в монотонном многоугольнике. — МГУ им. М. В. Ломоносова. — М.: 2002. — Деп. в ВИНИТИ 15.07.2002, № 1330-В2002. 14 с.

5. Березин С. Б. Графический подход к исследованию и решению задач динамического поиска. — Диссертация на соискание ученой степени кандидата физико-математических наук. — МГУ им. М. В. Ломоносова, ф-т ВМиК. — 2002.

6. Губайдулпин С. М., Шикин Е. В. Следящая область на цилиндре и на торе // Вестник Московского университета. Серия 15. Вычислительная математика и кибернетика. — 1992. — Л"« 2. — С. 46-50.

7. Ким Д. П. Методы поиска и преследования подвижных объектов. — М.: Наука. Физматлит, 1989. — 336 с.

8. Ларин П. М. Упреждающая область, порождаемая парой ищущих, и ее визуализация. — МГУ им. М. В. Ломоносова. — М.: 1995. — Деп. в ВИНИТИ 01.11.1995, № 2910-В1995. 44 с.

9. Ларин П. М. Следящая область пары отрезков // Фундаментальная и прикладная математика. — 1998. — Т. 4, № 2. — С. 559-566.

10. Ларин П. М. О невозможности гарантированного поиска в достаточно большой области. — МГУ им. М. В. Ломоносова. — М.: 1998. Деп. в ВИНИТИ 26.05.1998, № 1629-В1998. - 38 с.

11. Ларин П. М. О неразрешимости задач гарантированного поиска в достаточно большой области // Вестник Московского университета. Серия 15. Вычислительная математика и кибернетика. — 2000. — № 1. — С. 44г-47.

12. Ларин П. М. Функция периметра выпуклых множеств. — МГУ им. М. В. Ломоносова. — М.: 2004. — Деп. в ВИНИТИ 09.04.2004, № 594-В2004. 22 с.

13. Петросян Л. А. Дифференциальные игры преследования.— Л.: Изд. ЛГУ, 1977. 221 с.

14. Петросян Л. А., Зенкевич Н. А. Оптимальный поиск в условиях конфликта. — Л.: Изд. ЛГУ, 1987. — 76 с.

15. Петросян Л. А., Гарнаев А. Ю. Игры поиска: Учебное пособие.— СПб.: Изд. СПбГУ, 1992.- 215 с.

16. Петросян Л. А., Зенкевич Н. А., Семина Е. А. Теория игр: Учебное пособие.— М.: Высш. шк., Книжный дом «Университет», 1998.— 304 с.

17. Скворцов А. А. Динамический поиск в выпуклых областях // Фундаментальная и прикладная математика. — 1998. — Т. 4, № 2. — С. 785-790.

18. Скворцов А. А. Траектория патрулирования в задаче динамического поиска.— МГУ им. М. В. Ломоносова. — М.: 1998. — Деп. в ВИНИТИ 13.05.1998, № 1456-В1998. — 38 с.

19. Скворцов А. А. Динамический поиск в трехмерных выпуклых областях // Вестник Московского университета. Серия 15. Вычислительная математика и кибернетика. — 1999. — Л4 3. — С. 20-24.

20. Скворцов А. А. Алгоритмическая реализация теоретико-множественных операций на плоскости. — МГУ им. М. В. Ломоносова. М.: 2000. - Деп. в ВИНИТИ 10.07.2000, № 1915-В2000. -41 с.

21. Скворцов А. А. Динамический поиск в выпуклых областях и его визуализация. — Диссертация на соискание ученой степени кандидата физико-математических наук. — МГУ им. М. В. Ломоносова, ф-т ВМиК. 2000.

22. Хеллман О. Введение в теорию оптимального поиска. — Пер. с англ. Е. М. Столяровой. Под ред. Н. Н. Моисеева. — М.: Наука. Физмат-лит, 1985. — 246 с.

23. Чхартишвили А. Г. Об одном геометрическом свойстве следящей области в задачах поиска // Вестник Московского университета. Серия 1. Математика, механика. — 1992. — N* 3. — С. 7-10.

24. Чхартпишвили А. Г., Шикин Е. В. Метод следящих областей в задачах поиска // Математический сборник. — 1993. — Т. 184, К» 10. — С. 107-134.

25. Чхартпишвили А. Г., Шикин Е. В. Динамические задачи поиска и обнаружения на некоторых замкнутых поверхностях // Дифференциальные уравнения.— 1993. — Т. 29, X» 11. — С. 1948-1957.

26. Чхартишвили А. Г., Шикин Е. В. Следящая область в пространстве Лобачевского // Вестник Московского университета. Серия 1. Математика, механика. — 1994. — № 2. — С. 36-41.

27. Чхартишвили А. Г., Шикин Е. В. Об одном геометрическом подходе к решению динамических игр поиска // Дифференциальные уравнения. — 1994. — Т. 30, Л"» 6. — С. 1097-1098.

28. Чхартишвили А. Г., Шикин Е. В. Динамический поиск объектов, геометрический взгляд на проблему // Фундаментальная и прикладная математика. — 1995. — Т. 1, J0" 4. — С. 827-862.

29. Gal S. Search Games. — New York: Academic Press, 1980. — 216 pp.

30. Koopman В. O. Search and Screening: OEG Report 56. — Washington, D.C.: U.S. Navy Deptartment. Office, Chief of Naval Operations. Operations Evaluation Group, 1946.

31. Koopman В. O. The Theory of Search, Part I: Kinematic Bases // Operations Research. — 1956. — Vol. 4, no. 3. — Pp. 324-346.

32. Koopman В. O. The Theory of Search, Part II: Target Detection // Operations Research. — 1956. — Vol. 4, no. 5. — Pp. 503-531.

33. Koopman В. O. The Theory of Search, Part III: The Optimum Distribution of Searching Effort // Operations Research. — 1957.— Vol. 5, no. 5. — Pp. 613-626.