4817
правок
Алгоритм рабочей функции для k серверов: различия между версиями
Материал из WEGA
Алгоритм рабочей функции для k серверов (посмотреть исходный код)
Версия от 03:07, 20 декабря 2018
, 20 декабря 2018→Постановка задачи
Irina (обсуждение | вклад) Нет описания правки |
Irina (обсуждение | вклад) |
||
| Строка 5: | Строка 5: | ||
[[Файл:WFA.png]] | [[Файл:WFA.png]] | ||
Рис. 1. План для 2 серверов на последовательности запросов | Рис. 1. План для 2 серверов на последовательности запросов <math>\rho = r_1, r_2, ..., r_7</math>. Изначальная конфигурация равна <math>X_0 = \{ x_1, x_2 \}</math>. Сервер 1 обслуживает запросы <math>r_1, r_2, r_5, r_6</math>, сервер 2 – запросы <math>r_3, r_4, r_7</math>. Стоимость этого плана составляет <math>d(x_1, r_1) + d(r_1, r_2) + d(r_2, r_5) + d(r_5, r_6) + d(x_2, r_3) + d(r_3, r_4) + d(r_4, r_7)</math>, где d(x, y) обозначает расстояние между точками x и y | ||
В оффлайновом случае, когда даны M, | В оффлайновом случае, когда даны <math>\mathbb{M}, X_0</math> и полная последовательность запросов <math>\rho</math>, оптимальный план можно вычислить за полиномиальное время [6]. | ||
В онлайн-версии k-серверной задачи решение о том, к какому серверу следует переместиться для каждого запроса | В ''онлайн-версии'' k-серверной задачи решение о том, к какому серверу следует переместиться для каждого запроса <math>r_i</math>, должно приниматься до выдачи следующего запроса <math>r_{i + 1}</math>. Легко заметить, что в этом онлайн-сценарии гарантировать нахождение оптимального плана невозможно. Точность онлайн-алгоритмов нередко измеряется при помощи сравнительного анализа. Обозначим за <math>cost_{\mathcal{A}}(\rho)</math> стоимость плана, производимого онлайн-алгоритмом A для k-серверной задачи на последовательности запросов *, а за opt(*) – стоимость оптимального плана на этой последовательности. Назовем алгоритм A R-конкурентным, если costA(*) < R – opt(*) + B, где B – константа, которая может зависеть от M и X0. Минимальное значение R называется коэффициентом конкурентоспособности A. Разумеется, чем меньше R, тем лучше. | ||
