Пусть некоторый полный взвешенный неориентированный граф. Построим второй граф , добавив ребра одно за другим из в . Добавим края для всего.
Каждый раз, когда мы добавляем одно ребро к , мы рассматриваем кратчайшие расстояния между всеми парами в и . Мы посчитаем, сколько из этих кратчайших расстояний изменилось в результате сложения . Пусть будет числом кратчайших расстояний, которые меняются при добавлении th ребро, и пусть будет количеством ребер, которые мы добавим в итоге.
Насколько большой ?
Поскольку , C = O ( n 2 ) . Может ли эта граница быть улучшена? Обратите внимание, что я определяю C как среднее по всем ребрам, которые были добавлены, поэтому один раунд, в котором изменяется большое количество расстояний, не столь интересен, хотя он доказывает, что C = Ω ( n ) .
У меня есть алгоритм для жадного вычисления геометрического t-гаечного ключа, который работает за , поэтому, если C равно o ( n 2 ) , мой алгоритм работает быстрее, чем исходный жадный алгоритм, и если C действительно мал потенциально быстрее, чем самый известный алгоритм (хотя я сомневаюсь в этом).
Некоторые специфические для задачи свойства, которые могут помочь с хорошей границей: добавляемое ребро всегда имеет больший вес, чем любое ребро, уже существующее в графе (не обязательно строго больше). Кроме того, его вес меньше, чем кратчайший путь между u и v .
Можно предположить, что вершины соответствуют точкам в 2d плоскости, а расстояния между вершинами являются евклидовыми расстояниями между этими точками. То есть каждая вершина соответствует некоторой точке ( x , y ) на плоскости, а для ребра ( u , v ) = ( ( x 1 , y 1 ) , ( x 2 , y 2 ) ) ее вес равен к √
источник
Ответы:
Рассмотрим следующую линейную цепочку с узлами, n ребрами и порочно выбранными весами:n+1 n
[ источник ]
Ясно, что ребра могли быть добавлены в порядке их весов, и их . Добавление пунктирного ребра (что допустимо) создает более короткие пути для всех пар ( u i , b j ) с i , j = 1 , … , k . Как k ≈ nn∈O(|V|) (ui,bj) i,j=1,…,k и предполагая, чтоn∈Θ(|V|), первая и последняя строки содержатΘ(|V|) помногим узлам, и сложение вызываетΘ(|V|2)многих изменений кратчайшего пути.k≈n4 n∈Θ(|V|) Θ(|V|) Θ(|V|2)
Теперь мы можем двигаться «наружу», то есть добавить следующее ребро с весом между u k - 1 и b k - 1 и т. Д .; если мы продолжим это до ( u 1 , b 1 ) , мы вызовем всего Θ ( | V | 3 ) изменений кратчайшего пути.n+2 uk−1 bk−1 (u1,b1) Θ(|V|3)
Если это не убедит вас, обратите внимание, что вы можете начать этот «процесс» с и работать оттуда; Таким образом , вы добавить ≈ п ребер , которые вызывают в общей сложности ≈ Х п я = 1 я 2 ∈ thetas ; ( п 3 ) = & thetas ( | V | 3 ) много кратчайших изменений пути --- это просто невозможно сделать , чтобы поместиться на одном экран.(c1,c2) ≈n ≈∑ni=1i2∈Θ(n3)=Θ(|V|3)
источник