В информатике онлайн-алгоритм [1] - это алгоритм, который может обрабатывать входные данные по частям в последовательном режиме, то есть в том порядке, в котором входные данные поступают в алгоритм , без того, чтобы все входные данные были доступны с самого начала. .
Напротив, автономный алгоритм получает все данные о проблеме с самого начала и требуется для вывода ответа, который решает текущую проблему. В исследовании операций область, в которой разрабатываются онлайн-алгоритмы, называется онлайн-оптимизацией .
В качестве примера рассмотрим алгоритмы сортировки по выбору, сортировке и вставке : сортировка по выбору повторно выбирает минимальный элемент из несортированного остатка и помещает его на передний план, что требует доступа ко всему входу; таким образом, это автономный алгоритм. С другой стороны, сортировка вставкой учитывает один входной элемент на итерацию и дает частичное решение без учета будущих элементов. Таким образом, сортировка вставкой - это онлайн-алгоритм.
Обратите внимание, что окончательный результат сортировки вставкой является оптимальным, т. Е. Правильно отсортированный список. Для многих проблем онлайн-алгоритмы не могут сравниться по производительности с автономными алгоритмами. Если соотношение между производительностью онлайн-алгоритма и оптимального автономного алгоритма ограничено, онлайн-алгоритм называется конкурентным . [1]
Не у каждого автономного алгоритма есть эффективный онлайн- аналог.
Определение
Поскольку он не знает всех входных данных, онлайн-алгоритм вынужден принимать решения, которые впоследствии могут оказаться неоптимальными, и изучение онлайн-алгоритмов было сосредоточено на качестве принятия решений, которое возможно в этих условиях. Конкурентный анализ формализует эту идею, сравнивая относительную производительность онлайн- и офлайн-алгоритмов для одного и того же экземпляра проблемы. В частности, коэффициент конкурентоспособности алгоритма определяется как отношение его стоимости в наихудшем случае к оптимальной стоимости по всем возможным входам. Конкурентный коэффициент онлайн-задачи - это лучший конкурентный коэффициент, достигаемый онлайн-алгоритмом. Интуитивно понятно, что коэффициент конкурентоспособности алгоритма дает меру качества решений, производимых этим алгоритмом, в то время как коэффициент конкурентоспособности проблемы показывает важность знания будущего для этой проблемы.
Другие интерпретации
Чтобы узнать о других точках зрения на онлайн-входы в алгоритмы , см.
- алгоритм потоковой передачи : акцент на объеме памяти, необходимом для точного представления прошлых входных данных;
- динамический алгоритм : упор на временную сложность поддержки решений проблем с онлайн-входами.
Примеры
Некоторые онлайн-алгоритмы :
Проблемы в сети
Проблемой, иллюстрирующей концепции онлайн-алгоритмов, является проблема канадского путешественника . Цель этой проблемы - минимизировать затраты на достижение цели во взвешенном графе, где некоторые ребра ненадежны и могли быть удалены из графа. Однако то, что ребро было удалено ( не удалось ), путешественник узнает только тогда, когда он / она достигает одной из конечных точек ребра. Худший случай для этой проблемы - это просто отказ всех ненадежных ребер, и проблема сводится к обычной проблеме кратчайшего пути . Альтернативный анализ проблемы может быть сделан с помощью конкурентного анализа. Для этого метода анализа автономный алгоритм заранее знает, какие ребра выйдут из строя, и цель состоит в том, чтобы минимизировать соотношение между производительностью онлайн и офлайн алгоритмов. Эта проблема решена для PSPACE .
Есть много формальных проблем, которые предлагают в качестве решения более одного онлайн-алгоритма :
Смотрите также
Рекомендации
- ^ a b Карп, Ричард М. (1992). «Онлайн-алгоритмы против автономных алгоритмов: сколько стоит знать будущее?» (PDF) . Конгресс ИФИП (1) . 12 : 416–429 . Проверено 17 августа 2015 года .
- ^ Дочоу, Роберт (2016). Онлайн-алгоритмы для задачи выбора портфеля . Springer Gabler.
- Бородин, А .; Эль-Янив Р. (1998). Онлайн-вычисления и конкурентный анализ . Издательство Кембриджского университета. ISBN 0-521-56392-5.
Внешние ссылки
- Библиография статей по онлайн-алгоритмам