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

Эта статья поднимает множество проблем. Пожалуйста, помогите улучшить его или обсудите эти проблемы на странице обсуждения . ( Узнайте, как и когда удалить эти сообщения-шаблоны ) Эта статья может быть слишком технической, чтобы ее могло понять большинство читателей . Пожалуйста, помогите улучшить его, чтобы он был понятен неспециалистам , не удаляя технические детали. ( Июль 2020 г. ) ( Узнайте, как и когда удалить этот шаблон сообщения ) Эта статья требует дополнительных ссылок для проверки . Пожалуйста, помогите улучшить эту статью , добавив цитаты из надежных источников . Материал, не полученный от источника, может быть оспорен и удален. Найти источники:  «Проблема с прокатом лыж»  -  новости  · газеты  · книги  · ученый  · JSTOR ( июль 2020 г. ) ( Узнайте, как и когда удалить это сообщение-шаблон ) ( Узнайте, как и когда удалить этот шаблон сообщения )

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

Проблема [ править ]

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

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

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

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

Алгоритм безубыточности [ править ]

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

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

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

Безубыточность [ править ]

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

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

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

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

Следовательно, коэффициент конкуренции рандомизированного алгоритма определяется наихудшим значением из всех данных экземпляров. В случае проката лыжного снаряжения с подбрасыванием монеты мы отмечаем, что рандомизированный алгоритм имеет 2 возможных ветвления: если выпадает орел, мы покупаем в 8-й день, в противном случае мы покупаем в 10-й день. Мы можем назвать ветки и , соответственно, . , для . , и , для . ${\ displaystyle E_ {i}}$${\ displaystyle ALG_ {Heads}}$${\ displaystyle ALG_ {хвосты}}$${\ 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 я <8}$${\ Displaystyle E_ {8} = P (ALG_ {головки}) \ cdot ALG_ {головки} (8) + P (ALG_ {хвосты}) \ cdot ALG_ {хвосты} (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 i\geq 10}$

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

Лучший рандомизированный алгоритм против ничего не подозревающего противника - это случайным образом выбрать день i в соответствии со следующим распределением p, арендовать лыжи на i-1 дней и купить лыжи утром i-го дня, если они все еще готовы кататься на лыжах. Karlin et al. ^[2] впервые представил этот алгоритм с распределением, в котором покупка лыж стоит $ 1, а аренда стоит $ 1. Его ожидаемая стоимость составляет не более e / (e-1) в 1,58 раза больше, чем можно было бы заплатить, если бы знал количество дней, в течение которых можно кататься на лыжах. Никакой рандомизированный алгоритм не может быть лучше.${\displaystyle 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.,}$${\displaystyle b}$${\displaystyle \approx }$

Приложения [ править ]

• Кэширование Snoopy : ^[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 в худшем случае. Эту упрощенную задачу можно рассматривать как непрерывную версию проблемы проката лыж.

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

См. Также [ править ]

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

Ссылки [ править ]