Проблема с прокатом лыж.

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

Проблема

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

Рассмотрим человека, который решает покататься на лыжах, но на неопределенное количество дней. Прокат лыж стоит 1 доллар в день, а покупка пары лыж — 10 долларов. Если человек заранее знает, сколько дней он хочет кататься на лыжах, то точка безубыточности составит 10 дней. Менее 10 дней предпочтительна аренда, а более 10 дней – покупка. Однако без предварительного знания того, как долго человек будет кататься на лыжах, точка безубыточности неясна. Хороший алгоритм минимизирует соотношение стоимости, когда количество дней заранее известно, к стоимости, когда количество дней заранее неизвестно. Прокат лыж является одним из примеров этого класса проблем.

Алгоритм безубыточности

Алгоритм безубыточности предписывает арендовать лыжи на 9 дней и купить лыжи утром 10-го дня, если вы еще готовы кататься на лыжах. Если вам придется прекратить кататься на лыжах в течение первых 9 дней, это будет стоить столько же, сколько вы заплатили бы, если бы знали, сколько дней вы будете кататься на лыжах. Если человеку придется прекратить кататься на лыжах после 10-го дня, его затраты составят 19 долларов, что на 90% больше, чем он заплатил бы, если бы заранее знал количество дней, в течение которых он будет кататься на лыжах. Это худший случай для алгоритма безубыточности.

Алгоритм безубыточности известен как лучший детерминированный алгоритм для решения этой задачи.

Рандомизированный алгоритм

Человек может подбросить монетку. Если выпадает решка, она покупает лыжи на восьмой день; в противном случае она покупает лыжи на 10-й день. Это пример рандомизированного алгоритма . Ожидаемая стоимость не более чем на 80% превышает сумму, которую человек заплатил бы, если бы знал, сколько дней он будет кататься на лыжах, независимо от того, сколько дней он катается на лыжах. В частности, если человек катается на лыжах 10 дней, ее ожидаемая стоимость составит 1/2 [7+10] + 1/2 [9+10] = 18 долларов, всего лишь 80% превышения вместо 90%.

Рандомизированный алгоритм можно понимать как совокупность различных алгоритмов, каждый из которых выполняется с заданной вероятностью. Мы определяем ожидаемый коэффициент конкуренции в данном случае i как:

$E_{i}=\sum _{j}P(ALG_{j})\cdot ALG_{j}(i)$, где $ALG_{j}(i)$ - это коэффициент конкуренции, например, i, учитывая $ALG_{j}$.

Следовательно, коэффициент конкуренции рандомизированного алгоритма определяется наихудшим значением $E_{i}$ по всем данным случаям. В случае с прокатом лыж подбрасыванием монеты мы отмечаем, что рандомизированный алгоритм имеет 2 возможных ответвления: если монета выпадает орлом, мы покупаем в день 8, в противном случае мы покупаем в день 10. Мы можем назвать ветви $ALG_{heads}$ и $ALG_{tails}$, соответственно. $E_{i}=P(ALG_{heads})\cdot ALG_{heads}(i)+P(ALG_{tails})\cdot ALG_{tails}(i)={\frac {1}{2}}\cdot 1+{\frac {1}{2}}\cdot 1=1$, для $i<8$.

$E_{8}=P(ALG_{heads})\cdot ALG_{heads}(8)+P(ALG_{tails})\cdot ALG_{tails}(8)={\frac {1}{2}}\cdot {\frac {17}{8}}+{\frac {1}{2}}\cdot 1=1.5625$,

$E_{9}=P(ALG_{heads})\cdot ALG_{heads}(9)+P(ALG_{tails})\cdot ALG_{tails}(9)={\frac {1}{2}}\cdot {\frac {17}{9}}+{\frac {1}{2}}\cdot 1=1.444444$, и

$E_{i}=P(ALG_{heads})\cdot ALG_{heads}(i)+P(ALG_{tails})\cdot ALG_{tails}(i)={\frac {1}{2}}\cdot {\frac {17}{10}}+{\frac {1}{2}}\cdot {\frac {19}{10}}=1.8$, для $i\geq 10$.

Таким образом, коэффициент конкуренции рандомизированного алгоритма подбрасывания монеты с прокатом лыж составляет 1,8.

Лучший рандомизированный алгоритм против ничего не замечающего противника состоит в том, чтобы случайным образом выбрать какой-нибудь день i в соответствии со следующим распределением p, арендовать его на i-1 дней и купить лыжи утром дня i, если кто-то еще готов кататься на лыжах. Карлин и др. впервые представил этот алгоритм с распределением $p_{i}=\left\{{\begin{array}{ll}({\frac {b-1}{b}})^{b-i}{\frac {1}{b(1-(1-(1/b))^{b})}}&i\leq b\\0&i>b\end{array}}\right.,$ где покупка лыж стоит $ $b$ и аренда стоит 1 доллар. Его ожидаемая стоимость не превосходит e/(e-1) $\approx$ В 1,58 раза больше, чем заплатили бы, если бы знали, сколько дней придется кататься на лыжах. Ни один рандомизированный алгоритм не сможет добиться большего.

Приложения

• Снупи-кэширование : несколько кэшей используют одно и то же пространство памяти, разделенное на блоки. Когда кеш записывает в блок, кеш-память, разделяющая этот блок, тратит 1 цикл шины на обновление. Эти кеши могут сделать блок недействительным, чтобы избежать затрат на обновление. Но существует штраф в p циклов шины за аннулирование блока из кэша, которому вскоре после этого потребуется доступ к нему. Мы можем разбить последовательности запросов записи для нескольких кешей на последовательности запросов для двух кешей. Один кэш выполняет последовательность операций записи в блок. Другой кэш должен решить, следует ли обновляться, оплачивая 1 цикл шины за операцию, или сделать блок недействительным, заплатив p циклов шины за будущий запрос на чтение самого себя. Проблема с двумя кэшами и одним блоком слежения за кешированием — это всего лишь проблема проката лыж.

• TCP-подтверждение : Поток пакетов прибывает в пункт назначения и требует подтверждения протоколом TCP по прибытии. Однако мы можем использовать один пакет подтверждения для одновременного подтверждения нескольких ожидающих пакетов, тем самым уменьшая накладные расходы на подтверждения. С другой стороны, слишком большая задержка подтверждений может помешать механизмам контроля перегрузки TCP, и поэтому мы не должны допускать слишком большого увеличения задержки между временем прибытия пакета и временем отправки подтверждения. Карлин и др. описал семейство входных данных с одним параметром, называемое базовыми входными данными, и показал, что при ограничении этими базовыми входными данными проблема подтверждения TCP ведет себя так же, как проблема аренды лыж.

• Планирование общего времени завершения : Мы хотим запланировать задания с фиксированным временем обработки на m одинаковых машинах. Время обработки задания j равно p _j . Каждое задание становится известно планировщику в момент его выпуска r _j . Цель состоит в том, чтобы минимизировать сумму времени завершения для всех заданий. Упрощенная задача — это одна машина со следующими входными данными: в момент времени 0 поступает задание со временем обработки 1; k заданий со временем обработки 0 приходят в неизвестное время. Нам нужно выбрать время начала для первого задания. Ожидание требует затрат 1 доллара за единицу времени, однако запуск первого задания до того, как последующие k заданий могут повлечь за собой дополнительные затраты в размере k в худшем случае. Эту упрощенную задачу можно рассматривать как непрерывную версию проблемы аренды лыж.

• Рефакторинг против работы с плохим дизайном . При разработке программного обеспечения инженерам приходится выбирать между трудностями и риском ошибок при работе со слишком сложным дизайном и уменьшением сложности проекта перед внесением изменений. Дополнительные затраты на каждое изменение в старом дизайне — это стоимость «аренды», стоимость рефакторинга — это стоимость «покупки». «Сколько раз приходится работать с плохим дизайном, прежде чем его исправить?» проблема с прокатом лыж.

См. также

• Противник (онлайн-алгоритм)
• Конкурентный анализ (онлайн-алгоритм)
• Онлайн-алгоритм
• Оптимальная остановка
• Доказательство в худшем случае