4430
правок
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) мНет описания правки |
||
(не показано 18 промежуточных версий этого же участника) | |||
Строка 3: | Строка 3: | ||
== Постановка задачи == | == Постановка задачи == | ||
Рассмотрим множество S из n точек в d-мерном Евклидовом пространстве. Сеть на множестве S может быть смоделирована при помощи неориентированного графа G с множеством вершин S размера n и множеством ребер E, в котором каждое ребро ( | Рассмотрим множество S из n точек в d-мерном Евклидовом пространстве. Сеть на множестве S может быть смоделирована при помощи неориентированного графа G с множеством вершин S размера n и множеством ребер E, в котором каждое ребро (г, м) имеет вес. Геометрическая (евклидова) сеть представляет собой сеть, в которой весом ребра (u, v) является евклидово расстояние |uv| между его конечными точками. Пусть дано вещественное число t > 1. Мы говорим, что граф G является ''t-остовом'' множества S, если для каждой пары точек <math>u, v \in S \;</math> существует путь в G, вес которого не более чем в t раз превышает евклидово расстояние между u и v. Минимальное значение t, при котором граф G является t-остовом S, называется коэффициентом растяжения, или протяженностью, G. Более детальное изложение процедуры построения t-остовов можно найти в книге Нарасимхана и Смида [18]. В данной статье рассматривается построение t-остовов для заданного множества S из n точек в пространстве <math>\mathcal{R}^d \;</math> и положительного вещественного числа t > 1, где d является константой. | ||
Задача заключается в построении хорошего t-остова для S относительно следующих мер качества: | Задача заключается в построении хорошего t-остова для S относительно следующих мер качества: | ||
'''размер''': количество ребер в графе | '''размер''': количество ребер в графе; | ||
'''степень''': максимальное количество ребер, инцидентных вершине | '''степень''': максимальное количество ребер, инцидентных вершине; | ||
'''вес''': сумма весов ребер | '''вес''': сумма весов ребер; | ||
'''диаметр остова''': наименьшее целое число k, такое, что для любой пары вершин u и v из S существует путь в графе между u и v, длиной не более t • |uv| и содержащий не более k ребер | '''диаметр остова''': наименьшее целое число k, такое, что для любой пары вершин u и v из S существует путь в графе между u и v, длиной не более t • |uv| и содержащий не более k ребер; | ||
'''отказоустойчивость''': сохранение работоспособности графа при отказе ребра, вершины или области. | '''отказоустойчивость''': сохранение работоспособности графа при отказе ребра, вершины или области. | ||
Строка 22: | Строка 22: | ||
== Основные результаты == | == Основные результаты == | ||
Далее будут изложены три самых распространенных подхода к построению t-остова на множестве точек в евклидовом пространстве, а также приведено описание процесса построения отказоустойчивых остовов и остовов | Далее будут изложены три самых распространенных подхода к построению t-остова на множестве точек в евклидовом пространстве, а также приведено описание процесса построения отказоустойчивых остовов и остовов в присутствии многоугольных препятствий; и, наконец, будут вкратце описаны динамические и кинетические остовы. | ||
Строка 32: | Строка 32: | ||
'''<math>\Theta \;</math>-граф''' | '''<math>\Theta \;</math>-граф''' | ||
<math>\Theta \;</math>-графы были независимо разработаны в конце 80-х Кларксоном и Кейлом. Основная идея | <math>\Theta \;</math>-графы были независимо разработаны в конце 80-х Кларксоном и Кейлом. Основная идея заключается в независимой обработке каждой точки <math>p \in S \;</math> следующим образом. Разобьем пространство <math>\mathcal{R}^d \;</math> на k симплициальных конусов с угловым диаметром не более <math>\theta \;</math> и вершиной в точке p, где <math>k = O(1 / \theta^{d - 1}) \;</math>. Для каждого непустого конуса C добавляется ребро, связывающее p и точку в C, ортогональная проекция которой на некоторый фиксированный луч в C, исходящий из p, является максимально близкой к p (см. рис. 1a). Полученный граф называется <math>\Theta \;</math>-графом на S. | ||
Строка 40: | Строка 40: | ||
'''Теорема 1. <math>\Theta \;</math>-граф представляет собой t-остов на множестве S для <math>t = 1 / (cos \; \theta | '''Теорема 1. <math>\Theta \;</math>-граф представляет собой t-остов на множестве S для <math>t = 1 / (cos \; \theta - sin \; \theta)</math>, имеющий <math>O(n / \theta^{d - 1}) \;</math> ребер, и может быть вычислен за время <math>O((n / \theta^{d - 1}) log^{d - 1} \; n)</math> с использованием <math>O(n / \theta^{d - 1} + n \; log^{d - 2} \; n)</math> памяти.''' | ||
Строка 54: | Строка 54: | ||
'''Жадный подход с пробелами''' | '''Жадный подход с пробелами''' | ||
Множество ориентированных ребер удовлетворяет свойству пробелов, если источники любых двух разных ребер разделены расстоянием, по крайней мере в несколько раз превышающим длины кратчайшего из двух ребер. Арья и Смид [5] предложили алгоритм, использующий свойство пробелов для определения того, | Множество ориентированных ребер удовлетворяет ''свойству пробелов'', если источники любых двух разных ребер в множестве разделены расстоянием, по крайней мере в несколько раз превышающим длины кратчайшего из двух ребер. Арья и Смид [5] предложили алгоритм, использующий свойство пробелов для определения того, следует ли добавлять некоторое ребро к t-остовному графу. Используя свойство пробелов, можно доказать, что построенный остов имеет степень <math>O (1 / \theta^{d - 1}) \;</math> и вес O(log n • wt(MST(S))), где wt(MST(S)) – вес [[Минимальное остовное дерево|минимального остовного дерева]] S. | ||
'''WSPD-граф''' | '''WSPD-граф''' | ||
Пусть A и B – два конечных множества точек в <math>\mathcal{R}^d</math>. Будем называть A и B ''значительно удаленными'' по отношению к вещественному числу s > 0, если существуют два непересекающихся шара <math>C_A \;</math> и <math>C_B \;</math> одного и того же радиуса, такие, что <math>C_A \;</math> содержит A, <math>C_B \;</math> содержит B, а расстояние между <math>C_A \;</math> и <math>C_B \;</math> по меньшей мере в s раз превышает радиус <math>C_A \;</math>. Значение s называется коэффициентом | Пусть A и B – два конечных множества точек в <math>\mathcal{R}^d</math>. Будем называть A и B ''значительно удаленными'' по отношению к вещественному числу s > 0, если существуют два непересекающихся шара <math>C_A \;</math> и <math>C_B \;</math> одного и того же радиуса, такие, что <math>C_A \;</math> содержит A, <math>C_B \;</math> содержит B, а расстояние между <math>C_A \;</math> и <math>C_B \;</math> по меньшей мере в s раз превышает радиус <math>C_A \;</math>. Значение s называется ''коэффициентом удаленности''. | ||
'''Определение 1'''. Пусть S – множество точек в пространстве <math>\mathcal{R}^d \;</math>, а s > 0 – вещественное число. ''Декомпозицией значительно | '''Определение 1 [6]'''. Пусть S – множество точек в пространстве <math>\mathcal{R}^d \;</math>, а s > 0 – вещественное число. ''Декомпозицией на значительно удаленные пары'' (well-separated pair decomposition, WSPD) для S относительно s является последовательность <math>\{ A_i, B_i \} , 1 \le i \le m \;</math>, пар непустых подмножеств S, таких, что: | ||
(1) <math>A_i \cap B_i = \empty \;</math> для всех i = 1, 2, ... , m; | (1) <math>A_i \cap B_i = \empty \;</math> для всех i = 1, 2, ... , m; | ||
Строка 71: | Строка 71: | ||
Декомпозицию значительно | Декомпозицию на значительно удаленные пары разработали Кэллахан и Косарайю [6]. Построение t-остова при помощи этого подхода начинается с построения WSPD-декомпозиции S относительно коэффициента удаленности s = (4(t + 1))/(t - 1). Вначале положим остовный граф равным <math>G = (S, \empty) \;</math> и будем итеративно добавлять ребра следующим образом. Для каждой значительно удаленной пары {A, B} из декомпозиции к графу добавляется ребро (a, b), где a и b – произвольные точки из A и B, соответственно. Полученный граф называется WSPD-графом на S. | ||
'''Теорема 2. WSPD-граф представляет собой t-остов на множестве S, имеющий <math>O(s^d \cdot n) \;</math> ребер, и может быть построен за время <math>O(s^dn + n \; log \; n)</math>, где s = 4(t + 1)/(t | '''Теорема 2. WSPD-граф представляет собой t-остов на множестве S, имеющий <math>O(s^d \cdot n) \;</math> ребер, и может быть построен за время <math>O(s^dn + n \; log \; n)</math>, где s = 4(t + 1)/(t - 1).''' | ||
Строка 80: | Строка 80: | ||
''' | '''Граф с ограниченным диаметром''' | ||
Арья, Маунт и Смид [3] предложили модификацию алгоритма построения, в результате которой диаметр графа оказывается ограничен 2 log n. Вместо выбора произвольной точки в каждом значительно удаленном множестве их алгоритм тщательно выбирает особую точку для каждого множества. | Арья, Маунт и Смид [3] предложили модификацию алгоритма построения, в результате которой диаметр графа оказывается ограничен 2 log n. Вместо выбора произвольной точки в каждом значительно удаленном множестве их алгоритм тщательно выбирает особую точку для каждого множества. | ||
''' | '''Граф с ограниченной степенью''' | ||
Одна и та же точка v может быть частью нескольких значительно удаленных пар, и каждая из этих пар может сгенерировать ребро с конечной точкой в v. Арья и др. [2] предложили алгоритм, сохраняющий только самое короткое ребро для каждого направления конуса, объединив таким образом подход к построению <math>\Theta \;</math>-графа с подходом для WSPD-графа. Добавив шаг постобработки, рассматривающий все вершины с высокой степенью, можно получить t-остов степени <math>O(1 / (t - 1)^{2d - 1}) \;</math>. | Одна и та же точка v может быть частью нескольких значительно удаленных пар, и каждая из этих пар может сгенерировать ребро с конечной точкой в v. Арья и др. [2] предложили алгоритм, сохраняющий только самое короткое ребро для каждого направления конуса, объединив таким образом подход к построению <math>\Theta \;</math>-графа с подходом для WSPD-графа. Добавив шаг постобработки, рассматривающий все вершины с высокой степенью, можно получить t-остов степени <math>O(1 / (t - 1)^{2d - 1}) \;</math>. | ||
Строка 92: | Строка 92: | ||
'''Жадный остов''' | '''Жадный остов''' | ||
[[Жадный алгоритм]] был впервые представлен в 1989 году Берном (см. также работу Ленкопулоса и Лингаса [15]) и с тех пор широко исследовался. Граф, построенный при помощи жадного алгоритма, будем называть жадным остовом. Основная идея заключается в итеративном построении графа G. Ребра полного графа обрабатываются в порядке возрастания длины. Проверка ребра (u, v) включает запрос о кратчайшем пути в частичном остовном графе G. Если | [[Жадный алгоритм]] был впервые представлен в 1989 году Берном (см. также работу Ленкопулоса и Лингаса [15]) и с тех пор широко исследовался. Граф, построенный при помощи жадного алгоритма, будем называть жадным остовом. Основная идея заключается в итеративном построении графа G. Ребра полного графа обрабатываются в порядке возрастания длины. Проверка ребра (u, v) включает запрос о кратчайшем пути в частичном остовном графе G. Если длина кратчайшего пути в G между u и v не превышает t • |uv|, то ребро (u, v) отбрасывается, в противном случае оно добавляется к частичному остовному графу G. | ||
Дас, Нарасимхан и Салоу [ ] доказали, что жадный остов удовлетворяет так называемому ''свойству прыжков''. Множество неориентированных ребер E удовлетворяет свойству t-прыжков, если для любого <math>k \ge 2 \;</math> и любой возможной последовательности | Дас, Нарасимхан и Салоу [11] доказали, что жадный остов удовлетворяет так называемому ''свойству прыжков''. Множество неориентированных ребер E удовлетворяет свойству t-прыжков, если для любого <math>k \ge 2 \;</math> и любой возможной последовательности <math>\{ (p_1, q_1), ..., (p_k, q_k) \} \;</math> попарно различающихся ребер E выполняется соотношение | ||
<math>t \cdot |p_1 q_1| < \sum^k_{i = 2} |p_i q_i| + t \cdot \Big( \sum^{k - 1}_{i = 1} |q_i p_{i + 1}| + |p_k q_1| \Big)</math>. | |||
Используя свойство прыжков, можно ограничить вес графа. Дас и Нарасимхан [10] заметили, что жадный остов можно вычислить приближенно при сохранении свойства прыжков. Это наблюдение позволило разработать более быстрые алгоритмы для его построения. | |||
'''Теорема 3 ([14]). Приближенный жадный t-остов на множестве S, имеющий максимальную степень <math>O(1/(t - 1)^{2d - 1}) \;</math> и вес <math>O((1 / (t - 1)^{2d - 1} \cdot wt(MST(S))))</math>, может быть построен за время <math>O(n/((t - 1)^{2d}) \; log \; n)</math>.''' | |||
'''Отказоустойчивые остовы''' | |||
Понятие отказоустойчивых остовов было введено Левкопулосом и др. [16] в 1998 году. Оно означает, что при отказе одной или нескольких вершин либо одного или нескольких ребер остов должен сохранить свои основные свойства. В частности, в том, что осталось от остова после отказа вершин или ребер, по-прежнему должен сохраниться короткий путь между любыми двумя вершинами. Шумай и Чжао [8] показали, что жадный подход позволяет получить k-вершинный (или k-реберный) отказоустойчивый геометрический t-остов степени O(k) с общим весом <math>O(k^2 \cdot wt(MST(S))) \;</math>; эти границы являются асимптотически оптимальными. | |||
Для геометрических остовов естественно рассматривать ''отказы областей'' – то есть отказы, уничтожающие все вершины и ребра, пересекающие некоторую нерабочую геометрическую область. Пусть имеется нерабочая область F; граф <math>G \ominus F</math> представляет собой часть G, оставшуюся после того, как точки из S, находящиеся внутри области F, и все ребра, пересекающие F, были удалены из графа (см. рис. 1b). Абам и др. [1] показали, как строить t-остовы размера O(n log n), являющиеся отказоустойчивыми при отказе любой выпуклой области. Если разрешается использовать [[точка Штейнера|точки Штейнера]], можно получить t-остов линейного размера. | |||
Граф видимости на множестве попарно непересекающихся многоугольников называется графом взаимовидимых областей. Каждая | '''Остовы с препятствиями''' | ||
[[Visibility graph|Граф видимости]] на множестве попарно непересекающихся многоугольников называется ''графом взаимовидимых областей''. Каждая вершина многоугольника является вершиной в графе, а каждое ребро представляет видимую связь между ними: если две вершины видят друг друга, между ними строится ребро. Этот граф полезен благодаря тому, что содержит кратчайший путь, огибающий препятствия, между парой любых вершин. | |||
Строка 120: | Строка 122: | ||
Динамические и кинетические остовы | '''Динамические и кинетические остовы''' | ||
О динамических или кинетических остовах известно не так уж много. Арья и др. [ ] предложили структуру данных размера O(n log n), поддерживающую остов на базе списков с пропусками, описанный выше, с ожидаемым амортизированным временем вставки и удаления O(log | О динамических или кинетических остовах известно не так уж много. Арья и др. [4] предложили структуру данных размера <math>O(n \; log^d \; n)</math>, поддерживающую остов на базе списков с пропусками, описанный выше, с ожидаемым амортизированным временем вставки и удаления <math>O(log^d \; n \; log \; log \; n)</math> на основе модели случайных обновлений. | ||
Гао и др. [13] показали, как поддерживать t-остов размера O(n/(t- | Гао и др. [13] показали, как поддерживать t-остов размера <math>O(n/(t - 1)^d) \;</math> с максимальной степенью <math>O(1 / (t - 2)^d \; log \; \alpha)</math> и временем вставки и удаления <math>O((log \; \alpha)/(t - 1)^d)</math>, где <math>\alpha \;</math> обозначает пропорциональность S, т.е. отношение максимального расстояния между парой вершин к минимальному. Алгоритм основан на использовании иерархической структуры T с <math>O(log \; \alpha)</math> уровнями, каждый уровень которой содержит множество центров (подмножество S). Каждая вершина v на уровне i в структуре T связана ребрами со всеми остальными вершинами уровня i, находящимися на расстоянии не более <math>O(2^i / (t - 1)) \;</math> от v. Полученный граф является t-остовом S и может поддерживаться вышеописанным образом. Этот подход может быть обобщен до кинетического случая таким образом, чтобы суммарное количество событий в процессе поддержки остова составляло <math>O(n^2 \; log \; n)</math> при псевдоалгебраическом характере перемещения. Каждое событие может быть обновлено за время <math>O((log \; \alpha)/(t - 1)^d)</math>. | ||
== Применение == | == Применение == | ||
Алгоритмы построения разреженных остовов получили широкое применение в таких областях, как поиск в метрическом пространстве [1], который включает запрос по содержанию в мультимедийных объектах, текстовый информационный поиск, распознавание образов и | Алгоритмы построения разреженных остовов получили широкое применение в таких областях, как поиск в метрическом пространстве [1], который включает запрос по содержанию в мультимедийных объектах, текстовый информационный поиск, распознавание образов и аппроксимация функций. Еще одним примером является широковещательная рассылка в сетях коммуникаций [17]. Несколько хорошо известных теоретических работ также основываются на построении t-остовов – к примеру, Рао и Смит [19] совершили прорыв, предложив аппроксимационную схему с оптимальным временем O(n log n) для хорошо известной [[Евклидова задача коммивояжера|евклидовой задачи коммивояжера]], основанную на использовании t-остовов (или баньянов). Шумай и Лингас [7] предложили аппроксимационные схемы для задач о многосвязности с нахождением объектов минимальной стоимости в геометрических сетях. | ||
== Открытые вопросы == | == Открытые вопросы == | ||
В этой сфере остается много нерешенных задач. Стоит упомянуть некоторые из них: | В этой сфере остается много нерешенных задач. Стоит упомянуть некоторые из них: | ||
1. Разработка алгоритма построения динамического t-остова, который можно обновлять за время O( | 1. Разработка алгоритма построения динамического t-остова, который можно обновлять за время <math>O(log^c \; n)</math> для некоторого константного значения c. | ||
2. Определение, существует ли отказоустойчивый t-остов линейного размера для ситуации отказов выпуклых областей. | 2. Определение, существует ли отказоустойчивый t-остов линейного размера для ситуации отказов выпуклых областей. | ||
3. Алгоритм построения k-вершинного отказоустойчивого остова, который предложили Шумай и Чжао [8], позволяет получить k-вершинный отказоустойчивый t-остов степени O(k) с общим весом O( | 3. Алгоритм построения k-вершинного отказоустойчивого остова, который предложили Шумай и Чжао [8], позволяет получить k-вершинный отказоустойчивый t-остов степени O(k) с общим весом <math>O(k^2 \cdot wt(MST(S))) \;</math>. Однако до сих пор неизвестны способы его эффективной реализации. Можно ли вычислить такой остов за время O(n log n + kn)? | ||
4. Ограничение веса остовов на базе списков с пропусками. | 4. Ограничение веса остовов на базе списков с пропусками. | ||
== Экспериментальные результаты == | == Экспериментальные результаты == | ||
Задача построения остовов активно исследовалась с теоретической точки зрения, но получила гораздо меньше внимания с практической, или экспериментальной, стороны. Наварро и Паредес [ ] предложили четыре эвристики для множеств точек в пространстве высоких размерностей (d = 20) и эмпирическими методами показали, что время выполнения | Задача построения остовов активно исследовалась с теоретической точки зрения, но получила гораздо меньше внимания с практической, или экспериментальной, стороны. Наварро и Паредес [1] предложили четыре эвристики для множеств точек в пространстве высоких размерностей (d = 20) и эмпирическими методами показали, что время выполнения составляет <math>O(n^{2,24}) \;</math>, а количество ребер в полученных графах – <math>O(n^{1,13}) \;</math>. Недавно Фарши и Гудмундссон [12] провели тщательное сравнение алгоритмов построения остовов, упоминавшихся в разделе «Остовы на точках в евклидовом пространстве». | ||
== См. также == | == См. также == |
правок