Quel algorithme sont utilisés par les ascenseurs pour trouver le chemin le plus court pour parcourir les commandes détage?
On février 15, 2021 by adminJessaye de simuler un ascenseur, comme toujours jai commencé très simple en ne prenant quune seule commande à la fois, puis jai ajouté de la mémoire à lascenseur en la forme de files dattente pour que les étages soient parcourus dans lordre dans lequel ils ont été pressés, ce qui nest évidemment pas la meilleure approche.
Donc, pour le moment, jutilise un moyen très simple et « à courte vue » logique qui est, pour létage actuel, trouvez létage le plus proche de moi et définissez-le comme ma prochaine destination et faites une boucle jusquà ce quil ny ait plus détages dans la liste.
Mais cela ne fonctionne pas toujours, par exemple lascenseur était au 3ème étage dun 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 sélectionné, selon le code.
Comment trouver le chemin le plus court et rendre lascenseur plus efficace?
Commentaires
- Assez lié: programmers.stackexchange.com/q/96278/149904
- Je ‘ aimerais vous inviter à mon bureau et découvrir lalgorithme utilisé par les ascenseurs. Parce que je peux absolument ‘ t.
- @ gnasher729 Oh, je peux même si je ne ‘ ne vous connais pas , parce que ‘ est sûrement le même que dans mon bureau: ne vous arrêtez jamais à létage où je ‘ m dedans, sauf quand il est déjà plein de gens. Ai-je raison?
- Pas tout à fait. Il y a quatre ascenseurs. Vous appuyez sur le bouton, rien ne bouge pendant très longtemps. Si lon bouge, il sarrête juste avant votre sol et attend des siècles, jusquà ce quil soit dépassé par un autre qui dépasse votre sol puis redescend. En descendant vers le sol, il sarrête au moins trois fois sans que personne nentre.
- Jeu / défi de programmation pertinent: play.elevatorsaga.com
Réponse
« Lefficacité » nest pas la caractéristique la plus importante, le plus important est de sassurer que chaque lordre est suivi, quil ny a pas de famine. Si quelquun appuie sur 100 et que les gens continuent dappuyer sur 1 et 2, il peut être efficace de continuer entre ces étages, mais ce serait bien que 100 soit visité à un moment donné.
Je pense (daprès une observation personnelle quand jétais intéressé à comprendre) que la plupart dentre eux font:
- Commencez à aller dans la direction du premier bouton enfoncé, gardez une trace de la direction dans laquelle nous « re en cours
- Lorsquun é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.
-
- Si il y a encore dautres étages que nous devons visiter et qui sont dans la même direction, continuez dans cette direction .
- Sinon et il y a encore des étages que nous devons visiter, déplacez-vous dans cette direction.
- Sinon, nous avons terminé et commencerons à 1 lorsquun bouton sera à nouveau enfoncé.
Remarque que de nombreux ascenseurs ont des boutons «Je veux monter» et «Je veux descendre» à côté des portes au lieu dun seul bouton. Lalgorithme na besoin que dun petit changement: en 2, si le seul bouton enfoncé pour cet étage est lun des boutons à côté de la porte, arrêtez et ouvrez les portes uniquement si nous allons dans cette direction. Maintenez éventuellement le bouton enfoncé si les portes souvrent à cause dun bouton enfoncé à lintérieur de lascenseur et que celui-ci va dans la mauvaise direction.
Vous navez jamais à trouver un chemin complet, juste dans quelle direction aller.
Commentaires
- cela ma complètement sauté lesprit, jétais tellement concentré sur lefficacité et jai oublié que dautres choses sont importantes aussi . il ‘ nest toujours pas efficace daller dire de 2- > 100 et de revenir à 1 simplement parce que cétait dans le même sens mais à au moins, il nassure aucune famine. et, complètement hors sujet, est-ce peut-être pourquoi il ‘ est commun de trouver deux ascenseurs avec cette logique? ce qui me fait me demander sil est ‘ plus courant de trouver les ascenseurs allant dans la direction opposée à un moment donné. de toute façon, je ‘ je suis toujours curieux de savoir comment trouver le chemin complet le plus court, mais cela répond parfaitement à ma question, merci
- Notez quune fois que vous arrivez à dans un bâtiment de 100 étages, vous disposerez généralement dascenseurs desservant uniquement une plage détages spécifique (par exemple 0-19, 20-39,…), ainsi que dascenseurs express qui ne parcourent que de longues distances (par exemple 0 à 50, 0 à 100 , 50 à 100, mais pas détages entre les deux), vous devrez peut-être changer dascenseur pour vous rendre à 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 lefficacité de ces boutons fléchés vers le haut et vers le bas sur le site Expérience utilisateur qui a rendu la lecture très fascinante.
- merci, je ne ‘ pas le savoir. la subdivision semble être une bonne stratégie si une pièce brise le système entier ‘ t et aussi pour répartir la charge qui est importante pour lusure mécanique. Je me demandais si ces ascenseurs express étaient dus aux lacunes logiques de lalgorithme des ascenseurs de Knuth ‘.
- autre chose seulement ‘ d ajouter est que souvent ils ont un étage ‘ domicile ‘ auquel ils reviendront lorsquils ne seront pas utilisés, cela peut être différent pour différents ascenseurs, et peut-être même changer en fonction de lheure de la journée et des modes dutilisation prévus
- Jai tendance à appuyer sur le bouton haut / bas de manière semi-aléatoire quelle que soit la direction I ‘ Je voyage en fait. Dans mon cas, je nai jamais quune seule destination, donc lascenseur memmène à cet endroit, que jaie choisi de monter ou de descendre. Je soupçonne que si je devais appuyer sur le bouton bas, choisir un étage au-dessus de moi, puis choisir un étage en dessous de moi avant que lascenseur ne commence à bouger, cela mamènerait à létage en dessous de moi plutôt quau plancher que jai poussé en premier. Je peux me tromper, ‘ je ne manquerai pas de le tester la prochaine fois que je me trouverai dans un ascenseur.
Réponse
Lautre réponse donne correctement lalgorithme dascenseur standard, qui est essentiellement « continuez dans la même direction le plus longtemps possible et faites tous les arrêts nécessaires en cours de route ».
Il existe dautres algorithmes dascenseur. Par exemple, considérons un immeuble dappartements où les appartements deviennent plus chers à mesure que vous montez. Les propriétaires du bâtiment peuvent choisir de modifier lalgorithme de lascenseur pour «aller dans la même direction le plus longtemps possible mais ne sarrêter quen descendant». De cette façon, si vous avez des gens dans lascenseur qui sont dans le hall et qui vont à 2, 5 et 10, lascenseur passe à 10, puis 5, puis 2, déposant les gens par ordre de loyer quils paient. 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 cherchez une solution efficace puis trouvez une métrique pour le coût et implémentez un tas dalgorithmes différents, et exécutez des simulations. Noubliez pas de mesurer non seulement le coût moyen, mais également des mesures telles que la durée la plus longue pour quune demande soit traitée. Loptimisation pour des moyennes faibles peut parfois désoptimiser le pire des cas, ce qui est mauvais.
Commentaires
- Cela semble être rare (autres naissances)
Réponse
Notez que les ascenseurs utilisent les mêmes algorithmes de planification que certains contrôleurs de disque dur. Lalgorithme SCAN standard est même connu sous le nom dalgorithme dascenseur . Je pense quen pratique, lalgorithme LOOK est plus courant, car il est légèrement plus efficace que SCAN.
Commentaires
- Quand vous parlez si certainement, avez-vous une expérience professionnelle dans la mise en œuvre du code pour les ascenseurs? Surtout les nouveaux systèmes dascenseur? Je suis curieux de savoir si, après le 11 septembre à New York, il y a eu une plus grande priorité pour envoyer les passagers vers le bas plutôt que pour les faire monter.
- Faites sortir les passagers, pas descendre. Jutilise souvent lascenseur dans un parking, où le troisième étage des étages 1 à 6 est le rez-de-chaussée, donc pour méchapper, létage 3 serait le meilleur.
Réponse
Cette réponse concerne un système de contrôle de destination plus avancé . Dans un bâtiment avec plusieurs ascenseurs où les gens indiquent à quel étage ils veulent aller et le système leur attribue un ascenseur.
Lidée est assez simple, en théorie, vous savez où tout le monde et chaque ascenseur vont. Vous pouvez donc pour chaque ascenseur, calculer votre heure darrivée prévue et à quel point cela ralentira les autres. Choisissez avec avidité lascenseur le plus rapide.
Il y a des limitations à cela, telles que les groupes nappuyant quune seule fois sur le bouton et les personnes appuyant sur le bouton plusieurs fois.
Laisser un commentaire