4511
правок
Системы метрических задач: различия между версиями
Перейти к навигации
Перейти к поиску
м
→Нотация
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) м (→Нотация) |
||
| Строка 7: | Строка 7: | ||
'''Определение 1 (система метрических задач)'''. Зафиксируем метрическое пространство <math>(X, d_X) \;</math>. Пусть <math>\Gamma = \{ (r_x)_{x \in X}: \forall x \in X, r(x) \in [0, \infty] \}</math> – множество всех возможных задач. Обозначим за <math>T \subset \Gamma \;</math> подмножество задач, называемых ''допустимыми''. | '''Определение 1 (система метрических задач)'''. Зафиксируем метрическое пространство <math>(X, d_X) \;</math>. Пусть <math>\Gamma = \{ (r_x)_{x \in X}: \forall x \in X, r(x) \in [0, \infty] \}</math> – множество всех возможных задач. Обозначим за <math>T \subset \Gamma \;</math> подмножество задач, называемых ''допустимыми''. | ||
<math>MTS((X, d_X), T, a_0 \in X) \;</math>: | <math>MTS((X, d_X), T, a_0 \in X) \;</math>: | ||
| Строка 20: | Строка 19: | ||
Если X конечно, а последовательность задач <math>\tau \in T^* \;</math> задана заранее, динамический алгоритм может вычислить оптимальное решение, используя память размером <math>O(|X|) \;</math> и время <math>О(| \tau | \cdot |X|) \;</math>. | Если 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)'''. Детерминированный алгоритм решения задачи <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 | '''Определение 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 a \;</math>. Рандомизированный онлайн-алгоритм представляет собой вероятностное распределение над детерминированными онлайн-алгоритмами. | ||