Елена александровна сложность задачи о предотвращении столкновений

На правах рукописи

УДК 519.71 Снегова Елена Александровна СЛОЖНОСТЬ ЗАДАЧИ О ПРЕДОТВРАЩЕНИИ СТОЛКНОВЕНИЙ 01.01.09 дискретная математика и математическая кибернетика

АВТОРЕФЕРАТ

диссертации на соискание ученой степени кандидата физико-математических наук

МОСКВА 2012

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

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

Официальные оппоненты: Михалев Александр Александрович доктор физико-математических наук, профессор (ФГБОУ ВПО Московский государственный университет им. М. В. Ломоносова ) Алексиадис Никос Филиппович кандидат физико-математических наук, доцент (ГОУ ВПО Московский энергетический институт (технический университет) )

Ведущая организация: ГОУ ВПО Московский государственный университет приборостроения и информатики

Защита диссертации состоится 16 ноября 2012 г. в 16 ч. 45 м. на заседании диссертационного совета Д 501.001.84 при Московском государственном университете имени М.В.Ломоносова по адресу:

Российская Федерация, 119991, Москва, ГСП-1, Ленинские горы, д.1, Московский государственный университет имени М.В. Ломоносова, Механико-математический факультет, аудитория 14-08.

С диссертацией можно ознакомиться в библиотеке Механико математического факультета МГУ имени М.В. Ломоносова (Главное здание, 14 этаж).

Автореферат разослан 16 октября 2012 г.

Ученый секретарь диссертационного совета Д.501.001.84 при МГУ доктор физико-математических наук, профессор А.О.Иванов

Общая характеристика работы

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

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

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

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

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

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

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

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

Задача о предотвращении столкновений похожа по своей формулировке и методам решения на задачу из области вычислительной геометрии о поиске объекта, ближайшего к запросу, которая состоит в следующем: дано множество S из n объектов, для каждого запроса q требуется найти объект s из S, ближайший к q.

В большей части методов решения задачи поиска объекта, ближайшего к запросу, используются структуры данных, основанные на конструкции R-дерева1 или его модификации – приоритетном R-дереве2.

Задача о поиске объекта, ближайшего к запросу, имеет 4 вариации:

1. Случай статических (неподвижных) объектов и статических (неподвижных) запросов: Preparata и Shamos3, Roussopoulos4, Cheung и Guttman A. R-Trees: A Dynamic Index Structure for Spatial Searching. In Proceedings of the ACM SIGMOD International Conference on Management of Data, pp. 47–57, 1984.

L. Arge, M. de Berg, H. J. Haverkort, and K. Yi. The Priority R-Tree: A Practically Ecient and Worst Case-Optimal R-Tree. Symp. of the ACM Special Interest Group on Management of Data (SIGMOD), Paris, 2004, pages 347–358.

Preparata F.P., Shamos M.I.: Computational geometry: An introduction (texts and monographs in computer science), 5th edn. Springer, Berlin, Heidelberg, New York (1993) Roussopoulos N., Kelley S., and Vincent F. Nearest neighbor queries. In Proceedings of ACM SIGMOD Fu5, Korn и др. 2. Случай статических (неподвижных) запросов и динамических (движущихся) объектов: Berchtold и Ertl7, Kollios и Gunopulos8.

3. Случай динамических (движущихся) запросов и статических (неподвижных) объектов: Song и Roussopoulos9.

4. Случай динамических (движущихся) запросов и динамических (движущихся) объектов наиболее близок к рассматриваемой в данной работе задаче о предотвращении столкновений. Большинство алгоритмов для этого случая основываются на повторных применениях алгоритмов для решения обычной задачи о нахождении ближайшего соседа, что приносит значительные издержки10. Тао и др.11 предложили алгоритм в котором ответ на запрос формируется из трех компонент, а база данных постоянно обновляется. Случай предопределенного движения объектов рассмотрен Attalah’ом12.

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

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

Для наиболее распространенных законов движения объектов, International Conference on Management of Data, San Jose, USA, 1995.

Cheung K. L. and Fu A. W. Enhanced Nearest Neighbour Search on the R-tree. SIGMOD Record, 27(3): 16–21, 1998.

Korn F., Sidiropoulos N., Faloutsos C., Siegel E., and Protopapas Z. Fast nearest neighbor search in medical image databases. In Proceedings of International Conference on Very Large Database, Mumbai, India, 1996.

Berchtold, S., Ertl, B., Keim, D.A., Kriegel, H.P., Seidl, T.: Fast nearest neighbor search in high dimensional space. In: Proceedings of the International Conference on Data Engineering, pp. 209–218 (1998) Kollios, G., Gunopulos, D., Tsotras, V.J.: Nearest neighbor queries in a mobile environment. In: Pro ceedings of the International Workshop on Spatio-Temporal Database Management, pp. 119– 134 (1999) Song Z. and Roussopoulos N. K-Nearest Neighbor Search for Moving Query Point. In Proceedings of the 7th International Symposium on Spatial and Temporal Databases, pp. 79–96, 2001.

Seidl T. and Kriegel H. Optimal multi-step k-nearest neighbor search. In Proceedings of ACM SIGMOD International Conference on Management of Data, Seattle, USA, 1998.

Tao Y., Papadias D., Shen Q. Continuous Nearest Neighbor Search. In VLDB, 2002.

Atallah M. Dynamic Computational Geometry. Proc. 24th Annu. IEEE Sympos. Found. Comput. Sci, 1983.

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

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

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

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

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

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

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

2. Получен критерий сводимости задачи о предотвращении столкновений к задаче о прокалывании.

3. Для случая законов движения, являющихся аналитическими функциями, получен критерий сводимости к одномерным задачам поиска.

4. Разработаны приближенные алгоритмы решения задачи о предотвращении столкновений методом сведения к нескольким одномерным задачам поиска.

5. Для общего случая задачи о предотвращении столкновений разработан алгоритм, имеющий среднее время поиска, вставки и удаления порядка n, где n – размер базы данных.

Результаты работы могут быть Практическая ценность.

использованы в реальных динамических системах управления движением.

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

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

Апробация работы. Результаты работы докладывались на Международной конференции "Современные проблемы математики, механики и их приложений посвященной 70-летию ректора МГУ академика В.А.Садовничего (30 марта - 2 апреля 2009 г., Москва);

XVI и XVII конференциях студентов, аспирантов и молодых ученых "Ломоносов-2009" и "Ломоносов-2010 секция "Математика и механика" (Москва, 2009, 2010);

X Международном семинаре "Дискретная математика и ее приложения" (Москва, 1-5 февраля 2010 г.);

XIV восточно-европейской конференции по достижениям в базах данных и информационных системах "Four teenth East-European Conference on Advances in Databases and Information Systems"(Нови-Сад, Сербия, 2010);

X Международной конференции "Интеллектуальные системы и компьютерные науки" (Москва, 5- декабря 2011 года), а также на семинарах механико-математического факультета МГУ им. М.В.Ломоносова: на семинаре "Теория автоматов" под руководством академика, проф., д.ф-м.н. В.Б. Кудрявцева (2010 2011 г.), неоднократно на семинаре "Вопросы сложности алгоритмов поиска" под руководством проф., д.ф-м.н. Э.Э.Гасанова (2006-2011 гг.), на семинаре "Кибернетика и информатика" под руководством академика, проф., д.ф-м.н. В.Б. Кудрявцева (2011 гг.).

Публикации. По теме диссертации опубликовано 12 печатных работ [1-12].

Структура и объем работы. Диссертация состоит из введения и 5 глав. Объем диссертации 105 стр. Список литературы содержит наименований.

Постановка задачи. Сначала дадим неформальную постановку задачи. Внутри квадрата [, 1 + ] [, 1 + ] прямолинейно движутся точечные объекты, причем запросы появляются на левой стороне прямоугольника [, 1 + ] [0, 1], а объекты – на нижней стороне прямоугольника [0, 1] [, 1 + ].

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

В момент появления каждый объект и каждый запрос сообщают T  d T d  d d  T  d d   dE  dE d   dE  dE  dd  T '$ d  E  dE d   dE d   d 'E ' E d  d  d  T  d E  dE T  d &% d   d d    d d  T  d d  T  d Td   d T d   d d  Рис. 1: Движение объектов и запросов в задаче о предотвращении столкновений. Кругом отмечен пример столкновения объекта и запроса.

системе свои координаты и закон движения, а система фиксирует время его появления.

В задаче требуется для каждого запроса перечислить все объекты, которые появились до него и с которыми он, в течение своего движения внутри прямоугольника [, 1 + ] [0, 1], будет находиться в состоянии опасной близости, то есть на расстоянии по Манхэттену меньшем, чем.

Оси координат расположим вдоль сторон квадрата, таким образом, что у объектов координата по оси x в начальный момент равна и вектор скорости параллелен оси x, а у запросов координата по оси y в начальный момент равна, а вектор скорости параллелен оси y.

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

Схематично движение объектов и запросов в задаче о предотвращении столкновений изображено на рисунке 1.

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

1) параметр (0, 1 ), обозначающий расстояние опасной близости по Манхэттену;

2) дифференцируемая строго возрастающая функция f : R+ [, 1+ ], такая что f (0) =, называемая законом движения объектов;

3) дифференцируемая строго возрастающая функция fq : R+ [, 1+ ], такая что fq (0) =, называемая законом движения запроса;

4) бесконечная последовательность O = {o1, o2,..., on,...}, такая что oi = (ti, yi ), yi [0, 1], а ti – действительные числа, образующие возрастающую последовательность t0 t1 t2... tn..., называемая потоком объектов.

задачей о предотвращении Четверку (f, fq,, O) назовем столкновений.

Введем еще два параметра, которые понадобятся в дальнейшим:

параметр max = f 1 (1 + ), называемый временем движения объектов q и параметр max = fq (1 + ), называемый временем движения запроса.

Предполагаем, что объект oi = (ti, yi ) появляется на границе прямоугольника [, 1 + ] [0, 1] в момент времени ti в точке с координатами (, yi ) и движется по закону движения f параллельно оси x, то есть в момент t [ti, ti + max ] объект oi находится внутри прямоугольника [, 1 + ] [0, 1] в точке с координатами (f (t ti ), yi ).

Запросом q назовем пару (tq, x), где tq R, а x [0, 1].

Предполагаем, что запрос q = (tq, x) появляется на границе прямоугольника [0, 1] [, 1 + ] в момент времени tq в точке с координатами (x, ) и движется по закону движения fq параллельно q оси y, то есть в момент t [tq, tq + max ] запрос q находится внутри прямоугольника [0, 1] [, 1 + ] в точке с координатами (x, fq (t tq )).

Скажем, что объект oi = (ti, yi ) и запрос q = (tq, x) сталкиваются, если существует момент времени t R, такой что |f (tti )x|+|yi fq (ttq )|.

В задаче требуется для произвольного запроса перечислить все объекты из потока O, которые появились до него и с которыми он столкнется в процессе своего движения, то есть ответом на запрос q = (tq, x) при расстоянии опасной близости является множество J(f, fq,, O, q) = {oi = (ti, yi ) O| ti tq и t :

|f (t ti ) x| + |yi fq (t tq )| }.

Библиотекой V (t) в момент времени t назовем множество объектов из потока O, находящихся внутри прямоугольника [, 1 + ] [0, 1] в момент времени t, т.е. V (t) = {oi = (ti, yi ) O : ti t ti + max }.

Введем последовательность, объединяющую моменты появления и исчезновения объектов {si } = {ti } {ti + max } и заметим, что i=1 i=1 i= по сути V (t) – это кусочно-постоянная функция V : R 2O, меняющаяся в моменты появления и исчезновения объектов si, i N.

Решать задачу (f, fq,, O) в приведенной выше постановке не представляется возможным, поскольку множество O бесконечное и невозможно его целиком хранить в базе данных.

Допустим, что в каждый момент времени t имеются данные не про все множество O, а про его "текущее" подмножество V (t).

Введем множество ответа на запрос q = (tq, x) при библиотеке V (t) в момент времени t:

J(f, fq,, V (t), q) = = {oi = (ti, yi ) V (t)| t : |f (t ti ) x| + |yi fq (t tq )| } и заметим, что при tq [max si, min si ] J(f, fq,, O, q) = J(f, fq,, V (t), q).

si t si t Таким образом, в каждый момент времени t имеется информация о библиотеке V (t) и содержательно задача о предотвращении столкновений состоит из двух компонент:

1. Обновление библиотеки V (t) в моменты времени si, i N. В каждый момент ti, i N, происходит добавление объекта oi = (ti, yi ) в "текущую" библиотеку, а в каждый момент ti + max, i N, происходит удаление объекта oi = (ti, yi ) из "текущей" библиотеки.

2. Поиск ответа на запрос q = (tq, x) в библиотеке V (t), при условии, что tq [max si, min si ] 13.

si t si t Задачу о предотвращении столкновений в момент времени t будем обозначать как четверку (f, fq,, V (t)).

Алгоритм решения задачи о предотвращении столкновений.

Мы будем рассматривать задачу о предотвращении столкновений как динамическую задачу поиска. Обычно предполагается, что алгоритмы решения динамических задач поиска содержат в своей памяти базу данных, представленную некоторой структурой. Как правило структуры данных описываются на языке графов, например, на языке информационных графов14. При этом алгоритм решения динамических задач поиска воспринимается как совокупность трех процедур, работающих над этой структурой данных: процедуры поиска, процедуры вставки и процедуры удаления. Процедура поиска основная и позволяет решать главную задачу выбирать в базе данных объекты, удовлетворяющие запросу. Процедуры вставки и удаления служат для вставки в базу данных новых объектов и и удаления из базы имеющихся объектов, каждая из этих процедур изменяет Заметим, что t также принадлежит отрезку [max si, min si ], то есть в библиотеку V (t) могут si t si t поступать запросы с моментом появления равным t или близким к t Гасанов Э. Э., Кудрявцев В.Б. Теория хранения и поиска информации. М.: ФИЗМАТЛИТ, 2002.

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

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

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

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

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

Чтобы иметь возможность преобразовывать графы, будем считать, что множество элементарных операций содержит операции вставки и удаления вершин и ребер графа, операции изменения и вычисления нагрузок вершин и ребер, а также некоторые более сложные составные операции, каждая из которых выполняет некоторое локальное преобразование графа и имеет константную сложность, где опять же в качестве единицы измерения выступают операции сравнения. Примерами таких операций могут служить операции операции склейки и переброски вершин. Если неформально описывать эти операции, то операция переброски может быть применена к внутренней вершине f графа, имеющей четырех сыновей. Для операции переброски образуем новую вершину g. Два левых сына оставим сыновьями f, а два правых переделаем в сыновей g. Затем сделаем g братом f, сделав его сыном отца f. Операция склейки может быть применена к двум вершинам, имеющим общего родителя. Она заключается в простом объединении (склеивании) этих двух вершин.

Пусть O = {o1 = (t1, y1 ), o2 = (t2, y2 ),..., oi = (ti, yi ),...} произвольный поток объектов и {si } = {ti } {ti + max } i=1 i=1 i= последовательность, объединяющая моменты появления и исчезновения объектов. Алгоритмом решения задачи о предотвращении столкновений (f, fq,, O) будем называть совокупность трех процедур поиска, вставки и удаления, таких, что для любого i N если вызывать процедуру вставки во все моменты tj si, а процедуру удаления во все моменты tj + max si для объектов oj, то для любого запроса q = (tq, x) такого, что si tq si+1, процедура поиска в ответ будет выдавать множество J(f, fq,, V (tq ), q).

Пусть A – алгоритм, решающий задачу о предотвращении столкновений. Тогда сложность поиска по алгоритму A на запросе q при библиотеке V (t) есть величина, равная сумме сложностей всех элементарных операций, выполненных процедурой поиска при подаче на ее вход запроса q при условии, что на момент поиска структура данных соответствовала библиотеке V (t). Сложность поиска всегда включает в себя сложность перечисления ответа, которая как минимум равна длине ответа на запрос. Поэтому в перечислительных задачах поиска как правило исследуют сложность поиска без перечисления ответа.

Сложностью поиска без перечисления ответа на запросе q назовем величину, равную сложности на запросе q минус мощность ответа на запрос q. Обозначим эту сложность TA (f, fq,, q, V (t)).

Сложность вставки по алгоритму A объекта o в библиотеку V (t) обозначим SA (f, fq,, o, V (t)) и будем считать равной сумме сложностей всех элементарных операций, выполненных процедурой вставки при подаче на ее вход объекта o при условии, что на момент вставки структура данных соответствовала библиотеке V (t).

Сложность удаления по алгоритму A объекта o из библиотеки V (t) обозначим RA (f, fq,, o, V (t)) и будем считать равной сумме сложностей всех элементарных операций, выполненных процедурой удаления при подаче на ее вход объекта o при условии, что на момент удаления структура данных соответствовала библиотеке V (t).

Объемом алгоритма A для библиотеки V (t) назовем число ребер в графе, описывающем структуре данных, соответствующей библиотеке V (t), и обозначим QA (f, fq,, V (t)).

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

В первой главе приводится критерий сводимости задачи о предотвращении столкновений к одномерной задаче интервального поиска и алгоритм решения задачи в этом случае.

Задачей одномерного интервального поиска назовем пару (I, Z), где библиотека Z конечное подмножество множества действительных чисел R, а множество запросов I есть множество всех интервалов с концами из R. Содержательно эта задача состоит в том, чтобы для произвольного запроса p I перечислить все те и только те точки из Z, которые попадают в интервал p.

Ответ на запрос p I при библиотеке Z в задаче одномерного интервального поиска есть множество J(p, Z) = {z Z : z p}.

Будем говорить, что задача о предотвращении столкновений (f, fq,, V (t)) сводится с задаче одномерного интервального поиска, если существуют такие отображения, 1, 2 : R [0, 1] R, что для любой библиотеки V (t), любого запроса q = (tq, x) и любого объекта o V (t) верно o J(f, fq,, V (t), q) (o) J([1 (q), 2 (q)], Z), где Z = {(o) : o V (t)}.

Обозначим:

FL (x, y) = min (fq (y + ) f 1 (x + )), [0,] max (fq (y + + ) f 1 (x + )), FR (x, y) = [,0] XR = {x [0, 1] : y FR (x, y) 0}, XL = {x [0, 1] : y FL (x, y) 0}, YL = {y [0, 1] : x FL (x, y) 0}.

Теорема 1. Задача о предотвращении столкновений (f, fq,, V (t)) сводится к задаче одномерного интервального поиска тогда и только тогда, когда существуют функции, L, R : [0, 1] R такие, что для любой пары (x, y), для которой выполнено условие FL (x, y) 0, верно, что FL (x, y) = (y) + L (x), (1) а для любой пары (x, y), такой, что FR (x, y) 0, верно, что FR (x, y) = (y) + R (x). (2) При этом если выполнены условия (1) и (2) и если y YL, (y), (y) = если y YL, FL (0, 1), если x XR, R (x), R (x) = если x XR, FR (0, 1), если x XL, L (x), L (x) = если x XL, FL (0, 1), то функции сведения (, 1, 2 ) имеют вид (ti, yi ) = ti (yi ), 1 (tq, x) = tq + L (x), 2 (tq, x) = tq + R (x).

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

Теорема 2. Для алгоритма A1, решающего задачу о предотвращении столкновений сведением к задаче одномерного (f, fq,, V (t)) интервального поиска верно, что для сложности поиска ответа на любой запрос q, вставки любого объекта-данного o, удаления любого объекта-данного o по алгоритму A1, и для объема алгоритма A выполнены соответственно соотношения c log2 |V |, TA1 (f, fq,, V (t), q) c log2 |V |, SA1 (f, fq,, V (t), o) c log2 |V |, RA1 (f, fq,, V (t), o) c|V |, QA1 (f, fq,, V (t)) константа не зависящая от |V |.

где c Во второй главе приводится критерий сводимости задачи о предотвращении столкновений к одномерной задаче о прокалывании.

Задачей о прокалывании назовем пару (R, Z), где библиотека Z есть конечное множество всех интервалов с концами из R, a R есть множество всех действительных чисел. Содержательно эта задача состоит в том, чтобы для произвольного запроса p R перечислить все те и только те отрезки из Z, которые содержат p.

Ответ на запрос p R при библиотеке Z в задаче о прокалывании есть множество J(p, Z) = {z Z : p z}.

Будем говорить, что задача о предотвращении столкновений (f, fq,, V (t)) сводится с задаче о прокалывании, если существуют такие отображения, 1, 2 : R [0, 1] R, что для любой библиотеки V (t), любого запроса q = (tq, x) и любого объекта o V верно o J(f, fq,, V, q) [1 (o), 2 (o)] J((q), Z), где Z = {[1 (o), 2 (o)] : o V }.

Тройку (, 1, 2 ) будем называть функциями сведения.

Аналогично критерию сводимости к задаче одномерного интервального поиска обозначим YR = {y [0, 1] : x FR (x, y) 0}, YL = {y [0, 1] : x FL (x, y) 0}, XL = {x [0, 1] : y FL (x, y) 0}.

Теорема 3. Задача о предотвращении столкновений (f, fq,, V (t)) сводится к задаче о прокалывании тогда и только тогда, когда существуют функции, L, R : [0, 1] R такие, что для любой пары (x, y), для которой выполнено условие FL (x, y) 0, верно, что FL (x, y) = (x) + L (y), (3) а для любой пары (x, y), такой, что FR (x, y) 0, верно, что FR (x, y) = (x) + R (y). (4) При этом если выполнены условия (3) и (4) и если x XL, (x), (x) = если x XL, FL (0, 1), если y YR, R (y), R (y) = если y YR, FR (0, 1), если y YL, L (y), L (y) = если y YL, FL (0, 1), то функции сведения (, 1, 2 ) имеют вид (tq, x) = tq + (x), 1 (ti, yi ) = ti R (yi ), 2 (ti, yi ) = ti L (yi ).

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

Теорема 4. Пусть законы движения f, fq – аналитические функции.

Тогда задача о предотвращении столкновений (f, fq,, V (t)) сводится к задаче одномерного интервального поиска или задаче о прокалывании тогда и только тогда, когда выполнено хотя бы одно из четырех условий Условие 1.

1. Если (x, y) [, 1 + ] [0, 1] : fq (y) f 1 (x) 0, то (fq (y)) (f 1 (x)) ;

2. Если FL (x, 0) 0, то arg min FL (x, 0, );

[0,] 0, то arg max FL (x, 1, );

3. Если FR (x, 1) [,0] 4. Если (x, y) [0, 2] [0, 1] : FR (x, y) 0, то arg max FR (x, y, );

[,0] 5. Если (x, y) [0, ] [0, 1] : FL (x, y) 0, то arg min FL (x, y, );

[0,] Условие 2.

1. Если (x, y) [0, 1] [, 1 ] : fq (y) f 1 (x) 0, то (fq (y)) (f 1 (x)) ;

2. Если FL (0, y) 0, то 0 arg min FL (0, y, );

[0,] 0, то 0 arg max FR (1, y, );

3. Если FR (1, y) [,0] 4. Если (x, y) [0, 1] [1, 1] : FR (x, y) 0, то 0 arg max FR (x, y, );

[,0] 5. Если (x, y) [0, 1] [1, 1] : FL (x, y) 0, то 0 arg min FL (x, y, );

[0,] Условие 3. f – линейный многочлен;

Условие 4. fq – линейный многочлен.

При этом, в случаях 1, 3 задача о предотвращении столкновений (f, fq,, V (t)) сводится к задаче о прокалывании, а в случаях 2, 4 к задаче одномерного интервального поиска.

В четвертой главе рассматриваются алгоритмы сокращения перебора.

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

Задачей о пересечении назовем пару (I, Z), где библиотека Z есть конечное множество отрезков с концам из множества действительных чисел, a множество запросов I есть множество всех отрезков с концами из множества действительных чисел. Содержательно эта задача состоит в том, чтобы для произвольного запроса p I перечислить все те и только те отрезки из Z, которые пересекаются с отрезком p.

Ответ на запрос p I при библиотеке Z в задаче о пересечении есть множество J(p, Z) = {z Z : z p = }.

Будем говорить, что задача о предотвращении столкновений (f, fq,, V (t)) накрывается задачей о пересечении, если существуют такие отображения 1, 2, 3, 3 : R [0, 1] R, что для любой библиотеки V (t), любого запроса q = (tq, x) и любого объекта o V верно o J(f, fq,, V, q) [1 (o), 2 (o)] J([3 (q), 4 (q)], Z), где Z = {[1 (o), 2 (o)] : o V }.

Четверку (1, 2, 3, 4 ) будем называть функциями сведения.

Предположим, что поток объектов O = {o1 = (t1, y1 ), o2 = (t2, y2 ),..., oi = (ti, yi ),...} представляет собой случайный процесс такой, что моменты появления объектов ti образуют пуассоновский поток с параметром, а координаты появления yi имеют равномерное и независимое распределение на отрезке [0, 1] для каждого i. Такие потоки объектов будем называть пуассоновскими потоками объектов. Пусть V (t) случайная библиотека в момент времени t, порожденная пуассоновским потоком объектов O, т.е. V (t) = {oi = (ti, yi ) O : ti t ti + max.} Средней сложностью поиска по алгоритму A на запросе q для расстояния опасной близости назовем математическое ожидание по библиотеке от сложности поиска: TA (f, fq,,, q, t) = MV TA (f, fq,, V (t), q), где математическое ожидание берется по всем случайным библиотекам V (t), порожденными пуассоновскими потоками объектов с параметром, а TA (f, fq,, V (t), q) сложность поиска по алгоритму A на запросе q.

Поскольку пуассоновский поток объектов является стационарным, то для достаточно больших t, а именно t · max, число объектов в библиотеке не зависит от t и приблизительно равно · max. Отсюда в частности следует, что величина TA (f, fq,,, q, t) для достаточно больших t не зависит от t, и поэтому будем писать TA (f, fq,,, q).

Будем писать f (n) = O(g(n)), если существуют такие константы C1 и C2, что для любых n N выполнено C1 · g(n) f (n) C2 · g(n). Введем следующие обозначения для задачи о предотвращении столкновений:

f (y), vmax = f (y), vmin = min max y[,1+] y[,1+] q q vmin = min fq (y), vmax = max fq (y).

y[,1+] y[,1+] Будем предполагать, что задача о пересечении может быть решена со средней сложностью IS(max ), затрачивая объем памяти порядка O(max ), где max есть среднее число отрезков в библиотеке Z, совпадающее со средним числом объектов в области наблюдения. В этих предположениях построен алгоритм A2, который решает задачу о предотвращении столкновений (f, fq,, V (t)).

Теорема 5. Средняя сложность алгоритма A2, решающего задачу о предотвращении столкновений (f, fq,, V (t)) сведением к задаче о пересечении, на любом запросе q удовлетворяет неравенствам:

1 1 1 TA2 (f, fq,,, q) IS(max ) 2( + ) 2( + q ), q vmax vmax vmin vmin а объем равен QA2 (f, fq,, V (t)) = O(max ).

Будем говорить, что задача о предотвращении столкновений (f, fq,, V (t)) накрывается двумя задачами одномерного интервального поиска и одной задачей о прокалывании, если существуют отображения 1, 2, 3, 4, 5, 6, 7, 8, 9 : R [0, 1] R, что для любой библиотеки V (t), любого запроса q = (tq, x) и любого объекта o V верно, что если o J(f, fq,, V, q), то либо 1 (o) J([2 (q), 3 (q)], Z1 ), где Z1 = {1 (o) : o V }, либо 4 (o) J([5 (q), 6 (q)], Z2 ), где Z2 = {4 (o) : o V }, либо [7 (o), 8 (o)] J([9 (q), Z3 ), где Z3 = {[7 (o), 8 (o)] : o V }.

Будем предполагать, что задача о прокалывании (I2, Z2 ) может быть решена со средней сложностью DO(max ), где max есть среднее число отрезков в библиотеке Z2, совпадающее со средним числом объектов в области наблюдения. В этих предположениях построен алгоритм A3,который решает задачу о предотвращении столкновений (f, fq,, V (t)).

Теорема 6. Средняя сложность алгоритма A3, решающего задачу о предотвращении столкновений (f, fq,, V (t)) сведением к двум задачам одномерного интервального поиска и одной задаче о прокалывании, на любом запросе q удовлетворяет неравенствам:

+ O(log2 (max )) + DO(max ) TA3 (f, fq,,, q) vmax + O(log2 (max )) + DO(max ), vmin а объем равен QA3 (f, fq,, V (t)) = O(max ).

В четвертой главе также построен алгоритм A4,который решает задачу о предотвращении столкновений (f, fq,, V (t)) сведением к двум задачам о прокалывании и одной задаче одномерного интервального поиска.

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

Пусть vmin, vmax, vmin vmax, некоторые положительные числа, Fvmin,vmax множество дифференцируемых строго возрастающих функций f : R+ [, 1+], таких что f (0) =, и vmin f ( ) vmax для любого [0, f 1 (1 + )]. Пусть на Fvmin,vmax задано некоторое вероятностное пространство.

Будем считать, что у каждого объекта oi есть свой собственный закон движения fi Fvmin,vmax, и объект в этом случае представляет из себя тройку oi = (fi, ti, yi ), при этом как и ранее будем считать, что поток объектов O = {o1 = (f1, t1, y1 ), o2 = (f2, t2, y2 ),..., oi = (fi, ti, yi ),...} представляет собой случайный процесс такой, что моменты появления объектов ti образуют пуассоновский поток с параметром, координаты появления yi имеют равномерное и независимое распределение на отрезке [0, 1] для каждого i, а законы движения fi выбираются в соответствии с распределением, заданным на Fvmin,vmax, т.е. поток объектов является пуассоновским потоком. Пусть V (t) случайная библиотека в момент времени t, порожденная пуассоновским потоком объектов O, т.е. V (t) = {oi = (fi, ti, yi ) O : ti t ti + fi1 (1 + )}.

Поскольку пуассоновский поток объектов является стационарным, то для достаточно больших t, а именно t · (1 + 2)/vmin, среднее число объектов в библиотеке не зависит от t. Отсюда в частности следует, что все сложностные характеристики алгоритмов для достаточно больших t не будут зависеть от t, и поэтому параметр t мы далее будем опускать, считая, что t достаточно большое.

Закон движения запроса fq также не известен заранее и принадлежит множеству Fvmin,vmax. Запрос в этом случае представляет из себя тройку q = (fq, tq, x). Как и ранее, задача о предотвращении столкновений состоит в том чтобы для произвольного, но зафиксированного пуассоновского потока объектов O и произвольного запроса q = (fq, tq, x) найти в библиотеке V (tq ) все объекты, которые в процессе своего движения окажутся на расстоянии по Манхэттену не более чем от запроса q. В такой формулировке задачу о предотвращении столкновений обозначим как пятерку (vmin, vmax,,, O).

Пусть имеется некоторый алгоритм A решения задачи о предотвращении столкновений и пусть LA (V,...) некоторая сложностная характеристика алгоритма A для библиотеки V. Тогда обозначим LA (vmin, vmax,,,...) = MV LA (V,...), где математическое ожидание берется по всем случайным библиотекам V, порожденными пуассоновскими потоками объектов с параметром и законами движения из Fvmin,vmax.

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

Теорема 8. Каково бы ни было вероятностное пространство над множеством законов движения Fvmin,vmax, для алгоритма A5, решающего задачу о предотвращении столкновений (vmin, vmax,,, O), верно, что для произвольного запроса q средняя сложность поиска удовлетворяет неравенствам c1 (1 + 2)/vmax TA5 (vmin, vmax,,, q) c2 (1 + 2)/vmin ;

для любого объекта o средние сложности вставки и удаления удовлетворяют неравенствам c3 (1 + 2)/vmax SA5 (vmin, vmax,,, o) c4 (1 + 2)/vmin, c5 (1 + 2)/vmax RA5 (vmin, vmax,,, o) c6 (1 + 2)/vmin ;

средний объем алгоритма A5 удовлетворяет неравенствам c7 ((1 + 2)/vmax )3/2 c8 ((1 + 2)/vmin )3/2, QA5 (vmin, vmax,, ) где c1, c2, c3, c4, c5, c6, c7, c8 некоторые константы.

С учетом того, что среднее число объектов в библиотеке принадлежит отрезку [ vmax (1 + 2), vmin (1 + 2)], мы получаем, что основные средние сложностные характеристики алгоритма A5 равны по порядку корню квадратному от мощности библиотеки, а объем памяти, необходимый для хранения структур данных, в среднем равен по порядку мощности библиотеки в степени 3/2.

Благодарности Автор выражает глубокую благодарность своему научному руководителю профессору Гасанову Э.Э. за постановку задачи и постоянное внимание к работе, академику Кудрявцеву В.Б. за многочисленные полезные советы на всех этапах подготовки диссертации и всему коллективу кафедры математической теории интеллектуальных систем Механико математического факультета Московского государственного университета имени М.В.Ломоносова за теплую творческую атмосферу.

Публикации автора по теме диссертации Из списка ВАК:

1. Скиба Е.А. Логарифмическое решение задачи об опасной близости // Интеллектуальные системы. 2007. 11: 1–4. С. 693–719.

2. Снегова Е.А. Случай задачи об опасной близости, сводящийся одномерному интервальному поиску // Интеллектуальные системы. 2009.

13: 1–4. С. 97–118.

3. Снегова Е.А. Критерий сводимости задачи об опасной близости к одномерному интервальному поиску // Дискретная математика. 2011. 23: 3.

С. 138–158.

4. Снегова Е.А. Критерий сводимости задачи об опасной близости к одномерной задаче о прокалывании // Интеллектуальные системы. 2011.

15: 1–4. С. 281–306.

5. Снегова Е.А. Критерий сводимости задачи об опасной близости к одномерным задачам для полиномиальных законов движения // Интеллектуальные системы. 2011. 15: 1–4. С. 639–660.

6. Snegova, E. A. A criterion for reducibility of the problem on danger ous closeness to one-dimensional interval search // Discrete Mathematics and Applications. 2011. 21: 5–6. P. 701–725.

Публикации не из списка ВАК:

7. Скиба Е.А. Решение задачи об опасной близости при слабых ограничениях на законы движения // Международная конференция "Современные проблемы математики, механики и их приложений посвященная 70-летию ректора МГУ академика В.А.Садовничего (30 марта - 2 апреля 2009 г., Москва). Материалы конференции. С. 374–375.

8. Скиба Е.А. Приближенное решение задачи об опасной близости // Сборник тезисов XVI Международной конференции студентов, аспирантов и молодых ученых "Ломоносов-2009 секция "Математика и механика" (Москва, 13-18 апреля 2009). С. 61–62.

9. Снегова Е.А. Критерий сводимости задачи об опасной близости к одномерному интервальному поиску // Материалы X Международного семинара "Дискретная математика и ее приложения"(Москва, 1–6 февраля 2010 г.). Издательство механико-математического факультета МГУ, Москва, 2010. С. 432–434.

10. Снегова Е.А. О сводимости задачи об опасной близости к задаче одномерного интервального поиска // Тезисы докладов Секции "Математика и механика"Международной конференции студентов, аспирантов и молодых учёных "Ломоносов-2010". М.: Механико математический факультет МГУ имени М.В.Ломоносова, 2010.

11. Elena Snegova. Criteria for Reducibility of Moving Objects Closeness Problem // Advances in Databases and Information Systems. 2010. LNCS 6295.

Pp. 583–586.

12. Снегова Е.А. Критерий сводимости задачи о предотвращении столкновений к задаче о прокалывании // Материалы X Международной конференции "Интеллектуальные системы и компьютерные науки"(5- декабря 2011 года). М.: 2011. С. 108–111.