4817
правок
Алгоритм рабочей функции для k серверов: различия между версиями
Перейти к навигации
Перейти к поиску
м
Алгоритм рабочей функции для k серверов (посмотреть исходный код)
Версия от 10:46, 20 декабря 2018
, 20 декабря 2018→Постановка задачи
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 1: | Строка 1: | ||
== Постановка задачи == | == Постановка задачи == | ||
В рамках ''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 серверов на последовательности запросов. | В рамках ''k-серверной задачи'' мы хотим спланировать движение k серверов в метрическом пространстве <math>\mathbb{M}</math> в ответ на последовательность <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 серверов на последовательности запросов. | ||