Аноним

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

Материал из WEGA

Алгоритм DC-дерева для k серверов на деревьях (посмотреть исходный код)

Версия от 15:10, 14 декабря 2011

215 байт добавлено ,  14 декабря 2011
нет описания правки
Нет описания правки
Нет описания правки
Строка 1: Строка 1:
Постановка задачи
=======================Постановка задачи=======================================================


В рамках ''k-серверной задачи'' мы хотим спланировать движение k серверов в метрическом пространстве M в ответ на последовательность <math>\rho </math> = <math>r_{1}</math>, <math>r_{2}</math>, ..., <math>r_{n}</math> запросов, где <math>r_{i}</math> <math>\in</math> M для каждого i. Вначале все серверы расположены в одной и той же точке <math>r_{0}</math>  M. После выдачи каждого запроса <math>r_{i}</math> один из k серверов должен переместиться в <math>r_{i}</math>. План определяет, какой сервер перемещается по каждому запросу. Стоимость плана равна сумме расстояний, пройденных серверами, и наша задача заключается в нахождении плана с минимальной стоимостью.
В рамках ''k-серверной задачи'' мы хотим спланировать движение <math>k</math> серверов в метрическом пространстве <math>M</math> в ответ на последовательность  
 
<math>\rho = r_{1}, r_{2},...,r_{n}</math>  
 
запросов, где <math>r_{i}\in M</math> для каждого <math>i</math>.  
Вначале все серверы расположены в одной и той же точке <math>r_{0}\in M</math>. После выдачи каждого запроса <math>r_{i}</math> один из <math>k</math> серверов должен переместиться в <math>r_{i}</math>. План определяет, какой сервер перемещается по каждому запросу. Стоимость плана равна сумме расстояний, пройденных серверами, и наша задача заключается в нахождении плана с минимальной стоимостью.


В онлайн-версии k-серверной задачи решение о том, какой сервер должен быть перемещен по каждому запросу <math>r_{i}</math>, должно приниматься до выдачи следующего запроса <math>r_{i+1}</math>. Иными словами, выбор этого сервера является функцией от запросов <math>r_{1}, r_{2}</math>, ..., <math>r_{i}</math>. Легко заметить, что в этом онлайн-сценарии гарантировать нахождение оптимального плана невозможно. Точность онлайн-алгоритмов нередко измеряется при помощи сравнительного анализа. Если A – онлайн-алгоритм для k-серверной задачи, обозначим за costA() стоимость плана, производимого алгоритмом A на последовательности запросов , а за opt() – стоимость оптимального плана. Назовем алгоритм A R-конкурентным, если costA() < R – opt() + B, где B – константа, которая может зависеть от M и <math>r_{0}</math>. Минимальное значение R называется коэффициентом конкурентоспособности A. Разумеется, чем меньше R, тем лучше.
В онлайн-версии k-серверной задачи решение о том, какой сервер должен быть перемещен по каждому запросу <math>r_{i}</math>, должно приниматься до выдачи следующего запроса <math>r_{i+1}</math>. Иными словами, выбор этого сервера является функцией от запросов <math>r_{1}, r_{2}</math>, ..., <math>r_{i}</math>. Легко заметить, что в этом онлайн-сценарии гарантировать нахождение оптимального плана невозможно. Точность онлайн-алгоритмов нередко измеряется при помощи сравнительного анализа. Если A – онлайн-алгоритм для k-серверной задачи, обозначим за costA() стоимость плана, производимого алгоритмом A на последовательности запросов , а за opt() – стоимость оптимального плана. Назовем алгоритм A R-конкурентным, если costA() < R – opt() + B, где B – константа, которая может зависеть от M и <math>r_{0}</math>. Минимальное значение R называется коэффициентом конкурентоспособности A. Разумеется, чем меньше R, тем лучше.
Строка 13: Строка 18:
Попытки доказать k-серверную гипотезу привели к открытию k-конкурентных алгоритмов для некоторых ограниченных классов метрических пространств, включая алгоритм DC-TREE для деревьев [4], представленный в следующем разделе. (См. другие примеры в [1, 2, 3]). Дерево представляет собой метрическое пространство, определяемое как связный ациклический граф, дуги которого рассматриваются как отрезки прямых произвольной положительной длины. Это метрическое пространство включает как вершины деревьев, так и точки на дугах, а расстояния измеряются вдоль (уникальных) кратчайших путей.
Попытки доказать k-серверную гипотезу привели к открытию k-конкурентных алгоритмов для некоторых ограниченных классов метрических пространств, включая алгоритм DC-TREE для деревьев [4], представленный в следующем разделе. (См. другие примеры в [1, 2, 3]). Дерево представляет собой метрическое пространство, определяемое как связный ациклический граф, дуги которого рассматриваются как отрезки прямых произвольной положительной длины. Это метрическое пространство включает как вершины деревьев, так и точки на дугах, а расстояния измеряются вдоль (уникальных) кратчайших путей.


Основные результаты
========================Основные результаты===========================================================
 
Пусть T – дерево, согласно вышеприведенному определению. Пусть даны текущая конфигурация сервера S = {<math>s_{1}</math>, ..., <math>s_{k}</math>}, где <math>s_{k}</math> обозначает местоположение сервера j, и точка запроса r; алгоритм выполняет перемещение нескольких серверов, один из которых окажется в результате в точке r. Для двух точек x, y  T, обозначим через [x; y] уникальный путь из x в у в дереве T. Сервер j называется активным, если не существует другого сервера в [<math>s_{j}</math>, r] – {<math>s_{j}</math>}, и j является сервером с минимальным индексом, расположенным в s<math>_{j}</math> (последнее условие необходимо только для разрыва связей).
Пусть T – дерево, согласно вышеприведенному определению. Пусть даны текущая конфигурация сервера S = {<math>s_{1}</math>, ..., <math>s_{k}</math>}, где <math>s_{k}</math> обозначает местоположение сервера j, и точка запроса r; алгоритм выполняет перемещение нескольких серверов, один из которых окажется в результате в точке r. Для двух точек x, y  T, обозначим через [x; y] уникальный путь из x в у в дереве T. Сервер j называется активным, если не существует другого сервера в [<math>s_{j}</math>, r] – {<math>s_{j}</math>}, и j является сервером с минимальным индексом, расположенным в s<math>_{j}</math> (последнее условие необходимо только для разрыва связей).


Строка 38: Строка 44:
► Алгоритм рабочей функции для k серверов
► Алгоритм рабочей функции для k серверов


Рекомендованная литература
===============Литература=============================================================
 
1. Bein, W., Chrobak, M., Larmore, L.L.: The 3-server problem in the plane. Theor. Comput. Sci. 287, 387-391 (2002)
1. Bein, W., Chrobak, M., Larmore, L.L.: The 3-server problem in the plane. Theor. Comput. Sci. 287, 387-391 (2002)
2. Borodin, A., El-Yaniv, R.: Online Computation and Competitive Analysis. Cambridge University Press, Cambridge (1998)
2. Borodin, A., El-Yaniv, R.: Online Computation and Competitive Analysis. Cambridge University Press, Cambridge (1998)
3. Chrobak, M., Karloff, H., Payne, T.H., Vishwanathan, S.: New re sults on server problems. SIAM J. Discret. Math. 4, 172-181 (1991)
3. Chrobak, M., Karloff, H., Payne, T.H., Vishwanathan, S.: New re sults on server problems. SIAM J. Discret. Math. 4, 172-181 (1991)
4. Chrobak, M., Larmore, L.L.: An optimal online algorithm for k servers on trees. SIAM J. Comput. 20,144-148 (1991)
4. Chrobak, M., Larmore, L.L.: An optimal online algorithm for k servers on trees. SIAM J. Comput. 20,144-148 (1991)
5. Koutsoupias, E., Papadimitriou, C.: On the k-server conjecture. In: Proc. 26th Symp. Theory of Computing (STOC), pp. 507-511. ACM(1994)
5. Koutsoupias, E., Papadimitriou, C.: On the k-server conjecture. In: Proc. 26th Symp. Theory of Computing (STOC), pp. 507-511. ACM(1994)
6. Koutsoupias, E., Papadimitriou, C.: On the k-server conjecture. J.ACM 42,971-983 (1995)
6. Koutsoupias, E., Papadimitriou, C.: On the k-server conjecture. J.ACM 42,971-983 (1995)
7. Manasse, M., McGeoch, L.A., Sleator, D.: Competitive algorithms  for online problems. In: Proc. 20th Symp. Theory of Computing  (STOC), pp. 322-333. ACM (1988)
7. Manasse, M., McGeoch, L.A., Sleator, D.: Competitive algorithms  for online problems. In: Proc. 20th Symp. Theory of Computing  (STOC), pp. 322-333. ACM (1988)
8. Manasse, M., McGeoch, L.A., Sleator, D.: Competitive algorithms for server problems. J. Algorithms 11, 208-230 (1990)
8. Manasse, M., McGeoch, L.A., Sleator, D.: Competitive algorithms for server problems. J. Algorithms 11, 208-230 (1990)
Источник — http://pco.iis.nsk.su/wega/index.php/Служебная:Сравнение_версий/10091