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

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

Ключевые концепции

Конкурентный анализ

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

Модели противников

Онлайн-алгоритмы часто предполагают модели противников, где противник определяет последовательность вводов для максимизации недостатка онлайн-алгоритма. Распространенные модели противников включают:

• Забывчивый противник: Не знает внутреннего состояния онлайн-алгоритма при построении входной последовательности.
• Адаптивный противник: Строит входную последовательность, зная внутреннее состояние онлайн-алгоритма на каждом шаге.
• Адаптивный онлайн-противник: Строит ввод по мере продвижения алгоритма, но фиксирует всю входную последовательность перед просмотром любых решений, принятых алгоритмом.

Жадные алгоритмы

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

Распространенные онлайн-проблемы

Проблема страничной памяти

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

• Наименее недавно использованная (LRU): Вытесняет страницу, которая не использовалась дольше всего.
• Первый пришел, первый вышел (FIFO): Вытесняет самую старую страницу в кэше.
• Наименее часто используемая (LFU): Вытесняет страницу с наименьшей частотой доступа.

Проблема K-сервера

Проблема K-сервера включает набор K серверов, расположенных в точках метрического пространства, и последовательность запросов, каждый из которых указывает точку в метрическом пространстве. Целью является перемещение серверов для обслуживания запросов способом, который минимизирует общую стоимость перемещения. Заметные онлайн-стратегии для этой проблемы включают:

• Алгоритм рабочей функции: Принимает решения на основе рабочей функции, которая учитывает минимальную стоимость обслуживания всех запросов, увиденных до сих пор.
• Жадный алгоритм: Перемещает ближайший сервер к запрошенной точке.

Онлайн-биpartite сопоставление

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

Проблема аренды лыж

Проблема аренды лыж иллюстрирует баланс между арендой и покупкой. Учитывая стоимость аренды лыж за день и стоимость покупки лыж, целью является минимизация общей стоимости без знания заранее, сколько дней будет катания на лыжах. 2-конкурентный алгоритм арендует лыжи до тех пор, пока кумулятивная стоимость аренды не достигнет стоимости покупки, затем покупает лыжи.

Применения в реальном мире

Онлайн-распределение рекламы

Онлайн-распределение рекламы включает назначение рекламных слотов рекламодателям в реальном времени, когда пользователи загружают веб-страницы. Эта проблема очень актуальна в цифровом маркетинге, и онлайн-алгоритмы используются для балансировки немедленного дохода с долгосрочными выгодами. Компании, такие как Google, обрабатывают эти ситуации, используя онлайн-алгоритмы (Google Ads).

Сервисы вызова такси

Сервисы вызова такси, такие как Uber, должны сопоставлять водителей с запросами на поездку динамически. Целью является минимизация времени ожидания для пассажиров и времени простоя для водителей. Uber использует онлайн-алгоритмы для оптимизации этого процесса сопоставления (Uber).

Управление облачными ресурсами

В облачных вычислениях управление ресурсами включает динамическое распределение вычислительных ресурсов. Компании, такие как Amazon Web Services (AWS), используют онлайн-алгоритмы для распределения экземпляров на задачи, отправленные клиентами (AWS). Целью является максимизация использования ресурсов при минимизации стоимости и обеспечении качества обслуживания.

Торговля на фондовом рынке

Алгоритмическая торговля включает совершение транзакций на финансовых рынках с использованием заранее запрограммированных кодов, где решения должны приниматься в реальном времени в ответ на движения рынка. Компании, такие как Two Sigma и Renaissance Technologies, используют сложные онлайн-алгоритмы для управления портфелями и выполнения сделок (Two Sigma, Renaissance Technologies).

Примеры алгоритмов и их конкурентные соотношения

Онлайн-алгоритмы страничной памяти

1. LRU (Наименее недавно использованная): Этот алгоритм имеет конкурентное соотношение k, где k — размер кэша.
2. FIFO (Первый пришел, первый вышел): Также имеет конкурентное соотношение k.
3. LFU (Наименее часто используемая): Обычно не работает так же хорошо, как LRU или FIFO в терминах конкурентного соотношения.

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

1. Алгоритм рабочей функции: Для общих метрических пространств с k серверами конкурентное соотношение составляет 2k - 1.
2. Алгоритм двойного покрытия: Для специального случая проблемы k-сервера на линии конкурентное соотношение составляет k.

Онлайн-алгоритмы сопоставления

1. Алгоритм ранжирования: В контексте онлайн-биpartite сопоставления алгоритм ранжирования достигает конкурентного соотношения (1 - 1/e), где e — основание натурального логарифма.
2. Жадный алгоритм: Простой и эффективный, но менее эффективный, чем алгоритм ранжирования, когда производительность измеряется в терминах конкурентного соотношения.

Резюме

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