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

Не путать онлайн и офлайн .

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

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

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

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

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

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

Определение

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

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

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

• алгоритм потоковой передачи : упор на объем памяти, необходимый для точного представления прошлых входных данных;
• динамический алгоритм : упор на временную сложность поддержки решений проблем с онлайн-входами.

Примеры

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

• Сортировка вставкой
• Персептрон
• Отбор проб из резервуара
• Жадный алгоритм
• Модель противника
• Метрические системы задач
• Алгоритм шансов
• Алгоритм замены страниц
• Алгоритмы расчета дисперсии
• Алгоритм Укконена

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

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

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

• k -сервером проблема с
• Проблема с расписанием работы магазина
• Проблема с обновлением списка
• Бандитская проблема
• Проблема с секретарем
• Поиск игр
• Проблема с прокатом лыж.
• Задача линейного поиска
• Проблема выбора портфеля

См. также

• Динамический алгоритм
• Неравенство Пророка
• Вычисления в реальном времени
• Алгоритм потоковой передачи
• Последовательный алгоритм
• Машинное обучение онлайн / Офлайн обучение

Ссылки

• Бородин А. ; Эль-Янив, Р. (1998). Онлайн-вычисления и конкурентный анализ . Издательство Кембриджского университета. ISBN  0-521-56392-5 .

Внешние ссылки

• Библиография статей по онлайн-алгоритмам