4551
правка
Обобщенная двухсерверная задача: различия между версиями
Материал из WEGA
Обобщенная двухсерверная задача (посмотреть исходный код)
Версия от 11:55, 18 декабря 2017
, 18 декабря 2017→Постановка задачи
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 14: | Строка 14: | ||
Эффективность алгоритмов онлайн-оптимизации нередко измеряется при помощи сравнительного (конкурентного) анализа. Мы утверждаем, что алгоритм является | Эффективность алгоритмов онлайн-оптимизации нередко измеряется при помощи ''сравнительного (конкурентного) анализа''. Мы утверждаем, что алгоритм является <math> \; \alpha</math>-конкурентным (<math>\alpha \ge 1 \;</math>) для некоторой задачи минимизации, если для любого возможного экземпляра задачи стоимость решения алгоритма не более чем в <math>\alpha \;</math> раз превышает стоимость оптимального решения для этого экземпляра. | ||
[[Файл:GTSP.png]] | |||
В этом примере оба сервера перемещаются на плоскости и начинают движение с конфигурации ( | |||
Рис. 1. В этом примере оба сервера перемещаются на плоскости и начинают движение с конфигурации (<math>x_0, y_0 \;</math>). <math>\mathbb{X}</math>-сервер перемещается при выполнении запросов 1 и 3, <math>\mathbb{Y}</math>-сервер обслуживает запросы 2 и 4. Стоимость решения представляет собой сумму длин путей | |||
