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

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

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

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

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

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

Определение

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

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

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

Примеры

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

Проблемы в сети

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

Есть много формальных задач, которые предполагают более одного онлайн алгоритм как решение:

Смотрите также

Рекомендации

  1. ^ а б Карп, Ричард М. (1992). «Онлайн-алгоритмы против автономных алгоритмов: сколько стоит знать будущее?» (PDF). Конгресс ИФИП (1). 12: 416–429. Получено 17 августа 2015.
  2. ^ Дочоу, Роберт (2016). Онлайн-алгоритмы для задачи выбора портфеля. Springer Gabler.

внешняя ссылка