Подразделы

Другие разделы

Дата и время

04/04/2025 12:26:43

Авторизация

Методы уменьшения размера задачи

Идея методов уменьшения размера задачи Сортировка вставками Поиск в глубину и поиск в ширину Алгоритмы генерации комбинаторных объектов Бинарный поиск Задача поиска фальшивой монеты Задача выбора Онлайновые алгоритмы

Онлайновые алгоритмы

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

Напротив, автономный алгоритм получает все данные о проблеме с самого начала и они все требуются для получения ответа, который решает текущую проблему.

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

Задача может быть решена онлайн, если к ней применим метод уменьшения размера на 1 снизу вверх.

Для многих задач онлайновые алгоритмы не могут сравниться по производительности с автономными алгоритмами: $O(n^2)$ для сортировки вставками и $O(n log n)$ для сортировки слиянием.

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

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

Задача канадского путешественника

Это обобщение задачи о кратчайшем пути на графе, информация о ребрах которого появляется по мере его изучения (снегопад), а исследованные рёбра дают вклад в стоимость, даже если они не принадлежат конечному пути.

Задача о разборчивой невесте (игра в гугол)

Невеста ищет себе жениха среди $n$ претендентов. Она беседует с ними и и либо отказывает, либо принимает его предложение. Если предложение принято, они женятся и процесс останавливается. Если невеста отказывает жениху, то вернуться к нему позже она не сможет. О каждом претенденте известно, лучше он или хуже любого из предыдущих. Невеста выигрывает, если она выберет самого лучшего претендента. Выбор даже второго по порядку сравнения — проигрыш.

Оптимальная стратегия будет заключаться в том, чтобы отклонить всех первых $n//e$ претендентов и затем выбрать первого, кто будет лучше всех предыдущих. Вероятность выбора наилучшего претендента стремится к $1//e$ .

Игра в гугол Алиса пишет на нескольких листках любые числа, возможно не целые, от 0 до $10^100$ (гугол). Цель игры – найти самое большое число. Боб по очереди переворачивает листки и останавливается, когда дойдет до числа, которое по его мнению является самым большим. Он не может вернуться и выбрать ранее перевернутый лист. Если он перевернет все листы, то ему придется выбрать последний перевернутый.

Задача обновления списка

Дан набор элементов. Стоимость доступа к элементу пропорциональна его расстоянию от начала списка. На основании выполненных запросов можно перемещать элементы к началу списка так, чтобы стоимость доступа уменьшалась.

Пример – поисковые запросы в браузере. Неудачная попытка применения – изменяющиеся меню в Office 2003.

Задача проката лыж

Человек собирается кататься на лыжах неизвестное ему количество дней (потому что его могут вызвать из отпуска на работу). Прокат лыж стоит 1 доллар в день, покупка лыж – 10 долларов. Каждый день человек должен решить, продолжать ли арендовать лыжи еще на один день или купить пару лыж.