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

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

Вступление

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

Один из способов сделать это - просто запустить Алгоритм Дейкстры. Это требует времени , и не требует дополнительного места (кроме самого графика).

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

Простая структура данных, позволяющая достичь этой цели, - это матрица который определяет для каждой пары узлов расстояние между ними. Эта структура позволяет нам отвечать на запросы в постоянное время. , но требует дополнительное пространство. Его можно инициализировать вовремя используя алгоритм кратчайших путей для всех пар, такой как Алгоритм Флойда-Уоршолла.

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

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

Торуп и Цвик[1] описать более 10 различных ДО. Затем они предлагают новый ДЕЛАТЬ, который для каждого k, требует места , так что на любой последующий запрос расстояния можно приблизительно ответить вовремя . Приблизительное возвращаемое расстояние является не более чем растяжением. , то есть частное, полученное путем деления оценочного расстояния на фактическое, находится между 1 и . Время инициализации .

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

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

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

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

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

  • Для каждого : содержит каждый элемент , независимо, с вероятностью . Обратите внимание, что ожидаемый размер является . Элементы называются i-центры.

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

  • Для каждого : и . Т.е., i-центр ближайший к v, и расстояние между ними. Обратите внимание, что для фиксированного v, это расстояние слабо увеличивается с увеличением я. Также обратите внимание, что для каждого v, и .
  • .

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

  • Для каждого : . содержит все вершины в которые строго ближе к v чем все вершины в . Частичные союзы s - шары увеличивающегося диаметра, содержащие вершины с расстояниями до первой вершины следующего уровня.

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

Можно показать, что ожидаемый размер самое большее .

Для каждой связки , построить хеш-таблица это верно для каждого , Расстояние .

Общий размер структуры данных составляет

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

  • пока :
    • (поменять местами два входных узла; это не меняет расстояние между ними, так как граф неориентированный).
  • возвращаться

Можно показать, что на каждой итерации расстояние растет максимум . С , есть не более k-1 итераций, так что наконец . Теперь по неравенство треугольника, , поэтому возвращаемое расстояние не превышает .

Улучшения

Вышеупомянутый результат был позже улучшен Патраску и Родитти.[2] кто предлагает DO размера который возвращает приближение с коэффициентом 2.

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

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

Считается, что проблема SIO не имеет нетривиального решения. То есть требуется пространство для ответов на запросы во времени , например используя п-к-п таблица с пересечением между каждыми двумя наборами. Если эта гипотеза верна, это означает, что не существует 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.