4446
правок
Системы метрических задач: различия между версиями
Перейти к навигации
Перейти к поиску
→Нотация
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 20: | Строка 20: | ||
Если X конечно, а последовательность задач | Если X конечно, а последовательность задач <math>\tau \in T^* \;</math> задана заранее, динамический алгоритм может вычислить оптимальное решение, используя память размером <math>O(|X|) \;</math> и время <math>О(| \tau | \cdot |X|) \;</math>. Задача MTS интереснее всего в онлайновом режиме, в котором система должна реагировать на задачу <math>\tau_i \;</math> переходом в состояние <math>a_i \in X \;</math>, не зная будущих задач из <math>\tau \;</math>. Более формально: | ||
Определение 2 (онлайн-алгоритмы для MTS). Детерминированный алгоритм решения задачи MTS((X, | '''Определение 2 (онлайн-алгоритмы для MTS)'''. Детерминированный алгоритм решения задачи <math>MTS((X, d_X), T, a_0) \;</math> представляет собой отображение <math>S: T^* \to X^* \;</math>, такое, что для любого <math>\tau \in T \;</math> имеет место <math>|S(\tau)| = |\tau| \;</math> . Детерминированный алгоритм <math>S: T^* \to X^* \;</math> называется ''онлайновым'', если для любых <math>\tau, \sigma \in T^* \;</math> существует <math>a \in X^*, |a| = | \sigma | \;</math>, такое, что <math>S(\tau \circ \sigma) = S(\tau) \circ \sigma \;</math>. Рандомизированный онлайн-алгоритм представляет собой вероятностное распределение над детерминированными онлайн-алгоритмами. | ||
Онлайн-алгоритмы для MTS оцениваются с помощью (асимптотического) конкурентного анализа, который, грубо говоря, вычисляет наихудшее отношение стоимости алгоритма к оптимальной стоимости по всем возможным последовательностям задач. | Онлайн-алгоритмы для MTS оцениваются с помощью ''(асимптотического) конкурентного анализа'', который, грубо говоря, вычисляет наихудшее отношение стоимости алгоритма к оптимальной стоимости по всем возможным последовательностям задач. | ||
Определение 3. Рандомизированный онлайн-алгоритм R для задачи MTS((X, | '''Определение 3'''. Рандомизированный онлайн-алгоритм R для задачи <math>MTS((X, d_X), T, a_0) \;</math> называется c-конкурентным (по сравнению с рассеянными соперниками), если существует <math>b = b(X) \in \mathbb{R} \;</math>, такое, что для любой последовательности задач <math>\tau \in T^* \;</math> и любой последовательности точек <math>a \in X^*, |a| = | \tau | \;</math> | ||
имеет место соотношение <math>\mathbb{E} [cost(\tau, R(\tau))] \le c \cdot cost(\tau, a) + b \;</math>, где математическое ожидание берется над распределением R. | |||
имеет место соотношение E[cost( | |||
Коэффициентом конкурентоспособности онлайн-алгоритма R является инфимум над c > | Коэффициентом конкурентоспособности онлайн-алгоритма R является инфимум над <math>c \ge 1 \;</math>, для которого R является c-конкурентным. Детерминированным [соответственно, рандомизированным] коэффициентом конкурентоспособности задачи <math>MTS((X, d_X), T, a_0) \;</math> является инфимум над коэффициентами конкурентоспособности всех детерминированных [соответственно, рандомизированных] онлайн-алгоритмов для этой задачи. Отметим, что в силу наличия квантора существования при ''b'' асимптотический коэффициент конкурентоспособности (как рандомизированный, так и детерминированный) задачи <math>MTS((X, d_X), T, a_0) \;</math> независим от <math>a_0 \;</math> и, следовательно, может быть исключен из нотации. | ||
== Основные результаты == | == Основные результаты == | ||