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