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