4501
правка
Алгоритм DC-дерева для k серверов на деревьях: различия между версиями
Перейти к навигации
Перейти к поиску
Алгоритм DC-дерева для k серверов на деревьях (посмотреть исходный код)
Версия от 13:13, 16 декабря 2011
, 16 декабря 2011нет описания правки
Irina (обсуждение | вклад) Нет описания правки |
Irina (обсуждение | вклад) Нет описания правки |
||
| Строка 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 | стоимость оптимального плана. Назовем алгоритм 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-серверная задача была предложена Манассом, Макгиохом и Слейтором [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]: | ||