Задача прокату лиж — це назва для класу задач, в яких стоїть вибір серед двох альтернатив: нести періодичні витрати або зробити одноразовий платіж, що усуває або зменшує ці періодичні витрати.
Задача ред.
Багато онлайн задач містять підзадачу, відому як задача вибору між купівлею та орендою. Нам потрібно вирішити чи залишитися у поточному стані і нести певну суму витрат на одиницю часу, або перейти до іншого стану і заплатити деяку фіксовану велику суму без подальших платежів. Задача прокату лиж — класичний ігровий приклад, де оренда/купівля і є задачею. Її базова версія формулюється таким чином:
Ви збираєтесь кататися на лижах протягом невідомого числа днів (ви не знаєте точне число через різні причини, наприклад, втрата цікавості, випадки, в яких ви ламаєте ногу, або дуже погана погода). Припустімо, що прокат лиж коштує $1 на день а купівля лиж — $10. Кожен день ви маєте вирішувати чи продовжити брати лижі на прокат ще на один день або купити пару лиж. Якщо ви знаєте заздалегідь скільки днів ви кататиметесь на лижах, ви можете обрати варіант з найменшими витратами. Наприклад, якщо ви будете кататися протягом більше ніж 10 днів — дешевше буде купити лижі, але, якщо ви кататиметесь менше ніж 10 днів, то дешевше взяти їх у прокат. (Якщо ви кататиметесь точно 10 днів — вам байдуже.) Питання — що робити, коли ви не знаєте заздалегідь скільки днів ви кататиметесь.
Формально, задача може бути поставлена таким чином. Є число днів d (невідоме вам) протягом яких ви будете кататися на лижах. Ми шукаємо алгоритм, що мінімізує відношення між сумою, сплаченою використовуючи цей алгоритм (що не знає d) і сумою в найкращому випадку, якщо ви знаєте d наперед. Ця задача, як правило, аналізується у найгіршому випадку, де алгоритм фіксований і тоді ми дивимось на точність алгоритму у найгіршому випадку для всіх можливих d. Зокрема, не робить ніяких припущень відносно відносно розподілу d (і легко побачити, що, зі знанням розподілу d, перевагу віддавалася б іншому аналізу, також як іншим розв'язкам).
Беззбитковий алгоритм ред.
Беззбитковий алгоритм вказує брати у прокат протягом 9 днів і купити лижі на ранок дня 10 якщо ви все ще готові кататися. Якщо ви маєте припинити кататися протягом перших 9 днів, це коштує те саме, якщо б ви знали число днів, протягом яких ви кататиметесь. Якщо ви маєте зупинитись після 10 дня, ваші витрати — $19, що становить 90% більше від оптимуму. Це найгірший випадок для беззбиткового алгоритму.
Беззбитковий алгоритм відомий як найкращий детерміністичний алгоритм для цієї задачі.
Див. також ред.
- Супротивник (онлайн алгоритм)
- Порівняльний аналіз (онлайн алгоритм)
- Онлайн алгоритм
Посилання ред.
- 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
- 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.]
- Claire Mathieu. Brown University. Lecture note: http://www.cs.brown.edu/people/claire/skirental.pdf [ 12 вересня 2006 у Wayback Machine.]
- A. R. Karlin, M. Manasse, L. Rudolph and D. Sleator. Competitive snoopy caching. Algorithmica, 3(1): 79-119, 1988