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[modifier | modifier le code]

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[modifier | modifier le code]

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[modifier | modifier le code]

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é $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.,$ 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) $\approx$ 1.58 fois plus que l'algorithme offline qui connait le nombre de jours passés.

Extensions[modifier | modifier le code]

Le problème a été généralisé à plusieurs options dans un magasin^[2] ou plusieurs magasins^[3].

Notes et références[modifier | modifier le code]

↑ ^{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 23 février 2020)
↑ Zvi Lotker, Boaz Patt-shamir et Dror Rawitz, Rent, Lease or Buy: Randomized Algorithms for Multislope Ski Rental, 2008 (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 23 février 2020)

Portail de l'informatique théorique

[:0-1] {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 23 février 2020)

[2] Zvi Lotker, Boaz Patt-shamir et Dror Rawitz, Rent, Lease or Buy: Randomized Algorithms for Multislope Ski Rental, 2008 (lire en ligne)

[3] (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 23 février 2020)

[1]

[2]

[3]