Проблема с прокатом лыж - Ski rental problem

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

Проблема

Много онлайн-проблемы есть подзадача, называемая проблемой аренды / покупки. Нам нужно решить, оставаться ли в текущем состоянии и платить определенную сумму за единицу времени, или переключиться в другое состояние и платить некоторую фиксированную большую стоимость без дополнительных платежей.^[1] Прокат лыж^[2][3] это один из примеров, когда аренда / покупка - это вся проблема. Его базовая версия:

Человек катается на лыжах неизвестное количество дней. Аренда лыж стоит 1 доллар в день, а покупка лыж стоит 10 долларов. Каждый день человек должен решать, продолжать ли брать лыжи напрокат еще на один день или купить пару лыж. Если человек заранее знает, сколько дней он будет кататься на лыжах, он может определить свою минимальную стоимость. Если она будет кататься на лыжах более 10 дней, будет дешевле покупать лыжи, но если она будет кататься менее 10 дней, будет дешевле арендовать лыжи. Что ей делать, если она заранее не знает, сколько дней кататься на лыжах?^{[нужна цитата ]}

Формально проблему можно поставить так. Есть количество дней d (неизвестно), что человек будет кататься на лыжах. Цель состоит в том, чтобы найти алгоритм, который минимизирует соотношение между тем, что человек платит, используя алгоритм (который не знает d) и сколько человек заплатил бы оптимально, если бы он знал d заранее. Проблема обычно анализируется в наихудшем случае, когда алгоритм фиксируется, а затем мы смотрим на производительность алгоритма в наихудшем случае по всем возможным d. В частности, не делается никаких предположений относительно распределения d (и легко увидеть, что, зная распределение d, был бы предпочтительнее другой анализ, а также другие решения).^{[нужна цитата ]}

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

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

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

Безубыточность

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

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

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

Следовательно, коэффициент конкуренции рандомизированного алгоритма определяется наихудшим значением ${displaystyle E_{i}}$ по всем данным экземплярам. В случае проката лыжного снаряжения с подбрасыванием монеты мы отмечаем, что рандомизированный алгоритм имеет 2 возможных ветвления: если выпадает орел, мы покупаем в 8-й день, в противном случае мы покупаем в 10-й день. ${displaystyle ALG_{heads}}$ и ${displaystyle ALG_{tails}}$, соответственно. ${displaystyle 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}$, за ${displaystyle i<8}$. ${displaystyle 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}$, ${displaystyle 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}$, и ${displaystyle 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}$, за ${displaystyle igeq 10}$.

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

Лучший рандомизированный алгоритм против невнимательный противник состоит в том, чтобы выбрать какой-нибудь день i наугад в соответствии со следующим распределением p, арендовать лыжи на i-1 дней и купить лыжи утром i-го дня, если они все еще готовы кататься. Karlin et al.^[2] впервые представил этот алгоритм с распределением${displaystyle p_{i}=left{{egin{array}{ll}({frac {b-1}{b}})^{b-i}{frac {1}{b(1-(1-(1/b))^{b})}}&ileq b�&i>bend{array}}ight.,}$где покупка лыж стоит $${displaystyle b}$ а аренда стоит 1 доллар. Его ожидаемая стоимость составляет не более e / (e-1). ${displaystyle approx }$ В 1,58 раза больше, чем можно было бы заплатить, если бы знал, сколько дней он будет кататься на лыжах. Никакой рандомизированный алгоритм не может быть лучше.

Приложения

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

• Подтверждение TCP:^[5] Поток пакетов прибывает в пункт назначения, и протокол TCP требует подтверждения по прибытии. Однако мы можем использовать один пакет подтверждения для одновременного подтверждения нескольких ожидающих пакетов, тем самым уменьшая накладные расходы на подтверждения. С другой стороны, слишком большая задержка подтверждений может повлиять на механизмы управления перегрузкой TCP, и поэтому мы не должны допускать чрезмерного увеличения задержки между временем прибытия пакета и временем отправки подтверждения. Karlin et al.^[6] описал однопараметрическое семейство входов, называемых базовыми входами, и показал, что при ограничении этими базовыми входами проблема подтверждения TCP ведет себя так же, как проблема аренды лыж.

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

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

Смотрите также

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

Рекомендации

1. Стивен С. Сейден. Угадайка и рандомизированные онлайн-алгоритмы. Ежегодный симпозиум ACM по теории вычислений, 2000 г. http://portal.acm.org/citation.cfm?id=335385
2. А. Р. Карлин, М. С. Манассе, Л. А. МакГеоч и С. Овики. Конкурентные рандомизированные алгоритмы для неоднородных задач. In Proceedings of the First Annual ACM-SIAM Symposium on Discrete Algorithms, Сан-Франциско, Калифорния, 22 января 1990 г., стр. 301-309. Также в Algorithmica, 11 (6): 542-571, 1994. http://courses.csail.mit.edu/6.895/fall03/handouts/papers/karlin.pdf
3. Клэр Матье. Брауновский университет. Лекция: http://www.cs.brown.edu/~claire/Talks/skirental.pdf
4. А. Р. Карлин, М. Манассе, Л. Рудольф и Д. Слейтор. Конкурентное кеширование Snoopy. Algorithmica, 3 (1): 79-119, 1988 г.
5. Д. Р. Дули, С. А. Голдман и С. Д. Скотт. Задержка динамического подтверждения TCP: теория и практика // Proceedings of the Thirtieth Annual ACM Symposium on Theory of Computing (STOC), Dallas, TX, pp. 389-398, 1998.
6. Анна Р. Карлин и Клэр Кеньон и Дана Рэндалл. Динамическое подтверждение TCP и другие истории про e / (e-1). Тридцать третий ежегодный симпозиум ACM по теории вычислений (STOC), 2001. Algorithmica. http://www.cs.brown.edu/people/claire/Publis/ACKpaper.ps