Дистанционный оракул

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

Введение

Пусть G ( V , E ) — неориентированный взвешенный граф с n = | В | узлы и m = | Е | края. Нам хотелось бы ответить на запросы вида «каково расстояние между узлами s и t ?».

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

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

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

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

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

Торуп и Цвик описать более 10 различных DO. Затем они предлагают новый DO, который для каждого k требует места. $O(kn^{1+1/k})$, так что на любой последующий запрос о расстоянии можно приблизительно ответить за время $O(k)$. Возвращенное приблизительное расстояние не превышает максимального значения. $2k-1$, то есть частное, полученное путем деления расчетного расстояния на фактическое расстояние, лежит между 1 и $2k-1$. Время инициализации $O(kmn^{1/k})$.

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

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

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

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

Оракул состоит из уменьшающегося набора из k +1 наборов вершин:

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

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

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

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

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

Для каждого v вычислите его группу :

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

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

За каждую связку $B(v)$, создайте хеш-таблицу , содержащую все $w\in B(V)$, расстояние $d(w,v)$.

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

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

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

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

Улучшения

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

Сокращение от оракула пересечения множества

Если имеется ДО с коэффициентом аппроксимации не более 2, то можно построить оракул пересечения множеств (SIO) со временем запроса. $O(1)$ и требования к пространству $O(N+n)$, где n — количество наборов, а N — сумма их размеров; см. установленное пересечение oracle#Reduction до приблизительного расстояния oracle .

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