4817
правок
Алгоритм рабочей функции для k серверов: различия между версиями
Перейти к навигации
Перейти к поиску
Алгоритм рабочей функции для k серверов (посмотреть исходный код)
Версия от 07:38, 20 декабря 2018
, 20 декабря 2018→Основные результаты
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 20: | Строка 20: | ||
Формально, для каждой последовательности запросов | Формально, для каждой последовательности запросов <math>\rho</math> и k-серверной конфигурации X обозначим за <math>\omega_{\rho}(X)</math> минимальную стоимость обслуживания <math>\rho</math> с учетом ограничения, согласно которому по окончании работы алгоритма конфигурацией должна быть X. (Предположим, что начальная конфигурация <math>X_0</math> фиксирована). Функция <math>\omega_{\rho}(\cdot)</math> называется ''рабочей функцией'' для последовательности запросов <math>\rho</math>. | ||
'''Алгоритм WFA''' | '''Алгоритм WFA''' | ||
Обозначим за <math>\sigma</math> последовательность прошлых запросов и предположим, что текущая конфигурация серверов имеет вид <math>S = \{s_1, s_2, ..., s_k \}</math>, где <math>s_j</math> – местоположение j-го сервера. Пусть r – новый запрос. Выберем <math>s_j \in S</math>, для которого величина <math>\omega_{\sigma \rho}(S - \{ s_j \} \cup \{ r \}) + d(s_j, r)</math> минимальна, и переместим сервер j к r. | |||
Теорема 1 ([10,11]). Алгоритм WFA является (2k- | |||
'''Теорема 1 ([10,11]). Алгоритм WFA является (2k - 1)-конкурентным.''' | |||
== Применение == | == Применение == | ||