Algorithme de Karp : Ascenseurs et algorithmes | Le jeu des sciences

Notre ascenseur à balles de la semaine dernière ne devrait pas, pour le bien de ses occupants, accélérer à 10 m/s² avant la moitié de son trajet et, par conséquent, la réponse du deuxième visiteur est très raisonnable, car, comme le souligne Marina Puente :

« La décélération ne peut pas être supérieure à la gravité (9,8 m/s²) car les passagers perdraient le contact avec le plancher de l’ascenseur. Par conséquent, la vitesse maximale doit être atteinte avant le plancher de 100″.

Quant à l’ascenseur Gamow, à première vue, il semble que même s’il y a plus d’un ascenseur, la probabilité que le premier ascenseur qui s’arrête au 2ème étage descende est toujours de 5/6, puisque c’est la probabilité pour chaque individu. ascenseur et peu importe que vous utilisiez l’un ou l’autre. En fait, Gamow lui-même était confus au début. Mais Donald E. Knuth s’est rendu compte que, contre-intuitivement, s’il y a plusieurs ascenseurs, les choses changent, et il a analysé la situation en profondeur dans son article de 1979, The Gamow-Stern Elevator Problem. Les choses changent tellement que, lorsque le nombre d’ascenseurs tend vers l’infini, la probabilité tend vers 1/2, comme plusieurs lecteurs l’ont déduit (voir commentaires de la semaine dernière).

Concernant le problème de l’immeuble de cinq étages avec un seul ascenseur et pouvant accueillir deux personnes, Francisco Montesinos et Salva Fuster s’accordent sur la recherche d’un itinéraire minimum de 18 unités, qui dit :

« Je suis d’accord avec l’argument selon lequel un trajet de moins de 14 unités est impossible. Comme Francisco, j’ai également réalisé un parcours de 18 unités et je crois que 18 est le minimum réalisable. Pour le voir, je pense qu’il est pratique de diviser chaque mouvement à réaliser en segments unitaires dirigés (je laisse le schéma dans l’image ci-jointe). Chaque paire de segments entre deux étages adjacents peut être réalisée en un seul mouvement de 1 unité (2 unités si l’on compte dans les deux sens), mais compte tenu de l'(im)parité des segments, dans une partie des itinéraires nous ne pourrons que pour rapprocher une seule personne de sa destination (en particulier, cela se produira à 8 reprises).

L’algorithme de Karp

Le prestigieux informaticien Richard M. Karp, qui a reçu en 1985 le prix Turing pour ses contributions à la théorie des algorithmes et à la résolution des problèmes d’optimisation combinatoire, a conçu une procédure simple pour résoudre une généralisation du problème précédent :

1. Lorsque l’ascenseur monte, si quelqu’un (soit dans l’ascenseur, soit à l’étage où il vient de s’arrêter) veut monter, l’ascenseur est chargé des personnes ayant la destination la plus élevée, et tous les autres restent à cet étage, et puis l’ascenseur monte d’un étage. Si personne ne veut monter, l’ascenseur descend.
2. Lorsque l’ascenseur descend, il est chargé des personnes de la destination la plus basse (qu’elles soient déjà dans l’ascenseur ou à l’étage où il vient de s’arrêter) et l’ascenseur descend d’un étage. Si personne ne veut descendre, l’ascenseur monte.

J’invite mes lecteurs avisés à reconsidérer le problème des cinq étages en relation avec l’algorithme de Karp, et à rechercher d’éventuelles généralisations ou variantes de ce problème et des autres problèmes d’ascenseur vus récemment.

Vous pouvez suivre MATÉRIEL dans Facebook, X e Instagramcliquez ici pour recevoir notre newsletter hebdomadaire.