Problème de la location de skis
En informatique, le problème de la location de skis est un problème algorithmique qui modélise la prise de décisions sans connaissance sur le futur, et en particulier de la décision location VS achat présent dans les algorithmes online[1].
Description du problème
Un skieur part faire du ski pour un nombre inconnu de jours (le nombre de jours est inconnu car peut-être il va se casser une jambe, ou va devoir rentrer à cause d'une urgence familiale, etc.). Chaque jour, il doit décider s'il loue ses skis à 1€ par jour ou alors s'il achète ses skis une fois pour toutes à 10 €.
S'il reste strictement moins de 10 jours, il est plus avantageux de louer. S'il reste 10 jours ou plus, il vaut mieux les acheter. C'est l'algorithme offline. Le problème est de faire le bon choix sans connaître le nombre de jours, autrement dit on s'intéresse à un algorithme online.
Meilleur algorithme online déterministe
Le meilleur algorithme online déterministe est de louer les 9 premier jours, puis d'acheter le jour n° 10. Si le séjour est de 10 jours, l'algorithme online déterministe paie 9€ + 10€ au lieu de 10€ pour l'algorithme offline. Dans le cas général, où le prix d'achat est b, on paie 2b - 1 au lieu de b. On a (2b - 1)/b majoré par 2. Le ratio compétitif majoré par 2 -- c'est le rapport entre les performances de l'algorithme online et de l'algorithme offline.
Meilleur algorithme online aléatoire
L'idée de l'algorithme consiste à choisir le jour au hasard à partir duquel on décide d'acheter. Ce jour i est choisi selon une loi de probabilité entre le premier jour et le jour n° 10. L'algorithme décrit par Karlin et al.[1] consiste à choisir le jour i avec la probabilité où b est le prix de l'achat. Le ratio compétitif est alors défini comme une espérance. Le ratio compétitif est de e(e-1) 1.58 fois plus que l'algorithme offline qui connait le nombre de jours passés.
Extensions
Le problème a été généralisé à plusieurs options dans un magasin[2] ou plusieurs magasins[3].
Notes et références
- ↑ a et b (en) « Competitive randomized algorithms for non-uniform problems | Proceedings of the first annual ACM-SIAM symposium on Discrete algorithms », sur dl.acm.org (DOI 10.5555/320176.320216, consulté le )
- ↑ Zvi Lotker, Boaz Patt-shamir et Dror Rawitz, Rent, Lease or Buy: Randomized Algorithms for Multislope Ski Rental, (lire en ligne)
- ↑ (en) « The multi-shop ski rental problem | The 2014 ACM international conference on Measurement and modeling of computer systems », sur dl.acm.org (DOI 10.1145/2591971.2591984, consulté le )
Portail de l'informatique théorique