Faire des choix n'est pas toujours chose aisée. On peut se tromper du tout au tout ou, au contraire, prendre des décisions qui s'avéreront optimales par la suite. L'incertitude vient du fait qu'au moment où nous nous décidons, nous ne pouvons pas savoir ce que le futur nous réserve. Sur quelles bases faire des choix, sachant que l'avenir est totalement incertain ? Les algorithmes en ligne (ou online algorithms en anglais), peu connus, sont une piste de réflexion. De manière très simplifiée, ce sont des algorithmes qui doivent accomplir des tâches, prendre des décisions, à partir d'informations qu'ils ne connaissent pas intégralement dès le début, mais qui seront dévoilées au fil de l'eau. Un point commun unit de nombreuses variantes de ce contexte : lorsque l'algorithme reçoit un « bout » des données, il doit prendre une décision irrévocable (une fois un choix fait, l'algorithme ne peut plus revenir dessus).
Louer ou acheter un vélo ? --------------------------
M. Chronos est réparateur ambulant de montres et de pendules. Son atelier se trouve dans une camionnette, avec laquelle il se déplace. Un jour, il arrive en ville et installe son outil de travail sur la place du marché, sur laquelle il peut rester le temps qu'il veut tant qu'il n'en bouge pas. Par contre, il est obligé de loger à la sortie de la ville. Chaque jour, il doit faire les trajets entre les deux lieux, assez éloignés. Il décide de se déplacer à vélo. Il a deux options : soit acheter un vélo à dix euros, soit en louer un pour un euro par jour. Le souci, c'est qu'il ne sait absolument pas combien de temps il va rester dans cette ville. Il décide que tant qu'il a des clients il reste. Si, un jour, il n'en a aucun, il partira (et n'aura alors plus besoin de vélo).
L'incertitude provient de la durée de son séjour. M. Chronos ne sait absolument pas combien de temps il va avoir besoin d'un vélo. Imaginons qu'il reste J jours. La meilleure décision à prendre, s'il connaît J à l'avance, est simple. Si J < 10, alors il est préférable de louer, ce qui coûte J euros. Si J = 10, louer ou acheter coûte dix euros. Si J ≥ 10, alors il faut acheter (dès le premier jour). Hélas, M. Chronos ne connaît J qu'à la fin du jour J, c'est-à-dire trop tard…
Voyons ce qu'il peut faire. Il décide de louer pendant dix jours, puis d'acheter le jour 11 (il n'aura donc plus besoin de louer ensuite). Cela va lui coûter, en tout, 10 + 10 = 20 euros si J ≥ 11 et J euros sinon.