Начало
Учебные материалы
Методы уменьшения размера задачи
Идея методов уменьшения размера задачи Сортировка вставками Поиск в глубину и поиск в ширину Алгоритмы генерации комбинаторных объектов Бинарный поиск Задача поиска фальшивой монеты Задача выбора Онлайновые алгоритмы
Онлайновые алгоритмы
в том порядке, в котором входные данные передаются в алгоритм, без того, чтобы весь вход был доступен с самого начала.
Напротив, автономный алгоритм получает все данные о проблеме с самого начала и они все требуются для получения
ответа, который решает текущую проблему.
--
В качестве примера рассмотрим алгоритмы сортировки сортировка выбором и сортировка вставками:
сортировка выбором повторно выбирает минимальный элемент из несортированного остатка и помещает его
впереди, что требует доступа ко всему массиву; таким образом, это автономный алгоритм.
С другой стороны, сортировка вставками учитывает один входной элемент на итерацию и дает частичное решение без учета будущих элементов.
Таким образом, сортировка вставкой -- это онлайновый алгоритм.
Задача может быть решена онлайн, если к ней применим метод уменьшения размера на 1 снизу вверх.
Для многих задач онлайновые алгоритмы не могут сравниться по производительности с автономными алгоритмами:
`O(n^2)` для сортировки вставками и `O(n log n)` для сортировки слиянием.
--
Окончательный результат сортировки вставками является оптимальным, то есть правильно отсортированный список.
Но часто окончательный и промежуточные результаты могут быть не оптимальными,
так как алгоритм не знает всех входных данных, которые
могут быть неизвестного размера или даже бесконечными, и должен принимать решения, основываясь на неполной информации,
не зная будущих событий.
Если соотношение между качеством решения онлайнового алгоритма и оптимального автономного алгоритма ограничено,
онлайновый алгоритм называется *конкурентным*. Коэффициент конкурентоспособности алгоритма определяется как отношение
стоимости его решения в наихудшем случае к оптимальной стоимости по всем возможным входам.
--
```hide Задача канадского путешественника
Это обобщение задачи о кратчайшем пути на графе, информация о ребрах которого появляется по мере его изучения (снегопад), а исследованные рёбра дают вклад в стоимость, даже если они не принадлежат конечному пути.
```
```hide Задача о разборчивой невесте (игра в гугол)
Невеста ищет себе жениха среди `n` претендентов. Она беседует с ними и и либо отказывает, либо принимает его предложение. Если предложение принято, они женятся и процесс останавливается. Если невеста отказывает жениху, то вернуться к нему позже она не сможет. О каждом претенденте известно, лучше он или хуже любого из предыдущих. Невеста выигрывает, если она выберет самого лучшего претендента. Выбор даже второго по порядку сравнения — проигрыш.
Оптимальная стратегия будет заключаться в том, чтобы отклонить всех первых `n//e` претендентов и затем выбрать первого, кто будет лучше всех предыдущих. Вероятность выбора наилучшего претендента стремится к
`1//e`.
*Игра в гугол* Алиса пишет на нескольких листках любые числа, возможно не целые, от 0 до `10^100` (гугол). Цель игры -- найти самое большое число. Боб по очереди переворачивает листки и останавливается, когда дойдет до числа, которое по его мнению является самым большим. Он не может вернуться и выбрать ранее перевернутый лист. Если он перевернет все листы, то ему придется выбрать последний перевернутый.
```
```hide Задача обновления списка
Дан набор элементов. Стоимость доступа к элементу пропорциональна его расстоянию от начала списка. На основании выполненных запросов можно перемещать элементы к началу списка так, чтобы стоимость доступа уменьшалась.
Пример -- поисковые запросы в браузере. Неудачная попытка применения -- изменяющиеся меню в Office 2003.
```
```hide Задача проката лыж
Человек собирается кататься на лыжах неизвестное ему количество дней (потому что его могут вызвать из отпуска на работу). Прокат лыж стоит 1 доллар в день, покупка лыж -- 10 долларов. Каждый день человек должен решить, продолжать ли арендовать лыжи еще на один день или купить пару лыж.
Наилучшей стратегией является аренда лыж в первые 9 дней и покупка на 10 день. Коэффициент конкурентоспособности такого алгоритма равен 1.9. Можно улучшить этот коэффициент до `e//(e-1)~~1.58`, выбирая случайный день покупки лыж.
```
