4446
правок
Алгоритм DC-дерева для k серверов на деревьях: различия между версиями
Материал из WEGA
Алгоритм DC-дерева для k серверов на деревьях (посмотреть исходный код)
Версия от 21:26, 12 декабря 2011
, 12 декабря 2011нет описания правки
Irina (обсуждение | вклад) Нет описания правки |
Irina (обсуждение | вклад) Нет описания правки |
||
| Строка 1: | Строка 1: | ||
Постановка задачи | Постановка задачи | ||
В рамках ''k-серверной задачи'' мы хотим спланировать движение k серверов в метрическом пространстве M в ответ на последовательность <math>\rho </math> = | В рамках ''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-серверной задачи решение о том, какой сервер должен быть перемещен по каждому запросу | В онлайн-версии 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, тем лучше. | ||
| Строка 14: | Строка 14: | ||
Основные результаты | Основные результаты | ||
Пусть T – дерево, согласно вышеприведенному определению. Пусть даны текущая конфигурация сервера S = { | Пусть 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> (последнее условие необходимо только для разрыва связей). | ||
Алгоритм DC-TREE | Алгоритм DC-TREE | ||
