Обобщенная двухсерверная задача: различия между версиями
Перейти к навигации
Перейти к поиску
Irina (обсуждение | вклад) мНет описания правки |
Irina (обсуждение | вклад) мНет описания правки |
||
| Строка 4: | Строка 4: | ||
== Постановка задачи == | == Постановка задачи == | ||
В обобщенной двухсерверной задаче имеются два сервера, один из которых перемещается в метрическом пространстве <math>\mathbb{X} \;</math>, а другой – в метрическом пространстве <math>\mathbb{Y} \;</math>. Они обслуживают запросы <math>r \in \mathbb{X} \times \mathbb{Y} \;</math>, которые поступают один за одним. Запрос r = (x, y) обслуживается посредством перемещения <math>\mathbb{X}</math>-сервера в точку x либо <math>\mathbb{Y}</math>-сервера в точку y. Решение, какой из двух серверов переместить при следующем запросе, не подлежит отмене и принимается в отсутствие каких-либо знаний о будущих запросах. Задача заключается в минимизации расстояния, пройденного обоими серверами. | В обобщенной двухсерверной задаче имеются два сервера, один из которых перемещается в метрическом пространстве <math>\mathbb{X} \;</math>, а другой – в метрическом пространстве <math>\mathbb{Y} \;</math>. Они обслуживают запросы <math>r \in \mathbb{X} \times \mathbb{Y} \;</math>, которые поступают один за одним. Запрос r = (x, y) обслуживается посредством перемещения <math>\mathbb{X}</math>-сервера в точку x либо <math>\mathbb{Y}</math>-сервера в точку y. Решение, какой из двух серверов переместить при следующем запросе, не подлежит отмене и принимается в отсутствие каких-либо знаний о будущих запросах. Задача заключается в минимизации расстояния, пройденного обоими серверами. | ||
[[Файл:GTSP.png]] | |||
Рис. 1. В этом примере оба сервера перемещаются по плоскости и начинают движение с конфигурации (<math>x_0, y_0 \;</math>). <math>\mathbb{X}</math>-сервер перемещается при выполнении запросов 1 и 3, <math>\mathbb{Y}</math>-сервер обслуживает запросы 2 и 4. Стоимость решения представляет собой сумму длин путей | |||
| Строка 14: | Строка 19: | ||
Эффективность алгоритмов онлайн-оптимизации нередко измеряется при помощи ''сравнительного (конкурентного) анализа''. Мы утверждаем, что алгоритм является <math> \; \alpha</math>-конкурентным (<math>\alpha \ge 1 \;</math>) для некоторой задачи минимизации, если для любого возможного экземпляра задачи стоимость решения алгоритма не более чем в <math>\alpha \;</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>, если он посещает все запросы по порядку. Следовательно, допустимым путем является такой путь, который обслуживает всю последовательность и начинается с исходной конфигурации. | ||