1294
правки
Обобщенная двухсерверная задача: различия между версиями
Материал из WEGA
Обобщенная двухсерверная задача (посмотреть исходный код)
Версия от 11:07, 7 декабря 2024
, 7 декабрь→Литература
Irina (обсуждение | вклад) |
KVN (обсуждение | вклад) |
||
| (не показаны 4 промежуточные версии 1 участника) | |||
| Строка 6: | Строка 6: | ||
[[Файл:GTSP.png]] | |||
Рис. 1. В этом примере оба сервера перемещаются по плоскости и начинают движение с конфигурации (<math>x_0, y_0 \;</math>). <math>\mathbb{X}</math>-сервер перемещается при выполнении запросов 1 и 3, <math>\mathbb{Y}</math>-сервер обслуживает запросы 2 и 4. Стоимость решения представляет собой сумму длин путей | |||
'''Задачи онлайн-маршрутизации''' | |||
Обобщенная двухсерверная задача относится к классу задач маршрутизации под названием ''метрических систем сервисов'' [5, 10]. Подобную систему определяют метрическое пространство <math>\mathbb{M} \;</math> всех возможных конфигураций системы, начальная конфигурация <math>C_0 \;</math> и множество <math>\mathcal{R} \;</math> возможных запросов, в котором каждый запрос <math>r \in \mathcal{R} \;</math> является подмножеством <math>\mathbb{M} \;</math>. Пусть дана последовательность запросов <math>r_1, r_2, ..., r_n \;</math>. Допустимым решением является последовательность конфигураций <math>C_1, C_2, ..., C_n \;</math>, такая, что <math>C_i \in r_i \;</math> для всех <math>i \in \{ 1, ..., n \} \;</math>. | |||
При моделировании обобщенной двухсерверной задачи метрической системой сервисов мы получаем <math>\mathbb{M} = \mathbb{X} \times \mathbb{Y}</math> и <math>\mathcal{R} = \{ \{ x \times \mathbb{Y} \} \cup \{ \mathbb{X} \times y \} | x \in \mathbb{X}, y \in \mathbb{Y} \}</math>. В классической двухсерверной задаче оба сервера перемещаются в одном и том же пространстве и получают одни и те же запросы, т.е. <math>\mathbb{M} = \mathbb{X} \times \mathbb{X}</math> и <math>\mathcal{R} = \{ \{ x \times \mathbb{X} \} \cup \{ \mathbb{X} \times x \} | x \in \mathbb{X} \}</math>. | |||
Эффективность алгоритмов онлайн-оптимизации нередко измеряется при помощи ''сравнительного (конкурентного) анализа''. Мы утверждаем, что алгоритм является <math> \; \alpha</math>-''конкурентным'' (<math>\alpha \ge 1 \;</math>) для некоторой задачи минимизации, если для любого возможного экземпляра задачи стоимость решения алгоритма не более чем в <math>\alpha \;</math> раз превышает стоимость оптимального решения для этого экземпляра. | |||
| Строка 28: | Строка 28: | ||
Для фиксированной метрической системы сервисов S с метрическим пространством <math>\mathbb{M} \;</math> обозначим за <math>A(C, \sigma) \;</math> стоимость работы алгоритма A на входной последовательности <math>\sigma \;</math>, начинающего работу с конфигурации C. Пусть <math>OPT(C, \sigma) \;</math> – стоимость соответствующего оптимального решения. Мы говорим, что путь T в <math>\mathbb{M} \;</math> ''обслуживает'' последовательность <math>\sigma \;</math>, если он посещает все запросы по порядку. Следовательно, допустимым путем является такой путь, который обслуживает | Для фиксированной метрической системы сервисов S с метрическим пространством <math>\mathbb{M} \;</math> обозначим за <math>A(C, \sigma) \;</math> стоимость работы алгоритма A на входной последовательности <math>\sigma \;</math>, начинающего работу с конфигурации C. Пусть <math>OPT(C, \sigma) \;</math> – стоимость соответствующего оптимального решения. Мы говорим, что путь T в <math>\mathbb{M} \;</math> ''обслуживает'' последовательность <math>\sigma \;</math>, если он посещает все запросы по порядку. Следовательно, допустимым путем является такой путь, который обслуживает всю последовательность и начинается с исходной конфигурации. | ||
| Строка 61: | Строка 61: | ||
* [[Алгоритм DC-дерева для k серверов на деревьях]] | * [[Алгоритм DC-дерева для k серверов на деревьях]] | ||
* [[Системы метрических задач]] | * [[Системы метрических задач]] | ||
* [[ | * [[Онлайн-алгоритм подкачки и кэширования]] | ||
* [[Алгоритм рабочей функции для k серверов]] | * [[Алгоритм рабочей функции для k серверов]] | ||
| Строка 88: | Строка 88: | ||
12. Sleator, D.D., Tarjan, R.E.: Self-adjusting binary search trees. J.ACM 32,652-686 (1985) | 12. Sleator, D.D., Tarjan, R.E.: Self-adjusting binary search trees. J.ACM 32,652-686 (1985) | ||
[[Категория: Совместное определение связанных терминов]] | |||
[[Категория: Совместное определение связанных терминов]] | |||
