Сложность задачи о предотвращении столкновений тема автореферата и диссертации по математике, 01.01.09 ВАК РФ

МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ имени М. В. ЛОМОНОСОВА

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

005054224

Снегова Елена Александровна

"7

СЛОЖНОСТЬ ЗАДАЧИ О ПРЕДОТВРАЩЕНИИ СТОЛКНОВЕНИЙ

01.01.09 — дискретная математика и математическая кибернетика

АВТОРЕФЕРАТ

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

МОСКВА - 2012

- 1 НОЯ 2012

005054224

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

Научный руководитель:

Официальные оппоненты:

Ведущая организация:

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

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

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

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

Защита диссертации состоится 16 ноября 2012 г. в 16 ч. 45 м. на заседании диссертационного совета Д 501.001.84 при Московском государственном университете имени М.В.Ломоносова по адресу: Российская Федерация, 119991, Москва, ГСП-1, Ленинские горы, д.1, Московский государственный университет имени М.В. Ломоносова, Механико-математический факультет, аудитория 14-08.

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

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

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

А.О.Иванов

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

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

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

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

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

Поскольку задача о предотвращении столкновений динамическая, то

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

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

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

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

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

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

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

1. Случаи статических (неподвижных) объектов и статических (неподвижных) запросов: Preparata и Shamos3 , Roussopoulos4, Cheung и

ЧлііЦтап Л. R-Tree>-: Л Dynamic Index Structure for Spatial Searching. In Proceeding.s of the 19S4 ACM SIGMOD International Cnnfcreiice 011 Management of Data, pp. 47-57. 1984.

2L. Argc, M. de Berg, II. .1. Ilavcrkorc, and K. Yi. The Priority R-Trec: A Practically Eflicient and Worst-Case-Optimal R-TYee. Symp. of the ACM Special Interest Group on Management of Data (SIGMOD), Paris, 2004. pages 347-35S.

:!Prcparata F.P.. Shamos M.I.: Computational geometry: An introduction (tcxt.s and monographs in computer science). 5th edri. Springer, Berlín, Heidelherg, New York (1993)

4R.oussupoulos N.. Kcllcv S., and Vincent F. Xearest ricighbor queries. In Procecdings of ACM SIGMOD

Fu5, Korn ii др.6

2. Случай статических (неподвижных) запросов и динамических (движущихся) объектов: Berehtold и Ertl7. Kollios и Gunopulos8.

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

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

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

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

Для наиболее распространенных законов движения объектов.

International Conference on Management of Data. San Jose, USA, 1995.

'Cheung K. L. and Fu A. VV. Enhanced Nearest Neighbour Search on the R-tice. SIGMOD Record 27(3): 1G-21. 1998.

6Korn F.. Sidiropoulos N.. Faloutsos С , Sie°el E.. and Protopapas Z. Fast nearest neighbor search in medical imago databases. In Proceedings of International Conference on Verv Large Database, Mumbai India. 199G.

'Berehtold. S., Ertl. В., Kciiu, D.A., Kricgel, H.P.. Scidl, 'Г.: Fast nearest neighbor search in high-dimensional space. In: Proceedings of the International Conference on Data Engineering, pp. 209-218 (1998)

8Kollios, G.. Gunopulos. D.. Tsotras, V.J.: Nearest neighbor queries in a mobile environment. In: Proceedings of the International Workshop on Spatio-Tcmporal Database Management, pp. 119- 134 (1999)

9Soug Z. and Roussopoulos X. K-.\earest Neighbor Search for Moving Query Point. In Proceedings of the 7th International Symposium on Spatial and Temporal Databases, pp. 79-90. 2001.

10Seidl T. and Kriegel H. Optimal multi-step k-uearest neighbor search. In Proceedings of ACM SIGMOD International Conference on Management of Data. Seattle. USA. 199S.

"Tao Y.: Papadiai D., Shell Q. Continuous Nearest Neighbor Search. In VLDB, 2002.

12AtaIlah M. Dynamic Computational Gcomctrv. Proc. 24th Annu. IEEE Sympos. Found. Comput Sci 1983.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Апробация работы. Результаты работы докладывались па Международной конференции "Современные проблемы математики, механики и их приложений посвященной 70-летию ректора МГУ академика В.А.Садошшчего (30 марта - 2 апреля 2009 г., Москва); XVI и XVII конференциях студентов, аспирантов и молодых ученых "Ломоносов-2009" и "Ломоноеов-2010секция "Математика и механика" (Москва, 2009, 2010); X Международном семинаре "Дискретная математика и ее приложения" (Москва, 1-5 февраля 2010 г.); XIV восточно-европейской конференции по достижениям в базах данных и информационных системах "Fourteenth East-European Conference on Advances in Databases and Information Systems" (Нопи-Сад, Сербия, 2010); X Международной конференции "Интеллектуальные системы и компьютерные науки" (Москва, 5-10 декабря 2011 года), а также па семинарах механико-математического факультета МГУ им. М.В.Ломоносова: на семинаре "Теория автоматов" под руководством академика, проф., д.ф-м.н. В.Б. Кудрявцева (20102011 г.), неоднократно на семинаре "Вопросы сложности алгоритмов поиска" под руководством проф., д.ф-м.н. Э.Э.Гасанова (200G-2011 гг.), на семинаре "Кибернетика и информатика" под руководством академика, проф., д.ф-м.н. В.Б. Кудрявцева (2011 гг.).

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

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

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

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

В момент появления каждый объект и каждый запрос сообщают

Рис. 1: Движение объектов и запросов в задаче о предотвращении столкновений. Кругом отмечен пример столкновения объекта и запроса.

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

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

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

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

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

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

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

2) дифференцируемая строго возрастающая функция / : —> [—р, 1 +

р], такая что /(0) = -р, называемая законом движения объектов-,

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

4) бесконечная последовательность О = {оь о2,..., о„,...}, такая что ог = (ti,y¡), г/г € [0.1]. а f,- - действительные числа, образующие возрастающую последовательность f0 < h < t2 < ... < tn..., называемая потоком объектов.

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

Введем еще два параметра, которые понадобятся в дальнейшим: параметр ттах = /_1(1 + р), называемый временем движения объектов и параметр т^ах = /"'(1 +р), называемый временем движения запроса.

Предполагаем, что объект о,- = {U,yi) появляется на границе прямоугольника [-р, 1 + р] х [0,1] в момент времени tt в точке с координатами (-р, п движется по закону движения / параллельно оси х, то есть в момент t £ [tu и + ттах\ объект О,; находится внутри прямоугольника {-р. 1 + р] х [0, 1] в точке с координатами (/(i - U), ;</,-).

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

Предполагаем, что запрос q = (tq,x) появляется на границе прямоугольника [0, 1] х [-р, 1 + р] в момент времени tq в точке с координатами (х, -р) и движется по закону движения fq параллельно оси у, то есть в момент t е [tq, tq + r'J запрос q находится внутри прямоугольника [0,1] х \-р, 1 + р] в точке с координатами (х, fq(t. - t,)). Скажем, что объект о, = (ti,yt) и запрос q = (tq,x) сталкиваются, если существует момент времени t 6 К. такой что \f(t-ti)-x\ + \yi-fq(t-t.q)\ ^ />■

В задаче требуется для произвольного запроса перечислить все объекты из потока О, которые появились до него и с которыми он столкнется в процессе своего движения, то сеть ответом на запрос q = (t4,x) при расстоянии опасной близости р является множество

J{f- U Р, О, q) = {0i = (f.,, yt) € Q| ti <t„ и 3 t :

\f(t-U)-x\ + \yi-fq(t-tq)\^p\.

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

Введем последовательность, объединяющую моменты появления и исчезновения объектов {.Si}^! = {ti}^ и {i, + w}^! и заметим, что по сути V(t.) - это кусочно-постоянная функция V : R 2°, меняющаяся в моменты появления и исчезновения объектов Ы, х € N.

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

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

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

= {oi = {илм) € V{t)I 3t>: I/(f - U) - x\ + Ь ~ Ш ~ i,)| «S P} и заметим, что при tq € [max 67, rnins,] J(f. fq, p:0,q) = J(ffq, p,V(t),q).

Si^t ■1i>t

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

1. Обновление библиотеки V(f) в моменты времени Si, i £ N. В каждый момент ti, г е N, происходит добавление объекта ot = (t,-,?/;) в "текущую" библиотеку, а в каждый момент U + ттах, i € N, происходит удаление объекта Oi = {ti, г/i) из "текущей" библиотеки.

2. Поиск ответа на запрос q = (tq,x) в библиотеке V{t), при условии, что ta € fmaxs,-. min Sjl 13.

4 s.sSi .S i>t

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

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

13Заметнм. что t также принадлежит отрезку [max sit min s,j, то есть и библиотеку V{t) могут

a.^i i.X

поступать запросы с моментом появления равным t или близким к t

14Гасанов Э. Э.. Кудрявцев В.В. Теория хранения и поиска информации. — М.: ФИЗМАТЛИТ, 2002.

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

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

Пусть О = {01 = 02 = (Ь,У2),...,Ъ = (/,.//,)....} -

произвольный поток объектов и {в,}^ = и {и + тта.г}^! -

последовательность, объединяющая моменты появления и исчезновения объектов. Алгоритмом решения задачи о предотвращении столкновений (/,. /г, О) будем называть совокупность трех процедур поиска, вставки и удаления, таких, что для любого і Є N если вызывать процедуру вставки во все моменты Ь] ^ а процедуру удаления во все моменты ^ + ттах < в,-для объектов Оі, то для любого запроса q = .т) такого, что ві ^ < в^+ь процедура поиска в ответ будет выдавать множество ./(/, /,, р, У(іч), <?).

Пусть А - алгоритм, решающий задачу о предотвращении столкновений. Тогда сложность поиска по алгоритму А на запросе ц при библиотеке У{і) есть величина, равная сумме сложностей всех элементарных операций, выполненных процедурой поиска при подаче на ее вход запроса (/ при условии, что на момент поиска структура данных соответствовала библиотеке Сложность поиска всегда включает

в себя сложность перечисления ответа, которая как минимум равна длине ответа на запрос. Поэтому в перечислительных задачах поиска как правило исследуют сложность поиска без перечисления ответа. Сложностью поиска без перечисления ответа на запросе д назовем величину, равную сложности на запросе 9 минус мощность ответа на запрос д. Обозначим эту сложность /„ р, д,

Сложность вставки по алгоритму А объекта о в библиотеку У{Ь) обозначим £л(/; Іч,Р,о, У(і)) и будем считать равной сумме сложностей всех элементарных операций, выполненных процедурой вставки при подаче на ее вход объекта о при условии, что на момент вставки структура данных соответствовала библиотеке У(Ь).

Сложность удаления по алгоритму А объекта о из библиотеки У{Ь) обозначим о, У(ї)) и будем считать равной сумме сложностей

всех элементарных операций, выполненных процедурой удаления при подаче на ее вход объекта о при условии, что на момент удаления структура данных соответствовала библиотеке У{1).

Объемом алгоритма А для библиотеки У{і) назовем число ребер в графе, описывающем структуре данных, соответствующей библиотеке К(£): и обозначим <2д(/, /„ р, У(Ь)).

Содержание работы

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

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

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

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

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

Будем говорить, что задача о предотвращении столкновений (/-. ¡ч-, Р- У(^)) сводится с задаче одномерного интервального поиска, если существуют такие отображения (¿>, К х [ОД] —» К, что для

любой библиотеки У(Ь), любого запроса q = (Ьч,х) и любого объекта о 6 У(0 верно о в J{f.Jq,p..V{t),q) <=> -з(о) € Щч>1{ч),-Жч)\:2), гае

г=Ыо):оеУ(1)}.

Обозначим:

/•'/.(•'■% V) = ™.М1{у + £-р)-Г\х + £)),

Рк(х,у) = тах (/~1(у + $ + р)-Г1(х + 0):

Ха = {.гб[0Д]:Эг/ ^(.т, у) < 0}, Хь = {х 6 [0, 1] : Зу Р^х,у) < 0}, Уь = {у е [ОД] : Эх Рь{х,у) <0}.

Теорема 1. Задача о предотвращении столкновений (/, р,У^)) сводится к задаче одномерного интервального поиска тогда и только тогда, когда существуют функции ф, ф[_, фя : [0, 1] —» К такие, что для любой пары (х.у), для которой выполнено условие /-¿(.г', у) 5С 0, верно, что

= р{у) + фь{х), (1)

а для любой пары {х,у). такой, что Т'д(х.у) ^ 0, верно, что

1г1{(х,у) = ф{у) + фц(х). (2)

При этом если выполнены условия (1) и (2) и

Ф*(у)

■ф'в{х) =

( Фн{х). если х е Хц. \ F^í(0,1), если х £ Хя,

Ш*)

то функции сведения (дз, (/Зь^) имеют вид

!л) = ti - ф'^л),

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

Теорема 2. Для алгоритма Ль решающего задачу о предотвращении столкновений (/, /9. р, У(Ь)) сведением к задаче одномерного интервального поиска верно, что для сложности поиска ответа на любой запрос q, вставки любого объекта-дагтого о, удаления любого объекта-дагтого о по алгоритму Ль и для объема алгоритма /Ц выполнены соогпветс7пвенно соотношения

где с — константа не зависящая от \У\.

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

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

тА1и,/ч,р.У(1),ч) ^ с1о§2 IV'!,

Я А Л/,/я,Р,У(Ы < с\у\,

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

Будем говорить, что задача о предотвращении столкновении {f-.fq-.P-.V(t)) сводится с задаче о прокалывании, если существуют такие отображения '-p^u'-pi ® х [0, 1] —1• К, что для любой библиотеки V(t), любого запроса q = (t.q,x) и любого объекта о 6 V верно

О 6 Af-UP: \\<l) Ыо): 'Мо)} € Av(q),Z),

где Z = {[^i(o),tp2(o)} -.oeV).

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

Аналогично критерию сводимости к задаче одномерного интервального поиска обозначим

Yr = {у е [0,1]: Эх FR{x,y)< 0}, Yl = [у е [0,1] : Эх Fi(x, у) < 0}, XL = {хе [0,1] :Эу FL{x,y) < 0}.

Теорема 3. Задача о предотвращении столкновении (f,fq,p,V{t)) сводится к задаче о прокалывании тогда и только тогда, когда существуют функции ibL, уд : [0,1] —» К. такие, что для любой пары (х,у), для которой выполнено условие Fi(x,y) sj 0, верно, что

FL(x,y) = v{x) + yL(y), (3)

а для, любой нары (х, у). такой, что Fn(x,y) ^ 0, верно, что

Fr(x, у) = v(x) + рн(у). (4)

При этом, если выполнены условия (3) и (4) и

/«/ \ _ / v(.r), если х 6 Xl, v Ух) - | /7Л(0,1), если х £ Xl,

л _ / Vr{v), caiuyeYR, VrA'J) - | Fr[q 1}i eam y ^ Yr

-:.* f.\ _ f если у £ Yl,

Vl["> - { Fl(0,1), если у # Yl,

то функции сведения (ip, ipi,ip->) имеют вид

■j(tq,x) = t4 + v'(x), Vi(<i:J/i) = и-Ц>пЬл),

V>2(t-i, Vi) = ti- 1pl{yi).

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

Теорема 4. Пусть законы движения /, /9 - аналитические функции. Тогда задача о предотвращении столкновений (/, fq, р, V(t)) сводится к задаче одномерного интервального поиска или задаче о прокалывании тогда и только тогда, когда выполнено хотя бы одно из четырех условий

Условие 1.

1. Ест (х,у) G [рЛ + р] х [0, 1] : f~\y) - f~\x) sS 0, то

(/Я~Ъ)У < (ГЧ*))';

2. Если Fl(x, 0) ^ 0. то р е arg min FA.г, 0. Л;

€е[0,р]

3. Ecjiu Fr(x, 1) ^ 0. то -р G arg max FAx. l.f):

4. Если (x,y) 6 [0,2/з] x [0, 1] : FR(x,y) 0, mo

—p € arg max F/t(x.y. £):

fe[-p.0|

5. Если (x, у) e [0, p] x [0,1] : FL(x, у) sj 0, mo

p 6 arg min FL(x,y,£); ie(<M

Условие 2.

1. Ест (х, у) е [0, 1] X [-Р, 1 -р\, f~\y) - /-!(;,;) ^ 0,

то (/-ЧУ))' 2 (ГЧ*))';

2. Если Fl(0, у) ^ 0, то 0 е arg min FL(0, у, £);

ie[0./>]

3. Если FR(l, у) ^ 0, то 0 6 arg max FR( 1. и, f):

4. Если (x, у) € [0, 1] x [1 - p, 1] : FR(x, у) 0, mo 0 6 arg max FR(x.y,f):

5. EcjXU (x, у) e [0, 1] x [1 - p, 1] : FL(x: у) < 0, mo

0 G arg min FL(x,y,£)] iS[0,/)J

Условие 3. / - линейный многочлен;

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

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

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

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

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

Будем говорить, что задача о предотвращении столкновений (/■./ч-накрывается задачей о пересечении, если существуют такие отображения : Е х [0.1] —> Е, что для любой

библиотеки У(£), любого запроса q = {Ьч,х) и любого объекта о е V верно о е J{f..I(l,p,V,q) [у>1(о),?2(о)] € -ЩЫч)-. М<1)\-где

2={Ыо)./Мо)]:оеУ}.

Четверку (^1, <¿>9, <Р:и <Р-\) будем называть функциями сведения. Предположим, что ПОТОК объектов О = {о[ = (¿1. //1); 02 = 2/2), ■ ■ ■ : о, = (£,-.)/;), ...} представляет собой случайный процесс такой, что моменты появления объектов и образуют пуассоновский поток с параметром А, а координаты появления у,- имеют равномерное и независимое распределение на отрезке [0, 1] для каждого ¿. Такие потоки объектов будем называть пуаг.соновскими потоками объектов. Пусть У(Ь) случайная библиотека в момент времени £, порожденная пуассоновским потоком объектов О, т.е. У{Ь) = {о; = {и,у{) е О : £, < £ < ттах.}

Средней сложностью поиска по алгоритму .4 на запросе </ для расстояния опасной близости р назовем математическое ожидание по библиотеке от сложности поиска: 7л(/,А, <7, £) = /9, р. У^). </), где математическое ожидание берется по всем случайным библиотекам 1/(£), порожденными пуассоновскими потоками объектов с параметром А, а Тл(/, /,, р, К(£), q) — сложность поиска по алгоритму А па запросе </.

Поскольку пуассоновский поток объектов является стационарным, то для достаточно больших £, а именно £ > А • тщах, число объектов в библиотеке не зависит от t и приблизительно равно А • ттах. Отсюда в частности следует, что величина ТА(/, /,, р, А, ц, £) для достаточно больших

t не зависит от t, и поэтому будем писать 7д(/. fq, р, Л, <7).

Будем писать /(и) = 0(у(п)), если существуют такие константы С\ и Со, что для любых Ii G N выполнено С\ ■ д(п) < f(n) ^ С2 • д(п). Введем следующие обозначения для задачи о предотвращении столкновений:

Vmin = mill f'{y), vmax = max f'(y), „9

min J'q(y), ,max J'q{y)-

Будем предполагать, что задача о пересечении может быть решена со средней сложностью rS(\Tmax), затрачивая объем памяти порядка где ^ттах есть среднее число отрезков в библиотеке Z1 совпадающее со средним числом объектов в области наблюдения. В этих предположениях построен алгоритм А-2, который решает задачу о предотвращении столкновений (f.fq,p,V(t)).

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

2р\(— + --L) < TAl(f,f4,p,\,q) - rS(\Tmax) < 2р\(— + -І-),

Vmax V,nax Vmirl Vmjn

а объем равен QAl(f, fq, P, V(t)) = 0(\ттах) .

Будем говорить, что задача о предотвращении столкновений (f-.fq-.P-.V(t)) накрывается двумя задачами одномерного интервального поиска и одной задачей о прокалывании, если существуют отображения '•рЬ Ч>1-. '-Pi-. 'р4, <Р5, <¿>6: +>7, PS, <P<J R X [0. 1] —> К, ЧТО ДЛЯ Любой библиотеки V{t). любого запроса q = (tq,x) и любого объекта о Є V верно, что если о Є J{f..fq..p..V,q), то либо Є -/([^(^.^WUi),

где Z\ = {>1(0) : о Є V}, либо ^4(о) Є j([tpb{q), ^{q)\,Z-2), где Zi = (р4(о) : о Є V}, либо [j7{o). #3(0)] Є J([ipg(q), Z3), где

Будем предполагать, что задача о прокалывании (/2, Z2) может быть решена со средней сложностью DO(\Tmax), где Аттах есть среднее число отрезков в библиотеке /?2, совпадающее со средним числом объектов в области наблюдения. В этих предположениях построен алгоритм Аз,который решает задачу о предотвращении столкновений {f,fq-.p,V{t)).

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

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

-^-А + 0(log2(Aw)) + DO(Aw) ^ TÀ3(f, /„ p. q) ^

Umax

^ —А + 0(!og2(Aw)) + DO(Aw),

U min

а объем равен QAl(f, fq,p, V(t)) = 0{\ттах).

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

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

Пусть vmi„, Umax- Urnin < t'm/jj'- некоторые положительные числа, J~i'm,n,vma, ~ множество дифференцируемых строго возрастаю[цпх функций / : К+ \-р, 1+р], таких что /(0) = -р, и vrmn sC /'(г) < vmax для любого г е [0,/_1(1 + р)\. Пусть на задано некоторое вероятностное

пространство.

Будем считать, что у каждого объекта о, есть свой собственный закон движения fi € Jrvmi„,vmox-, и объект в этом случае представляет из себя тройку Oi = (fi, tu yi), при этом как и ранее будем считать, что поток объектов О = (oi = (fi, t\,lj\),02 = (h,tl,tj2),...,Ol = (/¿, f „ yt), . . .} представляет собой случайный процесс такой, что моменты появления объектов ti образуют пуассоновский поток с параметром А. координаты появления Vi имеют равномерное и независимое распределение на отрезке [0. 1] для каждого i, а законы движения /,• выбираются в соответствии с распределением, заданным на т.е. поток объектов является

пуассоновским потоком. Пусть V(t) случайная библиотека в момент времени t., порожденная пуассоновским потоком объектов О, т.е. V(t,) = {°г = (Л, tu yi)eO-.tl^t^ti + f~l( 1 + p)}.

Поскольку пуассоновский поток объектов является стационарным, то для достаточно больших £, а именно t > А • (1 4- '2p)/vmm, среднее число объектов в библиотеке не зависит от £. Отсюда в частности следует, что все сложностные характеристики алгоритмов для достаточно больших t не будут зависеть от t, и поэтому параметр t мы далее будем опускать, считая, что t. достаточно большое.

Закон движения запроса fq также не известен заранее и принадлежит множеству J~rmin,Vnlal. Запрос в этом случае представляет из себя тройку q = (fq-.tq,x). Как и ранее, задача о предотвращении столкновений состоит в

том чтобы для произвольного, но зафиксированного пуассоновского потока объектов О и произвольного запроса q — (/?, tq, х) найти в библиотеке V(tq) все объекты, которые п процессе своего движения окажутся на расстоянии по Манхэттену не более чем р от запроса q. В такой формулировке задачу о предотвращении столкновений обозначим как пятерку (vmin.vmax, р, А, О).

Пусть имеется некоторый алгоритм А решения задачи о предотвращении столкновений и пусть La(V, ...) некоторая сложностная характеристика алгоритма А для библиотеки V. Тогда обозначим ¿л(«1чм, Vmax, Р, А, ■ ■ ■) = М.уLa{V. ...), где математическое ожидание берется по всем случайным библиотекам V. порожденными пуассоновскими потоками объектов с параметром Л и законами движения

ИЗ ^"l;„„-„

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

Теорема 8. Каково бы. ни было вероятностное пространство над множеством законов движения J-Vmin Vmar, для алгоритма Л5) решающего задачу о предотвращении столкновений (vmju, vmax, р, А, О), верно, что для произвольного запроса q средняя сложность поиска удовлетворяет неравенствам

С1\Л(1 + 2 р)/г ■тах ^ -^4.5 (^mim ^maxi р, А, q) ^ с2 \/А(1 + 2p)/vmin\

для любого объекта о средние слоз/спости вставки и удаления удовлетворяют неравенствам

сзх/А(1 + 2p)/vmax ^ SA.(vmin, vmax, р., А, о) ^ с4\/А(1 + 2p)/vmln,

с5а/А(1 + 2p)/vmax sj RA5{vmin, vmax, р, А, о) < с6\/А(1 + 2p)/vmin\ средний объем алгоритма Ас, удовлетворяет неравенствам

С7(А(1 + 2p)/vmaxf'2 ^ QA-XVmin^ma^p.X) ^ Cg(A(l + 2Р)/Vmin)il2, где с 1. со, Сл, С4, es, cq, Cj, es — некоторые константы.

С учетом того, что среднее число объектов в библиотеке принадлежит отрезку (1 + 2р). -^-(1 + 2р)\, мы получаем, что основные средине

rnax "min

еложностные характеристики алгоритма As равны по порядку корню квадратному от мощности библиотеки, а объем памяти, необходимый для хранения структур данных, в среднем равен по порядку мощности библиотеки в степени 3/2.

Благодарности

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

Публикации автора по теме диссертации

Из списка ВАК:

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

2. CneroRa Е.А. Случай задачи об опасной близости, сводящийся одномерному интервальному поиску // Интеллектуальные системы. 2009. 13: 1-4. С. 97-118.

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

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

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

6. Snegova, Е. A. A criterion for reducibility of the problem on dangerous 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 G295. Pp. 583-58G.

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

Подписано в печать 11.10.2012 Формат 60x88 1/16. Объем 1.0 п.л. Тираж 110 экз. Заказ № 1251 Отпечатано в ООО «Соцветие красок» 119991 г.Москва, Ленинские горы, д.1 Главное здание МГУ, к. А-102

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

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

04201357131

Снегова Елена Александровна

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

Специальность 01.01.09 — дискретная математика и математическая кибернетика

Диссертация

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

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

Москва 2012

Оглавление

Введение 4

1 Сводимость к одномерному интервальному поиску 26

1 Основная лемма..................................................................26

2 Критерий сводимости к задаче одномерного интервального поиска .... 27

2.1 Достаточность............................................................30

2.2 Необходимость............................................................32

3 Решение задачи о предотвращении столкновений сводимостью к задаче одномерного интервального поиска............................................43

2 Сводимость к задаче о прокалывании 48

1 Критерий сводимости к задаче о прокалывании..............................48

1.1 Достаточность............................................................49

1.2 Необходимость............................................................51

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

1 Доказательство утверждения 1 ................................................64

1.1 Достаточность............................................................64

1.2 Необходимость............................................................65

2 Доказательство утверждения 3 ................................................73

3 Доказательство теоремы........................................................74

4 Алгоритмы сокращения перебора 78

1 Предположения о вероятностном распределении ............................78

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

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

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

прокалывании....................................................................89

5 Общий случай задачи о предотвращении столкновений 95

1 Вспомогательные утверждения..................................................96

2 Описание алгоритма............................................................97

Введение

Общая характеристика работы Актуальность темы.

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

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

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

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

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

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

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

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

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

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

В большей части методов решения задачи поиска объекта, ближайшего к запросу, используются структуры данных, основанные на конструкции R-дерева [1]. R-дерево - (R-Tree) это индексная структура для доступа к пространственным данным, предложенная А. Гуттманом (Калифорнийский университет, Беркли) в 1984 году [36]. R-дерево допускает произвольное выполнение операций добавления, удаления и поиска данных без периодической переиндексации. Эта структура данных разбивает пространство на множество иерархически вложенных и, возможно, пересекающихся, прямоугольников (для двумерного пространства). В случае трехмерного или многомерного пространства это будут прямоугольные параллелепипеды (кубоиды) или параллелотопы. Алгоритмы вставки и удаления используют эти ограничивающие прямоугольники для обеспечения того, чтобы «близкорасположенные» объекты были помещены в одну листовую вершину. В частности, новый объект попадёт в ту листовую вершину, для которой потребуется наименьшее расширение ее ограничивающего прямоугольника. Каждый элемент листовой вершины хранит два поля данных: способ идентификации данных, описывающих объект, (либо сами эти данные) и ограничивающий прямоугольник этого объекта. Аналогично, алгоритмы поиска (например, пересечение, включение, окрестности) используют ограничивающие прямоугольники для принятия решения о необходимости поиска в дочерней вершине.

Рис. 1: Пример R-дерева для хранения двумерных прямоугольников.

Таким образом, большинство вершин никогда не затрагиваются в ходе поиска.

Пример R-дерева изображен на рисунке .

Основным положительным качеством Л-дерева является его сбалансированность и возможность поддерживать это состояние без периодической переиндексации, затрачивая O(logn) операций во время добавления нового объекта или удаления уже имеющегося в базе данных объекта, (где п есть число элементов, хранящихся в R-дереве). Кроме того, R-дерево построено таким образом, что поиск ответа на подавляющее число запросов будет происходить "в основном в глубину" однако, в худшем случае возможно, что сложность поиска будет иметь порядок п, даже если ни один объект из базы данных не попадает в ответ на запрос. Объем R - дерева также линеен.

В 2004 году Lars Arge, Mark de Berg и др. изобрели модифицированную структуру данных под названием приоритетное R-дерево [2], которое позволяет производить поиск ответа на запрос за время 0(n1-s +Т) в худшем случае, где Т есть время перечисления запроса, ad - размерность пространства. Таким образом, для двумерного пространства поиск в худшем случае будет иметь сложность 0(\/п + Т). При этом, приоритетное R-дерево поддерживает логарифмические операции вставки и удаления, и также имеет линейную память.

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

1. случай статических (неподвижных) объектов и статических (неподвижных) запросов,

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

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

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

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

Поскольку диаграмма Вороного является многомерной структурой, то ее использование может потребовать много памяти. Поэтому, естественно, вместо ячеек Вороного хранить в R - дереве их минимальные охватывающие прямоугольник, что и реализовано в [3]. Характеристики соответствующего алгоритма совпадают с характеристиками R-дерева.

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

Roussopoulos и др. [6] разработали метод поиска к ближайших объектов. В их алгоритме обход R* - дерева (модификации Я-дерева [7]) при поиске происходит преимущественно в глубину, за счет чего и достигается эффективность работы алгоритма. Cheung и Fu [8] упростили их алгоритм без потери в эффективности, а Korn [5] и др. модифицировали предложенный алгоритм для случая к = 1, добавив несколько дополнительных этапов отбора. Benetis [9] и др. расширили предложенный алгоритм его на случай непрерывно движущихся объектов.

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

Случай движущихся объектов и точечных неподвижных запросов рассматривалась в [14]. Идея предложенного в статье алгоритма состоит в преобразовании диаграммы Вороного. В работе показано, что каждое такое преобразование имеет сложность Сп2, где константа С зависит от характера движения объектов.

Kollios и др. [12] предложили свой алгоритм решения объекта в одномерном пространстве, в котором они использовали отображение закона движения x(t) — x0+vxt в точку (.То, vx) так называемого дуального пространства.

Случай движущихся объектов и движущегося фиксированного запроса наиболее близок к рассматриваемой в данной работе задаче о предотвращении столкновений. Большинство алгоритмов для случая непрерывного движения объектов основываются на повторных применениях алгоритмов для решения обычной задачи о нахождении ближайшего соседа, что приносит значительные издержки (см., например, [13]).

Тао и др. [15] предложили алгоритм в котором ответ на запрос формируется из трех компонент: (i) текущий ответ на запрос, (ii) момент времени i, когда текущий ответ на запрос уже перестанет быть таковым, (iii) множество объектов, которое содержит новый ответ на запрос после Т. При этом, в данном алгоритме последнее множество постоянно обновляется. База данных для этого алгоритма также представляет из себя Я-дерево, и основным недостатком алгоритма является необходимость по нескольку раз совершать обход этого дерева для нахождения следующего ответа на запрос.

В [11] Song и Roussopoulos предложили решение задачи нахождения к ближайших объектов к фиксированному движущемуся запросу в двумерном пространстве. Идея алгоритма заключается в вычислении функции квадрата расстояния до запроса и хранении упорядоченных объектов в разные моменты времени. Алгоритм позволяет производить вставку и удаление объектов. При поиске R -дерево, которое хранит данные об объектах, приходится обходить всего один раз.

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

Случай предопределенного движения объектов рассмотрен в [16] Attalah'oM. Автор предложил алгоритмы для поиска самых близких к запросу и самых быстрых

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

Цель работы.

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

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

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

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

Методы исследования.

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

Научная новизна.

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

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

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