Модель противника - Adversary model
В Информатика, онлайн алгоритм измеряет свой конкурентоспособность против разных модели противника. Для детерминированных алгоритмов противник такой же, как и противник с адаптивным оффлайном. Для рандомизированных онлайн-алгоритмов конкурентоспособность может зависеть от модель противника использовал.
Общие противники
Три распространенных противника - это не обращающий внимания противник, адаптивный онлайн-противник и адаптивный офлайн-противник.
В невнимательный противник иногда называют слабым противником. Этот противник знает код алгоритма, но не знает рандомизированных результатов алгоритма.
В адаптивный онлайн-противник иногда называют средним противником. Этот противник должен принять собственное решение, прежде чем ему будет разрешено узнать решение алгоритма.
В адаптивный офлайн-противник иногда называют сильным противником. Этот противник знает все, даже генератор случайных чисел. Этот противник настолько силен, что рандомизация ему не помогает.
Важные результаты
От С. Бен-Давида, А. Бородин, Р. Карп, Г. Тардос, А. Вигдерсон у нас есть:
- Если существует рандомизированный алгоритм, который является α-конкурентным против любого адаптивного автономного противника, то существует также α-конкурентный детерминированный алгоритм.
- Если G - это рандомизированный c-конкурентный алгоритм против любого адаптивного онлайн-противника, и существует рандомизированный d-конкурентный алгоритм против любого не обращающего внимания противника, то G - рандомизированный (c * d) -конкурентный алгоритм против любого адаптивного офлайн-противника.
Смотрите также
Рекомендации
- Бородин, А.; Эль-Янив Р. (1998). Онлайн-вычисления и конкурентный анализ. Издательство Кембриджского университета. ISBN 978-0-521-56392-5.
- С. Бен-Давид; А. Бородин; Р. Карп; Г. Тардос; А. Вигдерсон. (1994). «О силе рандомизации в онлайн-алгоритмах» (PDF). Алгоритмика. 11: 2–14. Дои:10.1007 / BF01294260.