Войти
В информатике онлайн-алгоритм - это алгоритм, который может обрабатывать входные данные последовательно по частям, т. е. в том порядке, в котором входные данные передаются в алгоритм , без того, чтобы весь вход был доступен с самого начала.
Напротив, автономный алгоритм получает все данные о проблеме с самого начала и требуется для вывода ответа, который решает текущую проблему. В исследовании операций область, в которой разрабатываются онлайн-алгоритмы, называется онлайн-оптимизацией.
В качестве примера рассмотрим алгоритмы сортировки сортировка выбора и сортировка вставкой : сортировка по выбору повторно выбирает минимальный элемент из несортированного остатка и помещает его впереди, что требует доступа ко всему вводу; таким образом, это автономный алгоритм. С другой стороны, сортировка вставкой учитывает один входной элемент на итерацию и дает частичное решение без учета будущих элементов. Таким образом, сортировка вставкой - это онлайн-алгоритм.
Обратите внимание, что окончательный результат сортировки вставкой является оптимальным, то есть правильно отсортированный список. Для многих проблем онлайн-алгоритмы не могут сравниться по производительности с автономными алгоритмами. Если соотношение между производительностью онлайн-алгоритма и оптимального автономного алгоритма ограничено, интерактивный алгоритм называется конкурентным.
Не каждый автономный алгоритм имеет эффективный онлайн-аналог.
Поскольку он не знает всех входных данных, онлайн-алгоритм вынужден принимать решения, которые впоследствии могут оказаться неоптимальными, и изучение онлайн-алгоритмов было сосредоточено на качестве принятия решений, которое возможно в этом настройка. Конкурентный анализ формализует эту идею, сравнивая относительную производительность онлайн-алгоритма и автономного алгоритма для одного и того же экземпляра проблемы. В частности, коэффициент конкурентоспособности алгоритма определяется как отношение его стоимости в наихудшем случае к оптимальной стоимости по всем возможным входам. Конкурентный коэффициент онлайн-задачи - это лучший конкурентный коэффициент, достигаемый онлайн-алгоритмом. Интуитивно понятно, что коэффициент конкуренции алгоритма дает меру качества решений, производимых этим алгоритмом, в то время как коэффициент конкурентоспособности проблемы показывает важность знания будущего для этой проблемы.
Другие точки зрения на входные данные онлайн в алгоритмы см. В разделе
Некоторые онлайн-алгоритмы:
A Проблемой, иллюстрирующей концепции онлайн-алгоритмов, является Проблема канадского путешественника. Цель этой проблемы - минимизировать стоимость достижения цели во взвешенном графе, где некоторые ребра ненадежны и могли быть удалены из графа. Однако то, что ребро было удалено (не удалось), путешественник узнает только тогда, когда он / она достигает одной из конечных точек ребра. Наихудший случай для этой проблемы - это просто отказ всех ненадежных ребер, и проблема сводится к обычной проблеме Кратчайшего пути. Альтернативный анализ проблемы может быть сделан с помощью конкурентного анализа. Для этого метода анализа автономный алгоритм заранее знает, какие ребра выйдут из строя, и цель состоит в том, чтобы свести к минимуму соотношение между производительностью оперативного и автономного алгоритмов. Эта проблема PSPACE-complete.
Существует много формальных проблем, которые предлагают более одного онлайн-алгоритма в качестве решения:
