Problème de la location de skis
From Wikipedia, the free encyclopedia
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].
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.
