4817
правок
Алгоритм рабочей функции для k серверов: различия между версиями
Перейти к навигации
Перейти к поиску
Алгоритм рабочей функции для k серверов (посмотреть исходный код)
Версия от 03:03, 20 декабря 2018
, 20 декабря 2018нет описания правки
Irina (обсуждение | вклад) м (→См. также) |
Irina (обсуждение | вклад) Нет описания правки |
||
| Строка 1: | Строка 1: | ||
== Постановка задачи == | == Постановка задачи == | ||
В рамках k-серверной задачи мы хотим спланировать движение k серверов в метрическом пространстве M в ответ на последовательность | В рамках ''k-серверной задачи'' мы хотим спланировать движение k серверов в метрическом пространстве M в ответ на последовательность <math>\rho = r_1, r_2, ..., r_n</math> ''запросов'', где <math>r_i \in M</math> для каждого i. Вначале все серверы занимают одну и ту же конфигурацию <math>X_0 \subseteq \mathbb{M}</math>. После выдачи каждого запроса <math>r_i</math> один из k серверов должен переместиться в <math>r_i</math>. План S определяет, какой сервер перемещается по каждому запросу. Задача заключается в создании ''плана'' минимальной стоимости, где стоимость плана равна сумме расстояний, пройденных серверами. Ниже приводится пример плана для 2 серверов на последовательности запросов. | ||
[[Файл:WFA.png]] | |||
Рис. 1. План для 2 серверов на последовательности запросов % = r1 ;r2... r7. Изначальная конфигурация равна X0 = fx1;x2g. Сервер 1 обслуживает запросы r1, r2, r5, r6, сервер 2 – запросы r3, r4, r7. Стоимость этого плана составляет d(x1, r1) + d(r1, r2) + d(r2, r5) + d(r5, r6) + d(x2, r3) + d(r3, r4) + d(r4, r7), где d(x, y) обозначает расстояние между точками x и y | Рис. 1. План для 2 серверов на последовательности запросов % = r1 ;r2... r7. Изначальная конфигурация равна X0 = fx1;x2g. Сервер 1 обслуживает запросы r1, r2, r5, r6, сервер 2 – запросы r3, r4, r7. Стоимость этого плана составляет d(x1, r1) + d(r1, r2) + d(r2, r5) + d(r5, r6) + d(x2, r3) + d(r3, r4) + d(r4, r7), где d(x, y) обозначает расстояние между точками x и y | ||