1023
правки
Алгоритм DC-дерева для k серверов на деревьях: различия между версиями
Материал из WEGA
Алгоритм DC-дерева для k серверов на деревьях (посмотреть исходный код)
Версия от 15:15, 14 декабря 2011
, 14 декабря 2011→Постановка задачи================================
KVN (обсуждение | вклад) Нет описания правки |
KVN (обсуждение | вклад) |
||
| Строка 1: | Строка 1: | ||
=======================Постановка задачи======================================================= | =======================Постановка задачи======================================================= | ||
В рамках ''k-серверной задачи'' мы хотим спланировать движение <math>k</math> серверов в метрическом пространстве <math>M</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>. План определяет, какой сервер перемещается по каждому запросу. Стоимость плана равна сумме расстояний, пройденных серверами, и наша задача заключается в нахождении плана с минимальной стоимостью. | Вначале все серверы расположены в одной и той же точке <math>r_{0}\in M</math>. После выдачи каждого запроса <math>r_{i}</math> один из <math>k</math> серверов должен переместиться в <math>r_{i}</math>. План определяет, какой сервер перемещается по каждому запросу. Стоимость плана равна сумме расстояний, пройденных серверами, и наша задача заключается в нахождении плана с минимальной стоимостью. | ||
