Обобщенная двухсерверная задача: различия между версиями

Перейти к навигации Перейти к поиску
м
Строка 14: Строка 14:




Эффективность алгоритмов онлайн-оптимизации нередко измеряется при помощи сравнительного (конкурентного) анализа. Мы утверждаем, что алгоритм является a-конкурентным (a > 1) для некоторой задачи минимизации, если для любого возможного экземпляра задачи стоимость решения алгоритма не более чем в a раз превышает стоимость оптимального решения для этого экземпляра.
Эффективность алгоритмов онлайн-оптимизации нередко измеряется при помощи ''сравнительного (конкурентного) анализа''. Мы утверждаем, что алгоритм является <math> \; \alpha</math>-конкурентным (<math>\alpha \ge 1 \;</math>) для некоторой задачи минимизации, если для любого возможного экземпляра задачи стоимость решения алгоритма не более чем в <math>\alpha \;</math> раз превышает стоимость оптимального решения для этого экземпляра.




Обобщенная двухсерверная задача, рис. 1
[[Файл:GTSP.png]]
В этом примере оба сервера перемещаются на плоскости и начинают движение с конфигурации (x0, y0). X-сервер перемещается при выполнении запросов 1 и 3, Y-сервер обслуживает запросы 2 и 4. Стоимость решения представляет собой сумму длин путей
 
Рис. 1. В этом примере оба сервера перемещаются на плоскости и начинают движение с конфигурации (<math>x_0, y_0 \;</math>). <math>\mathbb{X}</math>-сервер перемещается при выполнении запросов 1 и 3, <math>\mathbb{Y}</math>-сервер обслуживает запросы 2 и 4. Стоимость решения представляет собой сумму длин путей




4551

правка

Навигация