4501
правка
Алгоритм DC-дерева для k серверов на деревьях: различия между версиями
Перейти к навигации
Перейти к поиску
Алгоритм DC-дерева для k серверов на деревьях (посмотреть исходный код)
Версия от 13:19, 16 декабря 2011
, 16 декабря 2011нет описания правки
Irina (обсуждение | вклад) Нет описания правки |
Irina (обсуждение | вклад) Нет описания правки |
||
| Строка 12: | Строка 12: | ||
стоимость оптимального плана. Назовем алгоритм A ''R-конкурентным'', если <math>cost_{A}(\varrho) < R \cdot opt(\varrho) + B</math>, где B – константа, которая может зависеть от M и <math>r_{0}</math>. Минимальное значение R называется ''коэффициентом конкурентоспособности'' A. Разумеется, чем меньше R, тем лучше. | стоимость оптимального плана. Назовем алгоритм A ''R-конкурентным'', если <math>cost_{A}(\varrho) < R \cdot opt(\varrho) + B</math>, где B – константа, которая может зависеть от M и <math>r_{0}</math>. Минимальное значение R называется ''коэффициентом конкурентоспособности'' A. Разумеется, чем меньше R, тем лучше. | ||
k-серверная задача была предложена Манассом, Макгиохом и Слейтором [7, 8], доказавшими, что не существует R-конкурентного онлайн-алгоритма для R < k для любого метрического пространства с не менее чем k + 1 точками. Они также представили 2-конкурентный алгоритм для k = 2 и сформулировали то, что позднее стали называть ''k-серверной гипотезой'', которая утверждает, что существует k-конкурентный онлайн-алгоритм для любого k. Кутсупиас и Пападимитриу [5, 6] доказали, что так называемый алгоритм рабочей функции имеет коэффициент конкурентоспособности не более 2k – 1, и на данный момент это наилучшая известная верхняя граница. | |||
Попытки доказать k-серверную гипотезу привели к открытию k-конкурентных алгоритмов для некоторых ограниченных классов метрических пространств, включая алгоритм DC-TREE для деревьев [4], представленный в следующем разделе. (См. другие примеры в [1, 2, 3]). Дерево представляет собой метрическое пространство, определяемое как связный ациклический граф, дуги которого рассматриваются как отрезки прямых произвольной положительной длины. Это метрическое пространство включает как вершины деревьев, так и точки на дугах, а расстояния измеряются вдоль (уникальных) кратчайших путей. | k-серверная задача была предложена Манассом, Макгиохом и Слейтором [7, 8], доказавшими, что не существует R-конкурентного онлайн-алгоритма для R < k для любого метрического пространства с не менее чем k + 1 точками. Они также представили 2-конкурентный алгоритм для k = 2 и сформулировали то, что позднее стали называть ''k-серверной гипотезой'', которая утверждает, что существует k-конкурентный онлайн-алгоритм для любого k. Кутсупиас и Пападимитриу [5, 6] доказали, что так называемый ''алгоритм рабочей функции'' имеет коэффициент конкурентоспособности не более 2k – 1, и на данный момент это наилучшая известная верхняя граница. | ||
Попытки доказать k-серверную гипотезу привели к открытию k-конкурентных алгоритмов для некоторых ограниченных классов метрических пространств, включая алгоритм DC-TREE для деревьев [4], представленный в следующем разделе. (См. другие примеры в [1, 2, 3]). [[Дерево]] представляет собой метрическое пространство, определяемое как связный ациклический граф, дуги которого рассматриваются как отрезки прямых произвольной положительной длины. Это метрическое пространство включает как вершины деревьев, так и точки на дугах, а расстояния измеряются вдоль (уникальных) кратчайших путей. | |||
== Основные результаты == | == Основные результаты == | ||
Пусть T – дерево, согласно вышеприведенному определению. Пусть даны текущая конфигурация сервера S = {<math>s_{1}</math>, ..., <math>s_{k}</math>}, где <math>s_{ | Пусть T – дерево, согласно вышеприведенному определению. Пусть даны текущая конфигурация сервера S = {<math>s_{1}</math>, ..., <math>s_{k}</math>}, где <math>s_{j}</math> обозначает местоположение сервера j, и точка запроса r; алгоритм выполняет перемещение нескольких серверов, один из которых окажется в результате в точке r. Для двух точек x, y <math>\in </math> T, обозначим через [x, y] уникальный путь из x в у в дереве T. Сервер j называется ''активным'', если не существует другого сервера в [<math>s_{j}</math>, r] – {<math>s_{j}</math>}, и j является сервером с минимальным индексом, расположенным в s<math>_{j}</math> (последнее условие необходимо только для разрыва связей). | ||
Алгоритм DC-TREE | Алгоритм DC-TREE | ||
По запросу r алгоритм перемещает все активные серверы, непрерывно и с одинаковой скоростью, в направлении r, пока один из серверов не достигнет запроса. Отметим, что в этом процессе некоторые серверы могут стать неактивными; в таком случае они останавливаются. Очевидно, что быстрее других до точки r доберется тот сервер, который был ближе всего к r в момент выдачи запроса r. На | По запросу r алгоритм перемещает все активные серверы, непрерывно и с одинаковой скоростью, в направлении r, пока один из серверов не достигнет запроса. Отметим, что в этом процессе некоторые серверы могут стать неактивными; в таком случае они останавливаются. Очевидно, что быстрее других до точки r доберется тот сервер, который был ближе всего к r в момент выдачи запроса r. На иллюстрации представлена работа алгоритма DC-TREE по запросу r. | ||
[[Файл:DCtree_pic1.jpg]] | |||
[[Файл:DCtree_pic2.png]] | |||
''Алгоритм DC-TREE обрабатывает запрос для r. Исходная конфигурация приведена слева; конфигурация после окончания обработки – справа. Вначале все серверы активны. Когда сервер 3 достигает точки x, сервер 1 становится неактивным. Когда сервер 3 достигает точки y, сервер 2 становится неактивным. | |||
'' | |||
Конкурентный анализ алгоритма DC-TREE основан на рассуждениях о потенциале. Стоимость алгоритма DC-TREE сравнивается со стоимостью алгоритма противоположной стороны, выполняющей запросы на собственных серверах. Обозначим за A конфигурацию серверов «противника» на данном этапе и определим потенциал , где D(S,A) – стоимость алгоритма нахождения соответствия с минимальной стоимостью между S и A. На каждом этапе противная сторона в первую очередь перемещает один из своих серверов в r. На данном под-этапе потенциал возрастает не более чем в k раз по сравнению со стоимостью противной стороны. Затем DC-TREE выполняет запрос. Можно показать, что сумма Ф и стоимости DC-TREE не возрастает. Два этих факта, с учетом накопления по всей последовательности запросов, приводят к следующему результату [4]: | Конкурентный анализ алгоритма DC-TREE основан на рассуждениях о потенциале. Стоимость алгоритма DC-TREE сравнивается со стоимостью алгоритма противоположной стороны, выполняющей запросы на собственных серверах. Обозначим за A конфигурацию серверов «противника» на данном этапе и определим потенциал , где D(S,A) – стоимость алгоритма нахождения соответствия с минимальной стоимостью между S и A. На каждом этапе противная сторона в первую очередь перемещает один из своих серверов в r. На данном под-этапе потенциал возрастает не более чем в k раз по сравнению со стоимостью противной стороны. Затем DC-TREE выполняет запрос. Можно показать, что сумма Ф и стоимости DC-TREE не возрастает. Два этих факта, с учетом накопления по всей последовательности запросов, приводят к следующему результату [4]: | ||