Алгоритм DC-дерева для k серверов на деревьях: различия между версиями

Перейти к навигации Перейти к поиску
Нет описания правки
Нет описания правки
Строка 10: Строка 10:
В ''онлайн-версии'' k-серверной задачи решение о том, какой сервер должен быть перемещен по каждому запросу <math>r_{i}</math>, должно приниматься до выдачи следующего запроса <math>r_{i+1}</math>. Иными словами, выбор этого сервера является функцией от запросов <math>r_{1}, r_{2}</math>, ..., <math>r_{i}</math>. Легко заметить, что в этом онлайн-сценарии гарантировать нахождение оптимального плана невозможно. Точность онлайн-алгоритмов нередко измеряется при помощи сравнительного анализа. Если A – онлайн-алгоритм для k-серверной задачи, обозначим за <math>cost_{A}(\varrho)</math> стоимость плана, производимого алгоритмом A на последовательности запросов <math>\varrho</math>
В ''онлайн-версии'' k-серверной задачи решение о том, какой сервер должен быть перемещен по каждому запросу <math>r_{i}</math>, должно приниматься до выдачи следующего запроса <math>r_{i+1}</math>. Иными словами, выбор этого сервера является функцией от запросов <math>r_{1}, r_{2}</math>, ..., <math>r_{i}</math>. Легко заметить, что в этом онлайн-сценарии гарантировать нахождение оптимального плана невозможно. Точность онлайн-алгоритмов нередко измеряется при помощи сравнительного анализа. Если A – онлайн-алгоритм для k-серверной задачи, обозначим за <math>cost_{A}(\varrho)</math> стоимость плана, производимого алгоритмом A на последовательности запросов <math>\varrho</math>
, а за <math>opt(\varrho)</math> -
, а за <math>opt(\varrho)</math> -
стоимость оптимального плана. Назовем алгоритм A R-конкурентным, если <math>cost_{A}(\varrho) < R - 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, и на данный момент это наилучшая известная верхняя граница.
Алгоритм DC-дерева для k серверов на деревьях. Рис. 1
Алгоритм DC-TREE обрабатывает запрос для r. Исходная конфигурация приведена слева; конфигурация после окончания обработки – справа. Вначале все серверы активны. Когда сервер 3 достигает точки x, сервер 1 становится неактивным. Когда сервер 3 достигает точки y, сервер 2 становится неактивным.
 
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-серверную гипотезу привели к открытию k-конкурентных алгоритмов для некоторых ограниченных классов метрических пространств, включая алгоритм DC-TREE для деревьев [4], представленный в следующем разделе. (См. другие примеры в [1, 2, 3]). Дерево представляет собой метрическое пространство, определяемое как связный ациклический граф, дуги которого рассматриваются как отрезки прямых произвольной положительной длины. Это метрическое пространство включает как вершины деревьев, так и точки на дугах, а расстояния измеряются вдоль (уникальных) кратчайших путей.


Строка 27: Строка 22:
Алгоритм DC-TREE
Алгоритм DC-TREE
По запросу r алгоритм перемещает все активные серверы, непрерывно и с одинаковой скоростью, в направлении r, пока один из серверов не достигнет запроса. Отметим, что в этом процессе некоторые серверы могут стать неактивными; в таком случае они останавливаются. Очевидно, что быстрее других до точки r доберется тот сервер, который был ближе всего к r в момент выдачи запроса r. На рис. 1 представлена работа алгоритма DC-TREE по запросу r.
По запросу r алгоритм перемещает все активные серверы, непрерывно и с одинаковой скоростью, в направлении r, пока один из серверов не достигнет запроса. Отметим, что в этом процессе некоторые серверы могут стать неактивными; в таком случае они останавливаются. Очевидно, что быстрее других до точки r доберется тот сервер, который был ближе всего к r в момент выдачи запроса r. На рис. 1 представлена работа алгоритма DC-TREE по запросу r.
Алгоритм DC-дерева для k серверов на деревьях. Рис. 1
Алгоритм 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]:


Источник — http://pco.iis.nsk.su/wega/index.php/Алгоритм_DC-дерева_для_k_серверов_на_деревьях