Задача прокату лиж

Задача прокату лиж — це назва для класу задач, в яких стоїть вибір серед двох альтернатив: нести періодичні витрати або зробити одноразовий платіж, що усуває або зменшує ці періодичні витрати.

Задача

Багато онлайн задач містять підзадачу, відому як задача вибору між купівлею та орендою. Нам потрібно вирішити чи залишитися у поточному стані і нести певну суму витрат на одиницю часу, або перейти до іншого стану і заплатити деяку фіксовану велику суму без подальших платежів[1]. Задача прокату лиж[2][3] — класичний ігровий приклад, де оренда/купівля і є задачею. Її базова версія формулюється таким чином:

Ви збираєтесь кататися на лижах протягом невідомого числа днів (ви не знаєте точне число через різні причини, наприклад, втрата цікавості, випадки, в яких ви ламаєте ногу, або дуже погана погода). Припустімо, що прокат лиж коштує $1 на день а купівля лиж — $10. Кожен день ви маєте вирішувати чи продовжити брати лижі на прокат ще на один день або купити пару лиж. Якщо ви знаєте заздалегідь скільки днів ви кататиметесь на лижах, ви можете обрати варіант з найменшими витратами. Наприклад, якщо ви будете кататися протягом більше ніж 10 днів — дешевше буде купити лижі, але, якщо ви кататиметесь менше ніж 10 днів, то дешевше взяти їх у прокат. (Якщо ви кататиметесь точно 10 днів — вам байдуже.) Питання — що робити, коли ви не знаєте заздалегідь скільки днів ви кататиметесь.

Формально, задача може бути поставлена таким чином. Є число днів d (невідоме вам) протягом яких ви будете кататися на лижах. Ми шукаємо алгоритм, що мінімізує відношення між сумою, сплаченою використовуючи цей алгоритм (що не знає d) і сумою в найкращому випадку, якщо ви знаєте d наперед. Ця задача, як правило, аналізується у найгіршому випадку, де алгоритм фіксований і тоді ми дивимось на точність алгоритму у найгіршому випадку для всіх можливих d. Зокрема, не робить ніяких припущень відносно відносно розподілу d (і легко побачити, що, зі знанням розподілу d, перевагу віддавалася б іншому аналізу, також як іншим розв'язкам).

Беззбитковий алгоритм

Беззбитковий алгоритм вказує брати у прокат протягом 9 днів і купити лижі на ранок дня 10 якщо ви все ще готові кататися[4]. Якщо ви маєте припинити кататися протягом перших 9 днів, це коштує те саме, якщо б ви знали число днів, протягом яких ви кататиметесь. Якщо ви маєте зупинитись після 10 дня, ваші витрати — $19, що становить 90% більше від оптимуму. Це найгірший випадок для беззбиткового алгоритму.

Беззбитковий алгоритм відомий як найкращий детерміністичний алгоритм для цієї задачі.

Див. також
  • Супротивник (онлайн алгоритм)
  • Порівняльний аналіз (онлайн алгоритм)
  • Онлайн алгоритм

Посилання
  1. Steven S. Seiden. A guessing game and randomized online algorithms. Annual ACM Symposium on Theory of Computing, 2000. http://portal.acm.org/citation.cfm?id=335385
  2. A. R. Karlin, M. S. Manasse, L. A. McGeoch, and S. Owicki. Competitive randomized algorithms for non-uniform problems. In Proceedings of the First Annual ACM-SIAM Symposium on Discrete Algorithms, San Francisco, CA, 22-24 January 1990, pp. 301—309. Also in Algorithmica, 11(6): 542—571, 1994. http://theory.lcs.mit.edu/classes/6.895/fall03/handouts/papers/karlin.pdf Архівовано 20 вересня 2006 у Wayback Machine.
  3. Claire Mathieu. Brown University. Lecture note: http://www.cs.brown.edu/people/claire/skirental.pdf%5Bнедоступне+посилання+з+липня+2019%5D
  4. A. R. Karlin, M. Manasse, L. Rudolph and D. Sleator. Competitive snoopy caching. Algorithmica, 3(1): 79-119, 1988
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.