Azərbaycanca
Беларускі
Dansk
Deutsch
Española
Français
Indonesia
Italiana
日本語
Қазақ
Lietuvos
Nederlands
Português
Русский
සිංහල
แบบไทย
Türkçe
Українська
中國人
United State
Afrikaans
Задача прокату лиж — це назва для класу задач, в яких стоїть вибір серед двох альтернатив: нести періодичні витрати або зробити одноразовий платіж, що усуває або зменшує ці періодичні витрати.
Задача
Багато онлайн задач містять підзадачу, відому як задача вибору між купівлею та орендою. Нам потрібно вирішити чи залишитися у поточному стані і нести певну суму витрат на одиницю часу, або перейти до іншого стану і заплатити деяку фіксовану велику суму без подальших платежів. Задача прокату лиж — класичний ігровий приклад, де оренда/купівля і є задачею. Її базова версія формулюється таким чином:
Ви збираєтесь кататися на лижах протягом невідомого числа днів (ви не знаєте точне число через різні причини, наприклад, втрата цікавості, випадки, в яких ви ламаєте ногу, або дуже погана погода). Припустімо, що прокат лиж коштує $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
Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет
Zadacha prokatu lizh ce nazva dlya klasu zadach v yakih stoyit vibir sered dvoh alternativ nesti periodichni vitrati abo zrobiti odnorazovij platizh sho usuvaye abo zmenshuye ci periodichni vitrati ZadachaBagato onlajn zadach mistyat pidzadachu vidomu yak zadacha viboru mizh kupivleyu ta orendoyu Nam potribno virishiti chi zalishitisya u potochnomu stani i nesti pevnu sumu vitrat na odinicyu chasu abo perejti do inshogo stanu i zaplatiti deyaku fiksovanu veliku sumu bez podalshih platezhiv Zadacha prokatu lizh klasichnij igrovij priklad de orenda kupivlya i ye zadacheyu Yiyi bazova versiya formulyuyetsya takim chinom Vi zbirayetes katatisya na lizhah protyagom nevidomogo chisla dniv vi ne znayete tochne chislo cherez rizni prichini napriklad vtrata cikavosti vipadki v yakih vi lamayete nogu abo duzhe pogana pogoda Pripustimo sho prokat lizh koshtuye 1 na den a kupivlya lizh 10 Kozhen den vi mayete virishuvati chi prodovzhiti brati lizhi na prokat she na odin den abo kupiti paru lizh Yaksho vi znayete zazdalegid skilki dniv vi katatimetes na lizhah vi mozhete obrati variant z najmenshimi vitratami Napriklad yaksho vi budete katatisya protyagom bilshe nizh 10 dniv deshevshe bude kupiti lizhi ale yaksho vi katatimetes menshe nizh 10 dniv to deshevshe vzyati yih u prokat Yaksho vi katatimetes tochno 10 dniv vam bajduzhe Pitannya sho robiti koli vi ne znayete zazdalegid skilki dniv vi katatimetes Formalno zadacha mozhe buti postavlena takim chinom Ye chislo dniv d nevidome vam protyagom yakih vi budete katatisya na lizhah Mi shukayemo algoritm sho minimizuye vidnoshennya mizh sumoyu splachenoyu vikoristovuyuchi cej algoritm sho ne znaye d i sumoyu v najkrashomu vipadku yaksho vi znayete d napered Cya zadacha yak pravilo analizuyetsya u najgirshomu vipadku de algoritm fiksovanij i todi mi divimos na tochnist algoritmu u najgirshomu vipadku dlya vsih mozhlivih d Zokrema ne robit niyakih pripushen vidnosno vidnosno rozpodilu d i legko pobachiti sho zi znannyam rozpodilu d perevagu viddavalasya b inshomu analizu takozh yak inshim rozv yazkam Bezzbitkovij algoritmBezzbitkovij algoritm vkazuye brati u prokat protyagom 9 dniv i kupiti lizhi na ranok dnya 10 yaksho vi vse she gotovi katatisya Yaksho vi mayete pripiniti katatisya protyagom pershih 9 dniv ce koshtuye te same yaksho b vi znali chislo dniv protyagom yakih vi katatimetes Yaksho vi mayete zupinitis pislya 10 dnya vashi vitrati 19 sho stanovit 90 bilshe vid optimumu Ce najgirshij vipadok dlya bezzbitkovogo algoritmu Bezzbitkovij algoritm vidomij yak najkrashij deterministichnij algoritm dlya ciyeyi zadachi Div takozhPortal Matematika Onlajn algoritmPosilannyaSteven 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 veresnya 2006 u Wayback Machine Claire Mathieu Brown University Lecture note http www cs brown edu people claire skirental pdf 12 veresnya 2006 u Wayback Machine A R Karlin M Manasse L Rudolph and D Sleator Competitive snoopy caching Algorithmica 3 1 79 119 1988