4431
правка
Декомпозиция на значительно удаленные пары: различия между версиями
Материал из WEGA
Декомпозиция на значительно удаленные пары (посмотреть исходный код)
Версия от 12:12, 13 марта 2018
, 13 марта 2018→Применение
Irina (обсуждение | вклад) м (→Применение) |
Irina (обсуждение | вклад) м (→Применение) |
||
| Строка 63: | Строка 63: | ||
• '''Самый дальний сосед, диаметр, центр'''. Самым дальним соседом точки <math>p \in S_1 \;</math> является точка в <math>S_1 \;</math>, находящаяся на максимальном расстоянии от p. Родственными задачами являются задачи вычисления [[диаметр|диаметра]], максимального среди попарных кратчайших расстояний между точками в S1, а также вычисление ''центра'' – точки, максимальное расстояние от которой до всех остальных точек множества является минимальным. | • '''Самый дальний сосед, диаметр, центр'''. Самым дальним соседом точки <math>p \in S_1 \;</math> является точка в <math>S_1 \;</math>, находящаяся на максимальном расстоянии от p. Родственными задачами являются задачи вычисления [[диаметр|диаметра]], максимального среди попарных кратчайших расстояний между точками в S1, а также вычисление ''центра'' – точки, максимальное расстояние от которой до всех остальных точек множества является минимальным. | ||
• '''Ближайший сосед, пара ближайших точек'''. Ближайшим соседом точки <math>p \in S_1 \;</math> является точка в <math>S_1 \;</math>, находящаяся на минимальном расстоянии от p. Родственными задачами являются задачи вычисления ''пары ближайших точек'', то есть пары с минимальным кратчайшим расстоянием, а также | • '''Ближайший сосед, пара ближайших точек'''. Ближайшим соседом точки <math>p \in S_1 \;</math> является точка в <math>S_1 \;</math>, находящаяся на минимальном расстоянии от p. Родственными задачами являются задачи вычисления ''пары ближайших точек'', то есть пары с минимальным кратчайшим расстоянием, а также ''бихроматической пары ближайших точек'' – пары, для которой расстояние между точками двух разных множеств является минимальным. | ||
• '''Медиана'''. Медианой множества S является точка в S с минимальным средним (или суммарным) расстоянием до всех остальных точек. | • '''Медиана'''. Медианой множества S является точка в S с минимальным средним (или суммарным) расстоянием до всех остальных точек. | ||
• '''Коэффициент растяжения'''. Для графа G, определенного на множестве S, коэффициентом растяжения относительно метрики на графе единичных дисков является максимальное соотношение | • '''Коэффициент растяжения'''. Для графа G, определенного на множестве S, коэффициентом растяжения относительно метрики на графе единичных дисков является максимальное соотношение <math>\pi_G (p, q) / \pi(p, q) \;</math>, где <math>\pi_G, \pi \;</math> – расстояния, порожденные G и графом единичных дисков, соответственно. | ||
Все вышеупомянутые задачи могут быть точно или приближенно решены для точек на евклидовой плоскости. Однако для метрик, порожденных графами (даже планарными графами), было получено относительно мало результатов, помимо решения дорогостоящей задачи нахождения кратчайших путей между всеми парами. Для вычисления диаметра существует простой метод с линейным временем выполнения, обеспечивающий 2-аппроксимацию (*), а также алгоритм 4/3-аппроксимации с временем выполнения O( | Все вышеупомянутые задачи могут быть точно или приближенно решены для точек на евклидовой плоскости. Однако для метрик, порожденных графами (даже планарными графами), было получено относительно мало результатов, помимо решения дорогостоящей задачи нахождения кратчайших путей между всеми парами. Для вычисления диаметра существует простой метод с линейным временем выполнения, обеспечивающий 2-аппроксимацию (*), а также алгоритм 4/3-аппроксимации с временем выполнения <math>O(m \sqrt{n \; log \; n} + n^2 \; log \; n)</math> для графа с n вершинами и m ребрами, предложенный Эйнгвортом и др. [1]. | ||
''(*) Выберите произвольную вершину v и вычислите дерево кратчайших путей с корнем в v. Предположим, что самая дальняя от v вершина находится на расстоянии D от нее. Тогда, согласно неравенству треугольников, диаметр графа не превышает 2D.'' | |||
Используя декомпозицию значительно удаленных пар, Гао и Чжан [ ] показали, что можно получить более эффективную аппроксимацию вышеприведенных задач о близости для метрики на графе единичных дисков. В частности, можно получить алгоритмы с почти линейным временем выполнения для вычисления 2,42-аппроксимации и алгоритмы с временем выполнения O( | Используя декомпозицию значительно удаленных пар, Гао и Чжан [7] показали, что можно получить более эффективную аппроксимацию вышеприведенных задач о близости для метрики на графе единичных дисков. В частности, можно получить алгоритмы с почти линейным временем выполнения для вычисления 2,42-аппроксимации и алгоритмы с временем выполнения <math>O(n \sqrt{n \; log \; n} / \varepsilon^3)</math> для вычисления <math>(1 + \varepsilon) \;</math>-аппроксимации для любого <math>\varepsilon > 0 \;</math>. Кроме того, декомпозицию значительно удаленных пар можно использовать для получения оракула расстояния, требующего <math>O(n \; log \; n / \varepsilon^4)</math> объема памяти, такого, что на любой <math>(1 + \varepsilon) \;</math>-запрос расстояния в графе единичных дисков можно получить ответ за время O(1). | ||
Узким местом всех вышеупомянутых алгоритмов является приближенное вычисление расстояний по кратчайшим путям между O( | Узким местом всех вышеупомянутых алгоритмов является приближенное вычисление расстояний по кратчайшим путям между O(n log n) парами. Алгоритм работы [7] только строит декомпозицию значительно удаленных пар, не делая подходящего приближенного вычисления расстояний. Коэффициент аппроксимации и время выполнения определяются соответствующими параметрами алгоритма аппроксимации, выполняющего оценку расстояния между каждой парой в декомпозиции значительно удаленных пар. После выполнения оценки расстояния оставшаяся часть вычисления требует почти линейного времени. | ||
Для графа общего вида неизвестно, можно ли вычислить расстояния по кратчайшим путям между O(n log n) парами значительно быстрее, чем расстояния по кратчайшим путям между всеми парами. Для планарного графа можно ли вычислить расстояния по кратчайшим путям между O(n log n) парами за время O( | Для графа общего вида неизвестно, можно ли вычислить расстояния по кратчайшим путям между O(n log n) парами значительно быстрее, чем расстояния по кратчайшим путям между всеми парами. Для планарного графа можно ли вычислить расстояния по кратчайшим путям между O(n log n) парами за время <math>O(n \sqrt{n \; log \; n)</math>, используя сепараторы размера <math>O( \sqrt{n}) \;</math> [2]. Этот метод можно расширить на графы единичных дисков с ограниченной константой плотностью, поскольку такие графы удовлетворяют свойству сепараторов, аналогичного свойству для планарных графов [ ]. Что касается аппроксимации, Торуп [15] недавно предложил алгоритм для планарных графов, способный отвечать на запросы о (1 + \varepsilon)-кратчайшем расстоянии за время O(1/\varepsilon) после выполнения предварительной обработки, требующей почти линейного времени. К сожалению, алгоритм Торупа использует сбалансированные сепараторы кратчайших путей в планарных графах, которые невозможно сходу распространить на графы единичных дисков. С другой стороны, известно, что существует планарный 2,42-остов для графа единичных дисков [11]. Применяя алгоритм Торупа к этому планарному остову, можно вычислить 2,42-аппроксимацию кратчайшего расстояния для O(nlogn) пар за почти линейное время. | ||
== Открытые вопросы == | == Открытые вопросы == | ||
