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

• Автор: Снегова, Елена Александровна
• Шифр специальности: 01.01.09
• Научная степень: Кандидатская
• Год защиты: 2012
• Место защиты: Москва
• Количество страниц: 105 с. : ил.

Оглавление
Введение
1 Сводимость к одномерному интервальному поиску
1 Основная лемма
2 Критерий сводимости к задаче одномерного интервального поиска
2.1 Достаточность
2.2 Необходимость
3 Решение задачи о предотвращении столкновений сводимостью к задаче
одномерного интервального поиска
2 Сводимость к задаче о прокалывании
1 Критерий сводимости к задаче о прокалывании
1.1 Достаточность
1.2 Необходимость
3 Сводимость к интервальному поиску и задаче о прокалывании для
аналитических законов движения
1 Доказательство утверждения 1
1.1 Достаточность
1.2 Необходимость
2 Доказательство утверждения 3
3 Доказательство теоремы
4 Алгоритмы сокращения перебора
1 Предположения о вероятностном распределении
2 Алгоритм решения задачи о предотвращении столкновений сведением к
задаче о пересечении
3 Алгоритм решения задачи о предотвращении столкновений сведением к
одной задаче о прокалывании и двум задачам одномерного интервального поиска

4 Алгоритм решения задачи о предотвращении столкновений сведением к одной задаче одномерного интервального поиска и двум задачам о прокалывании
5 Общий случай задачи о предотвращении столкновений
1 Вспомогательные утверждения
2 Описание алгоритма

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

• ГД = (l + e,X0),
• q2 = (i + Зе + Ç(a:o, y2), Tq),
• Чз = (t + 2e, x0),
• 94 = (i + C(*o. У2) + 2e, æ0).
Моменты t[ и t3q показаны на рис. 1.4, где (, = ((х0,у‘).
Покажем, что V = V(t) = V(tq) = V(tq) = V{tq) = {оь o2,o3, o4}, то есть Ц G [i,, tt + ттах, где i,j G {1,2,3,4}. Для этого необходимо показать, что min t3 > maxi, и
1=1,4 t=l
maxt3 < mini, + ттах.
1=1,4 1=1
• min t3n = t+e > t + maxFR(x0,yk)+3e = maxi,, что равносильно e < — max
7=1,4 fc=l,2 *=1,4 fc=l
и это верно из-за выбора е;
• maxI,3 = I. + Зе + ({х0,у2) > min t, + TmaJ. = t + тт{д(.т0,у1), Fxo, у2) + е} + ттах,
7=1,4 *=1
что выполнено, поскольку в силу выбора £ верно, ЧТО £ < РХ°’У )+Т™* и е <
Fr(x 0,yl)+TrnaI
Используя утверждение леммы 1, покажем, что выполнено J(f,f4,P,V(t),q 0 = {ouo2}.J(fJq,p,V(t),q2) = {0u03},J(fJq,p,V(t),q3)
{oi,o2,o4}, J(f, f4,p, V(t),q4) = {ob o3,o4}.
• Oi G J{f,fq,p,V{l),q1 4Ф FR{xQ,yl) — e G [Ft(xo, î/1), Fr(x0, y1)], что верно,
поскольку в силу (1.18) £ < Fr(xо, у1) - Fi(xq, у1) = С(а?о, У1);
• 02 6 J(/, /,,Д, V"(i), Çi) 4Ф FR(x0,y2) € [FL(xo,y2),Fß(x0,y2)], что верно;
• о3 g J(f,f4,p,V{t),qi) Fß(x0,y2) + 2e [FL(x0, у2), F(x0, у2)], что верно,
поскольку е > 0:
• о4 i J(f,fq,p,V(t),qi) => Fr(x0, у2) + e i [FL(x0,y2),FR(x0,y2)}, что верно,
поскольку е > 0;
• oi G J(f,fg,p, V(t),q2) FK(x0,y1) -3£-Ç(x0.y2) £ [FL(x0l y1), Fß(x0, y1)]
—3e — C(x0,y2) G [—С(ж0,У1), 0] 4Ф e G [0, )]; чт0 верно по условию
(1.18) выбора e;
• 02 <£ J(/, fq. p, V(i), y2) <£> FL(x0,y2) - 2e [FL(x0,y2), Ffi(x0,y2)], что верно,
поскольку e > 0;
• o3 G J(f,fq,p,V(t),q2) Fl(x0, y2) G [FL(æ0,y2),Ffl(.T0,y2)], что верно;