Алгоритм DC-дерева для k серверов на деревьях: различия между версиями
Перейти к навигации
Перейти к поиску
Irina (обсуждение | вклад) Нет описания правки |
Irina (обсуждение | вклад) Нет описания правки |
||
| Строка 8: | Строка 8: | ||
Вначале все серверы расположены в одной и той же точке <math>r_{0}\in M</math>. После выдачи каждого запроса <math>r_{i}</math> один из <math>k</math> серверов должен переместиться в <math>r_{i}</math>. ''План'' определяет, какой сервер перемещается по каждому запросу. ''Стоимость'' плана равна сумме расстояний, пройденных серверами, и наша задача заключается в нахождении плана с минимальной стоимостью. | Вначале все серверы расположены в одной и той же точке <math>r_{0}\in M</math>. После выдачи каждого запроса <math>r_{i}</math> один из <math>k</math> серверов должен переместиться в <math>r_{i}</math>. ''План'' определяет, какой сервер перемещается по каждому запросу. ''Стоимость'' плана равна сумме расстояний, пройденных серверами, и наша задача заключается в нахождении плана с минимальной стоимостью. | ||
В ''онлайн-версии'' k-серверной задачи решение о том, какой сервер должен быть перемещен по каждому запросу <math>r_{i}</math>, должно приниматься до выдачи следующего запроса <math>r_{i+1}</math>. Иными словами, выбор этого сервера является функцией от запросов <math>r_{1}, r_{2}</math>, ..., <math>r_{i}</math>. Легко заметить, что в этом онлайн-сценарии гарантировать нахождение оптимального плана невозможно. Точность онлайн-алгоритмов нередко измеряется при помощи сравнительного анализа. Если A – онлайн-алгоритм для k-серверной задачи, обозначим за <math>cost_{A}(\varrho</math> | В ''онлайн-версии'' k-серверной задачи решение о том, какой сервер должен быть перемещен по каждому запросу <math>r_{i}</math>, должно приниматься до выдачи следующего запроса <math>r_{i+1}</math>. Иными словами, выбор этого сервера является функцией от запросов <math>r_{1}, r_{2}</math>, ..., <math>r_{i}</math>. Легко заметить, что в этом онлайн-сценарии гарантировать нахождение оптимального плана невозможно. Точность онлайн-алгоритмов нередко измеряется при помощи сравнительного анализа. Если A – онлайн-алгоритм для k-серверной задачи, обозначим за <math>cost_{A}(\varrho)</math> стоимость плана, производимого алгоритмом A на последовательности запросов <math>\varrho</math> | ||
, а за <math>opt(\varrho)</math> - | |||
стоимость оптимального плана. Назовем алгоритм A R-конкурентным, если <math>cost_{A}(\varrho) < R - opt(\varrho) + B</math>, где B – константа, которая может зависеть от M и <math>r_{0}</math>. Минимальное значение R называется коэффициентом конкурентоспособности A. Разумеется, чем меньше R, тем лучше. | |||