Quel algorithme est utilisé par les ascenseurs pour trouver le chemin le plus court pour les commandes de plancher de voyage?

27

J'essaie de simuler un ascenseur, comme toujours j'ai commencé très simplement en ne prenant qu'une seule commande à la fois, puis j'ai ajouté de la mémoire à l'ascenseur sous forme de files d'attente afin que les étages soient parcourus dans l'ordre dans lequel ils ont été pressés, ce qui n'est évidemment pas la meilleure approche.

Donc, pour le moment, j'utilise une logique très simple et à courte vue qui, pour l'étage actuel, trouve l'étage le plus proche de moi et le définit comme ma prochaine destination et boucle jusqu'à ce qu'il n'y ait plus d'étages dans la liste.

Mais cela ne fonctionne pas toujours, par exemple l'ascenseur était au 3ème étage d'un immeuble de 5 étages et a reçu des commandes 4,5,2 le chemin le plus court serait 2-> 4-> 5 qui coûte 4 étages mais en utilisant cette logique 4-> 5-> 2 qui coûte 5 a la même chance d'être choisi, selon le code.

Comment trouver le chemin le plus court et rendre l'ascenseur plus efficace?

Raed Tabani
la source
6
Je voudrais vous inviter à mon bureau et découvrir l'algorithme utilisé par les ascenseurs. Parce que je ne peux absolument pas.
gnasher729
1
@ gnasher729 Oh, je peux même si je ne vous connais pas, car c'est sûrement la même chose que dans mon bureau: ne vous arrêtez jamais à l'étage où je suis, sauf quand il est déjà plein de monde. Ai-je raison?
Andres F.
2
Pas assez. Il y a quatre ascenseurs. Vous appuyez sur le bouton, rien ne bouge pendant très longtemps. Si quelqu'un bouge, il s'arrête juste avant votre étage et attend pendant des siècles, jusqu'à ce qu'il soit dépassé par un autre qui passe devant votre étage puis redescend. Sur le chemin du sol, il s'arrête au moins trois fois sans que personne n'y entre.
gnasher729
2
Jeu de programmation / défi pertinent
dwikle

Réponses:

30

"L'efficacité" n'est pas la caractéristique la plus importante, la plus importante est de s'assurer que chaque commande est suivie, qu'il n'y a pas de famine. Si quelqu'un appuie sur 100 et que les gens continuent d'appuyer sur 1 et 2, il peut être efficace de continuer entre ces étages, mais ce serait bien que 100 soient visités à un moment donné.

Je pense (d'après une observation personnelle lorsque j'étais intéressé à comprendre) que la plupart d'entre eux le font:

  1. Commencez à aller dans la direction du premier bouton enfoncé, gardez une trace de la direction dans laquelle nous allons
  2. Lorsqu'un étage est atteint et que ce bouton a été enfoncé, arrêtez et ouvrez les portes, marquez les boutons de cet étage comme n'étant plus enfoncés.
    • S'il y a encore plus d'étages que nous devons visiter qui sont dans la même direction, continuez dans cette direction .
    • Sinon et il y a encore des étages que nous devons visiter, allez dans cette direction.
    • Si ce n'est pas le cas, nous avons terminé et commencerons à 1 lorsque vous appuyez à nouveau sur un bouton.

Notez que de nombreux ascenseurs ont des boutons "Je veux monter" et "Je veux descendre" à côté des portes au lieu d'un seul bouton. L'algorithme n'a besoin que d'un petit changement: en 2, si le seul bouton pressé pour cet étage est l'un des boutons à côté de la porte, arrêtez et ouvrez les portes seulement si nous allons dans cette direction. Peut-être maintenez le bouton enfoncé si les portes s'ouvrent à cause d'un bouton enfoncé à l'intérieur de l'ascenseur et qu'il va dans la mauvaise direction.

Vous n'avez jamais à trouver un chemin complet , juste dans quelle direction aller ensuite.

RemcoGerlich
la source
cela m'a complètement évité, j'étais tellement concentré sur l'efficacité et j'ai oublié que d'autres choses sont importantes aussi. ce n'est toujours pas efficace d'aller de 2 à> 100 et de revenir à 1 simplement parce que c'était dans le même sens mais au moins ça n'assure pas de famine. et, complètement hors sujet, c'est peut-être pourquoi il est courant de trouver deux ascenseurs avec cette logique? ce qui me fait me demander s'il est plus courant de trouver les ascenseurs allant dans la direction opposée à un moment donné. Quoi qu'il en soit, je suis toujours curieux de savoir comment trouver le chemin le plus court, mais cela répond très bien à ma question, merci
Raed Tabani
7
Notez qu'une fois que vous arrivez à un immeuble de 100 étages, vous aurez généralement des ascenseurs desservant uniquement une gamme spécifique d'étages (par exemple 0-19, 20-39,…), ainsi que des ascenseurs express qui ne parcourent que de longues distances (par exemple 0 à 50, 0 à 100, 50 à 100, mais aucun étage entre les deux), vous devrez donc peut-être changer d'ascenseur pour arriver à destination. Vous pouvez également avoir plusieurs ascenseurs par puits qui ne peuvent évidemment pas se croiser. Totalement hors sujet: IIRC, il y avait une question sur l'efficacité de ces boutons fléchés haut et bas sur le site User Experience qui rendait la lecture très fascinante.
Jörg W Mittag
merci, je ne le savais pas. la subdivision semble être une bonne stratégie si une partie ne détruit pas tout le système et également pour répartir la charge qui est importante pour l'usure mécanique. Je me demande si ces ascenseurs express sont dus aux défauts logiques de l'algorithme de Knuth's Elevator.
Raed Tabani
La seule autre chose que j'ajouterais, c'est que souvent, ils ont un étage `` à la maison '' où ils reviendront lorsqu'ils ne seront pas utilisés, cela peut être différent pour différents ascenseurs, et peut-être même changer en fonction de l'heure de la journée et des modèles d'utilisation prévus
JK .
J'ai tendance à appuyer sur le bouton haut / bas de façon semi-aléatoire, quelle que soit la direction dans laquelle je voyage. Dans mon cas, je n'ai qu'une seule destination, donc l'ascenseur m'emmène à cet endroit, que je choisisse ou non vers le bas. Je soupçonne que si je devais appuyer sur le bouton vers le bas, choisir un étage au-dessus de moi, puis choisir un étage en dessous de moi avant que l'ascenseur ne commence à bouger, cela m'amènerait à l'étage en dessous de moi plutôt qu'à l'étage que j'ai poussé en premier. Je peux me tromper, je vais être sûr de le tester la prochaine fois que je me retrouve dans un ascenseur.
Ucenna
13

L'autre réponse donne correctement l'algorithme d'ascenseur standard, qui est fondamentalement "continuez dans la même direction aussi longtemps que possible et faites chaque arrêt nécessaire en cours de route".

Il existe d'autres algorithmes d'ascenseur. Par exemple, considérons un immeuble d'appartements où les appartements deviennent plus chers à mesure que vous montez. Les propriétaires de l'immeuble pourraient choisir de modifier l'algorithme de l'ascenseur pour "aller dans la même direction le plus longtemps possible mais ne s'arrêter qu'en descendant". De cette façon, si vous avez des personnes dans l'ascenseur qui sont dans le hall et vont au 2, 5 et 10, l'ascenseur passe à 10, puis 5, puis 2, déposant les gens par ordre de loyer. Mais bien sûr, lorsque les personnes sur 10 quittent leur appartement, elles devront plus souvent attendre plus longtemps pour se rendre dans le hall.

Si vous recherchez une solution efficace, proposez une mesure du coût et implémentez un ensemble d'algorithmes différents, puis exécutez des simulations. N'oubliez pas de mesurer non seulement le coût moyen, mais également les mesures comme la plus longue demande de traitement d'une demande. L'optimisation pour des moyennes faibles peut parfois désoptimiser le pire des cas, ce qui est mauvais.

Eric Lippert
la source
1
Il semble être rare (autres alogirthms)
FindOutIslamNow
10

Notez que les ascenseurs utilisent les mêmes algorithmes de planification que certains contrôleurs de disque dur. L'algorithme SCAN standard est même connu sous le nom d' algorithme d'ascenseur . Je pense qu'en pratique, l' algorithme LOOK est plus courant, car il est légèrement plus efficace que SCAN.

gardenhead
la source
Lorsque vous parlez si certainement, avez-vous une expérience professionnelle dans la mise en œuvre du code des ascenseurs? Systèmes d'ascenseurs particulièrement récents? Je suis curieux de savoir si après le 11 septembre à New York, il y a eu une priorité plus élevée à l'envoi de passagers par rapport à leur remontée.
John Zabroski