4446
правок
Алгоритм DC-дерева для k серверов на деревьях: различия между версиями
Материал из WEGA
Алгоритм DC-дерева для k серверов на деревьях (посмотреть исходный код)
Версия от 21:09, 12 декабря 2011
, 12 декабря 2011нет описания правки
Irina (обсуждение | вклад) (Новая страница: «Постановка задачи В рамках ''k-серверной задачи'' мы хотим спланировать движение k серверов…») |
Irina (обсуждение | вклад) Нет описания правки |
||
| Строка 1: | Строка 1: | ||
Постановка задачи | Постановка задачи | ||
В рамках ''k-серверной задачи'' мы хотим спланировать движение k серверов в метрическом пространстве M в ответ на последовательность <math>\ | В рамках ''k-серверной задачи'' мы хотим спланировать движение k серверов в метрическом пространстве M в ответ на последовательность <math>\rho </math> = r<math>{1}_{}</math>, r2, ..., rn запросов, где ri <math>\in </math> M для каждого i. Вначале все серверы расположены в одной и той же точке r0 M. После выдачи каждого запроса ri один из k серверов должен переместиться в ri. План определяет, какой сервер перемещается по каждому запросу. Стоимость плана равна сумме расстояний, пройденных серверами, и наша задача заключается в нахождении плана с минимальной стоимостью. | ||
В онлайн-версии k-серверной задачи решение о том, какой сервер должен быть перемещен по каждому запросу ri, должно приниматься до выдачи следующего запроса ri+1. Иными словами, выбор этого сервера является функцией от запросов r1, r2, …, ri. Легко заметить, что в этом онлайн-сценарии гарантировать нахождение оптимального плана невозможно. Точность онлайн-алгоритмов нередко измеряется при помощи сравнительного анализа. Если A – онлайн-алгоритм для k-серверной задачи, обозначим за costA() стоимость плана, производимого алгоритмом A на последовательности запросов , а за opt() – стоимость оптимального плана. Назовем алгоритм A R-конкурентным, если costA() < R – opt() + B, где B – константа, которая может зависеть от M и r0. Минимальное значение R называется коэффициентом конкурентоспособности A. Разумеется, чем меньше R, тем лучше. | В онлайн-версии k-серверной задачи решение о том, какой сервер должен быть перемещен по каждому запросу ri, должно приниматься до выдачи следующего запроса ri+1. Иными словами, выбор этого сервера является функцией от запросов r1, r2, …, ri. Легко заметить, что в этом онлайн-сценарии гарантировать нахождение оптимального плана невозможно. Точность онлайн-алгоритмов нередко измеряется при помощи сравнительного анализа. Если A – онлайн-алгоритм для k-серверной задачи, обозначим за costA() стоимость плана, производимого алгоритмом A на последовательности запросов , а за opt() – стоимость оптимального плана. Назовем алгоритм A R-конкурентным, если costA() < R – opt() + B, где B – константа, которая может зависеть от M и r0. Минимальное значение R называется коэффициентом конкурентоспособности A. Разумеется, чем меньше R, тем лучше. | ||
