Оракул расстояния - Distance oracle - Wikipedia

В вычисление, а расстояние оракул (DO) это структура данных для вычисления расстояний между вершинами в график.

Вступление

Позволять грамм(V,E) - неориентированный взвешенный граф с п = |V| узлы и м = |E| края. Хотим ответить на вопросы вида «какое расстояние между узлами s ит?".

Один из способов сделать это - просто запустить Алгоритм Дейкстры. Это требует времени ${\displaystyle O(m+n\log n)}$, и не требует дополнительного места (кроме самого графика).

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

Простая структура данных, позволяющая достичь этой цели, - это матрица который определяет для каждой пары узлов расстояние между ними. Эта структура позволяет нам отвечать на запросы в постоянное время. ${\displaystyle O(1)}$, но требует ${\displaystyle O(n^{2})}$ дополнительное пространство. Его можно инициализировать вовремя ${\displaystyle O(n^{3})}$ используя алгоритм кратчайших путей для всех пар, такой как Алгоритм Флойда-Уоршолла.

ДО находится между этими двумя крайностями. Он использует менее ${\displaystyle O(n^{2})}$ пространство, чтобы ответить на запросы менее чем за ${\displaystyle O(m+n\log n)}$ время. Большинству DO приходится идти на компромисс с точностью, то есть они возвращают не точное расстояние, а его приближение с постоянным коэффициентом.

Приблизительный DO

Торуп и Цвик^[1] описать более 10 различных ДО. Затем они предлагают новый ДЕЛАТЬ, который для каждого k, требует места ${\displaystyle O(kn^{1+1/k})}$, так что на любой последующий запрос расстояния можно приблизительно ответить вовремя ${\displaystyle O(k)}$. Приблизительное возвращаемое расстояние является не более чем растяжением. ${\displaystyle 2k-1}$, то есть частное, полученное путем деления оценочного расстояния на фактическое, находится между 1 и ${\displaystyle 2k-1}$. Время инициализации ${\displaystyle O(kmn^{1/k})}$.

Некоторые особые случаи включают:

• За ${\displaystyle k=1}$ получаем простую матрицу расстояний.
• За ${\displaystyle k=2}$ мы получаем структуру, используя ${\displaystyle O(n^{1.5})}$ пространство, которое отвечает на каждый запрос за постоянное время и коэффициент приближения не более 3.
• За ${\displaystyle k=\lfloor \log n\rfloor }$, мы получаем структуру, используя ${\displaystyle O(n\log n)}$ пространство, время запроса ${\displaystyle O(\log n)}$, и растянуть ${\displaystyle O(\log n)}$.

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

DO для общих метрических пространств

Оракул построен из убывающей коллекции k+1 набор вершин:

• ${\displaystyle A_{0}=V}$
• Для каждого ${\displaystyle i=1,\ldots ,k-1}$: ${\displaystyle A_{i}}$ содержит каждый элемент ${\displaystyle A_{i-1}}$, независимо, с вероятностью ${\displaystyle n^{-1/k}}$. Обратите внимание, что ожидаемый размер ${\displaystyle A_{i}}$ является ${\displaystyle n^{1-i/k}}$. Элементы ${\displaystyle A_{i}}$ называются i-центры.
• ${\displaystyle A_{k}=\emptyset }$

Для каждого узла vрассчитайте расстояние до каждого из этих наборов:

• Для каждого ${\displaystyle i=0,\ldots ,k-1}$: ${\displaystyle d(A_{i},v)=\min {(d(w,v)|w\in A_{i}}}$ и ${\displaystyle p_{i}(v)=\arg \min {(d(w,v)|w\in A_{i}}}$. Т.е., ${\displaystyle p_{i}(v)}$ i-центр ближайший к v, и ${\displaystyle d(A_{i},v)}$ расстояние между ними. Обратите внимание, что для фиксированного v, это расстояние слабо увеличивается с увеличением я. Также обратите внимание, что для каждого v, ${\displaystyle d(A_{0},v)=0}$ и ${\displaystyle p_{0}(v)=v}$.
• ${\displaystyle d(A_{k},v)=\infty }$.

Для каждого узла v, рассчитать:

• Для каждого ${\displaystyle i=0,\ldots ,k-1}$: ${\displaystyle B_{i}(v)=\{w\in A_{i}\setminus A_{i+1}|d(w,v)<d(A_{i+1},v)\}}$. ${\displaystyle B_{i}(v)}$ содержит все вершины в ${\displaystyle A_{i}}$ которые строго ближе к v чем все вершины в ${\displaystyle A_{i+1}}$. Частичные союзы ${\displaystyle B_{i}}$s - шары увеличивающегося диаметра, содержащие вершины с расстояниями до первой вершины следующего уровня.

Для каждого vвычислить его связка:

• ${\displaystyle B(v)=\bigcup _{i=0}^{k-1}B_{i}(v).}$

Можно показать, что ожидаемый размер ${\displaystyle B(v)}$ самое большее ${\displaystyle kn^{1/k}}$.

Для каждой связки ${\displaystyle B(v)}$, построить хеш-таблица это верно для каждого ${\displaystyle w\in B(V)}$, Расстояние ${\displaystyle d(w,v)}$.

Общий размер структуры данных составляет ${\displaystyle O(kn+\Sigma |B(v)|)=O(kn+nkn^{1/k})=O(kn^{1+1/k})}$

После инициализации этой структуры следующий алгоритм находит расстояние между двумя узлами: ты и v:

• ${\displaystyle w:=u,i:=0}$
• пока ${\displaystyle w\notin B(v)}$:
  • ${\displaystyle i:=i+1}$
  • ${\displaystyle (u,v):=(v,u)}$ (поменять местами два входных узла; это не меняет расстояние между ними, так как граф неориентированный).
  • ${\displaystyle w:=p_{i}(u)}$
• возвращаться ${\displaystyle d(w,u)+d(w,v)}$

Можно показать, что на каждой итерации расстояние ${\displaystyle d(w,u)}$ растет максимум ${\displaystyle d(v,u)}$. С ${\displaystyle A_{k-1}\subseteq B(v)}$, есть не более k-1 итераций, так что наконец ${\displaystyle d(w,u)\leq (k-1)d(v,u)}$. Теперь по неравенство треугольника, ${\displaystyle d(w,v)\leq d(w,u)+d(u,v)\leq kd(v,u)}$, поэтому возвращаемое расстояние не превышает ${\displaystyle (2k-1)d(u,v)}$.

Улучшения

Вышеупомянутый результат был позже улучшен Патраску и Родитти.^[2] кто предлагает DO размера ${\displaystyle O(n^{4/3}m^{1/3})}$ который возвращает приближение с коэффициентом 2.

Редукция из множества оракулов пересечения

Если существует ДО с коэффициентом аппроксимации не более 2, то можно построить установить оракул пересечения (SIO) со временем запроса ${\displaystyle O(1)}$ и требования к пространству ${\displaystyle O(N+n)}$, куда п количество комплектов и N сумма их размеров; видеть установить оракул пересечения # Приведение к приблизительному расстоянию оракул.

Считается, что проблема SIO не имеет нетривиального решения. То есть требуется ${\displaystyle \Omega (n^{2})}$ пространство для ответов на запросы во времени ${\displaystyle O(1)}$, например используя п-к-п таблица с пересечением между каждыми двумя наборами. Если эта гипотеза верна, это означает, что не существует DO с коэффициентом приближения менее 2 и постоянным временем запроса.^[2]

Рекомендации

1. Торуп, М.; Цвик, У. (2005). «Приблизительное расстояние оракулов». Журнал ACM. 52: 1–24. CiteSeerX  10.1.1.295.4480. Дои:10.1145/1044731.1044732.
2. Патраску, М .; Родитти, Л. (2010). Дистанционные оракулы за пределами границы Торуп-Цвик. 2010 51-й ежегодный симпозиум IEEE по основам компьютерных наук (FOCS). п. 815. Дои:10.1109 / FOCS.2010.83. ISBN  978-1-4244-8525-3.