4501
правка
Алгоритм DC-дерева для k серверов на деревьях: различия между версиями
Перейти к навигации
Перейти к поиску
Алгоритм DC-дерева для k серверов на деревьях (посмотреть исходный код)
Версия от 23:46, 14 декабря 2011
, 14 декабря 2011нет описания правки
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-серверной задачи, обозначим за | В онлайн-версии 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}</math>(<math>\rho</math> | ||
) стоимость плана, производимого алгоритмом A на последовательности запросов , а за opt() – стоимость оптимального плана. Назовем алгоритм A R-конкурентным, если costA() < R – opt() + B, где B – константа, которая может зависеть от M и <math>r_{0}</math>. Минимальное значение R называется коэффициентом конкурентоспособности A. Разумеется, чем меньше R, тем лучше. | |||