Jump to content

Онлайн-алгоритм

(Перенаправлено из автономного алгоритма )

В информатике алгоритм онлайн- [1] это тот, который может обрабатывать свои входные данные по частям последовательным образом, т. е. в том порядке, в котором входные данные подаются в алгоритм , без того, чтобы весь ввод был доступен с самого начала.

Напротив, автономному алгоритму с самого начала предоставляются все данные о проблеме, и он должен вывести ответ, который решает поставленную проблему. В исследовании операций область, в которой разрабатываются онлайн-алгоритмы, называется онлайн-оптимизацией .

В качестве примера рассмотрим алгоритмы сортировки : сортировка выбором и сортировка вставкой : сортировка выбором неоднократно выбирает минимальный элемент из неотсортированного остатка и помещает его в начало, что требует доступа ко всему вводу; таким образом, это автономный алгоритм. С другой стороны, сортировка вставками рассматривает один входной элемент за итерацию и создает частичное решение без учета будущих элементов. Таким образом, сортировка вставками — это онлайн-алгоритм.

Обратите внимание, что конечный результат сортировки вставками является оптимальным, т. е. правильно отсортированным списком. Для многих задач онлайн-алгоритмы не могут сравниться по производительности с автономными алгоритмами. Если соотношение производительности онлайн-алгоритма и оптимального оффлайн-алгоритма ограничено, онлайн-алгоритм называется конкурентным . [1]

Не каждый оффлайн-алгоритм имеет эффективный онлайн- аналог.

В теории грамматик они связаны с прямолинейными грамматиками .

Определение

[ редактировать ]

Поскольку он не знает всей входной информации, онлайн-алгоритм вынужден принимать решения, которые впоследствии могут оказаться неоптимальными, и изучение онлайн-алгоритмов сосредоточено на качестве принятия решений, которое возможно в этих условиях. Конкурентный анализ формализует эту идею, сравнивая относительную производительность онлайн- и офлайн-алгоритма для одного и того же экземпляра проблемы. В частности, коэффициент конкурентоспособности алгоритма определяется как отношение его стоимости в наихудшем случае к оптимальной стоимости для всех возможных входных данных. Коэффициент конкуренции онлайн-задачи — это лучший коэффициент конкуренции, достигнутый онлайн-алгоритмом. Интуитивно понятно, что коэффициент конкурентоспособности алгоритма дает меру качества решений, полученных с помощью этого алгоритма, а коэффициент конкурентоспособности проблемы показывает важность знания будущего для этой проблемы.

Другие интерпретации

[ редактировать ]

Другие точки зрения на онлайн-входы в алгоритмы см.

Некоторые онлайн-алгоритмы :

Проблемы онлайн

[ редактировать ]

Проблема, иллюстрирующая концепции онлайн-алгоритмов, — это проблема канадского путешественника . Цель этой проблемы — минимизировать стоимость достижения цели во взвешенном графе, где некоторые ребра ненадежны и могут быть удалены из графа. Однако о том, что ребро было удалено ( не удалось узнает только ), путешественник тогда, когда он/она достигает одной из конечных точек ребра. Худшим случаем этой проблемы является просто то, что все ненадежные ребра выходят из строя, и проблема сводится к обычной задаче о кратчайшем пути . Альтернативный анализ проблемы можно провести с помощью конкурентного анализа. В этом методе анализа автономный алгоритм заранее знает, какие ребра потерпят неудачу, и цель состоит в том, чтобы минимизировать соотношение между производительностью онлайн- и оффлайн-алгоритмов. Эта задача является PSPACE-полной .

которых предлагает более одного онлайн-алгоритма Существует множество формальных задач, решение :

См. также

[ редактировать ]
  1. ^ Перейти обратно: а б Карп, Ричард М. (1992). «Онлайн-алгоритмы против офлайн-алгоритмов: сколько стоит знать будущее?» (PDF) . Конгресс ИФИП (1) . 12 : 416–429 . Проверено 17 августа 2015 г.
  2. ^ Дочоу, Роберт (2016). Онлайн-алгоритмы решения задачи выбора портфеля . Спрингер Габлер.
[ редактировать ]
Arc.Ask3.Ru: конец переведенного документа.
Arc.Ask3.Ru
Номер скриншота №: e0d247a68e5492cb7f387ca52d574673__1709314560
URL1:https://arc.ask3.ru/arc/aa/e0/73/e0d247a68e5492cb7f387ca52d574673.html
Заголовок, (Title) документа по адресу, URL1:
Online algorithm - Wikipedia
Данный printscreen веб страницы (снимок веб страницы, скриншот веб страницы), визуально-программная копия документа расположенного по адресу URL1 и сохраненная в файл, имеет: квалифицированную, усовершенствованную (подтверждены: метки времени, валидность сертификата), открепленную ЭЦП (приложена к данному файлу), что может быть использовано для подтверждения содержания и факта существования документа в этот момент времени. Права на данный скриншот принадлежат администрации Ask3.ru, использование в качестве доказательства только с письменного разрешения правообладателя скриншота. Администрация Ask3.ru не несет ответственности за информацию размещенную на данном скриншоте. Права на прочие зарегистрированные элементы любого права, изображенные на снимках принадлежат их владельцам. Качество перевода предоставляется как есть. Любые претензии, иски не могут быть предъявлены. Если вы не согласны с любым пунктом перечисленным выше, вы не можете использовать данный сайт и информация размещенную на нем (сайте/странице), немедленно покиньте данный сайт. В случае нарушения любого пункта перечисленного выше, штраф 55! (Пятьдесят пять факториал, Денежную единицу (имеющую самостоятельную стоимость) можете выбрать самостоятельно, выплаичвается товарами в течение 7 дней с момента нарушения.)