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