Jakiego algorytmu używają windy, aby znaleźć najkrótszą ścieżkę do zamówień piętra podróży?

Staram się symulować windę, jak zawsze zacząłem bardzo prosto, biorąc tylko jedno zamówienie na raz, a następnie dodałem pamięć do windy w postaci kolejek, aby piętra były przemieszczane w kolejności, w której zostały wciśnięte, co oczywiście nie jest najlepszym podejściem.

Więc w tej chwili używam bardzo prostej i „krótkowzrocznej” logiki, która polega na tym, że dla bieżącej podłogi znajdź podłogę najbliżej mnie i ustaw ją jako mój następny cel i zapętlaj ją, dopóki na liście nie będzie już więcej pięter.

Ale to nie zawsze działa, na przykład winda znajdowała się na 3 piętrze pięciopiętrowego budynku i otrzymała zamówienia 4,5,2, najkrótsza ścieżka to 2-> 4-> 5, która kosztuje 4 piętra, ale przy użyciu tej logiki 4-> 5-> 2, która kosztuje 5, ma taką samą szansę na wybranie, w zależności od kodu.

Jak znaleźć najkrótszą ścieżkę i zwiększyć wydajność windy?

— Raed Tabani
źródło

Nieco powiązane: programmers.stackexchange.com/q/96278/149904

— manlio

Chciałbym zaprosić cię do mojego biura i wymyślić algorytm, z którego korzystają tam windy. Ponieważ absolutnie nie mogę.

— gnasher729,

@ gnasher729 Och, mogę, mimo że cię nie znam, bo to na pewno to samo, co w moim biurze: nigdy nie zatrzymuj się na podłodze, na której się znajduję, chyba że jestem już pełen ludzi. Czy mam rację?

— Andres F.,

Nie do końca. Istnieją cztery windy. Naciskasz przycisk, przez długi czas nic się nie rusza. Jeśli jeden się poruszy, zatrzymuje się tuż przed podłogą i czeka przez wieki, dopóki nie zostanie wyprzedzony przez inny, który mija podłogę, a następnie opada. W drodze na ziemię zatrzymuje się co najmniej trzy razy i nikt nie wchodzi.

— gnasher729,

Odpowiednia gra programistyczna / wyzwanie: play.elevatorsaga.com

— dwikle 27.09.16

Odpowiedzi:

„Wydajność” nie jest najważniejszą cechą, najważniejsze jest upewnienie się, że każde zamówienie jest przestrzegane, aby nie było głodu. Jeśli ktoś naciśnie 100, a ludzie będą naciskać 1 i 2, może być skuteczne przechodzenie między tymi piętrami, ale byłoby miło, gdyby w pewnym momencie odwiedzono 100.

I pomyśleć (z osobistej obserwacji, kiedy był zainteresowany zastanawianie się), że większość z nich zrobić:

Zacznij iść w kierunku pierwszego naciśniętego przycisku, śledź kierunek, w którym zmierzamy
Po osiągnięciu podłogi i naciśnięciu tego przycisku zatrzymaj i otwórz drzwi, zaznacz przyciski tej podłogi jako już nie naciśnięte.
- Jeśli jest jeszcze więcej pięter, które musimy odwiedzić, są w tym samym kierunku, idź dalej w tym kierunku .
- Jeśli nie i nadal są podłogi, które musimy odwiedzić, idź w tym kierunku.
- Jeśli nie, to skończymy i zaczniemy od 1 po ponownym naciśnięciu przycisku.

Zauważ, że wiele wind ma przyciski „Chcę wejść” i „Chcę zejść” obok drzwi zamiast jednego przycisku. Algorytm wymaga tylko niewielkiej zmiany: w 2, jeśli jedynym przyciskiem naciśniętym dla tej podłogi jest jeden z przycisków obok drzwi, zatrzymaj się i otwórz drzwi, jeśli idziemy w tym kierunku. Prawdopodobnie trzymaj wciśnięty przycisk, jeśli drzwi są otwarte z powodu przycisku wciśniętego w windzie i idzie w złym kierunku.

Nigdy nie musisz wymyślać całej ścieżki , tylko w którym kierunku iść dalej.

— RemcoGerlich
źródło

to całkowicie pomijało mój umysł, byłem tak skoncentrowany na wydajności i zapomniałem, że inne rzeczy też są ważne. nadal nie jest efektywne przejście z 2 na> 100 i powrót do 1 tylko dlatego, że było w tym samym kierunku, ale przynajmniej nie zapewnia głodu. i zupełnie nie na temat, być może dlatego często spotykamy dwie windy z tą logiką? co sprawia, że zastanawiam się, czy bardziej powszechne jest znajdowanie wind poruszających się w przeciwnym kierunku w danym momencie. tak czy inaczej, wciąż jestem ciekawy, jak znaleźć najkrótszą całą ścieżkę, ale to bardzo trafnie odpowiada na moje pytanie, dzięki

— Raed Tabani

Pamiętaj, że po dotarciu do budynku ze 100 piętrami zwykle masz windy obsługujące tylko określony zakres pięter (np. 0–19, 20–39,…), a także windy ekspresowe, które pokonują duże odległości (np. 0 do 50, 0 do 100, 50 do 100, ale brak pięter pomiędzy), więc może być konieczna zmiana wind, aby dostać się do miejsca docelowego. Możesz również mieć wiele wind na wał, które oczywiście nie mogą się przejechać. Zupełnie nie na temat: IIRC pojawiło się pytanie o skuteczność tych przycisków ze strzałkami w górę i w dół na stronie User Experience, które stworzyły bardzo fascynującą lekturę.

— Jörg W Mittag

dzięki, nie wiedziałem tego. dzielenie wydaje się dobrą strategią, jeśli jedna część psuje cały system, a nie rozkłada obciążenia, które jest ważne dla zużycia mechanicznego. Zastanawiam się, czy te ekspresowe windy powstały z powodu logicznych niedociągnięć algorytmu Knuth's Elevator.

— Raed Tabani,

jedyną rzeczą, którą dodam, jest to, że często mają podłogę „domową”, do której powrócą, gdy nie będą używane, może być różna dla różnych wind, a być może nawet zmieniać się w zależności od pory dnia i oczekiwanych wzorców użytkowania

— jk .

Mam tendencję do naciskania przycisku góra / dół częściowo losowo, niezależnie od tego, w którym kierunku faktycznie podróżuję. W moim przypadku mam tylko jeden cel, więc winda zabiera mnie do tego miejsca, niezależnie od tego, czy wybrałem na dół. Podejrzewam, że gdybym wcisnął przycisk w dół, wybrał piętro nad sobą, a następnie piętro pode mną, zanim winda zacznie się poruszać, zabrałoby mnie to na podłogę pode mnie, a nie na podłogę, którą najpierw pchnąłem. Mogę się mylić, z pewnością przetestuję to następnym razem, gdy znajdę się w windzie.

— Ucenna

Druga odpowiedź poprawnie podaje standardowy algorytm windy, który w zasadzie „kontynuuj jazdę w tym samym kierunku tak długo, jak to możliwe i zatrzymuj się po drodze”.

Istnieją inne algorytmy windy. Weźmy na przykład budynek mieszkalny, w którym mieszkania stają się droższe w miarę wchodzenia. Właściciele budynku mogą zmodyfikować algorytm windy, aby „jechał w tym samym kierunku tak długo, jak to możliwe, ale zatrzymywał się tylko w drodze w dół”. W ten sposób, jeśli masz ludzi w windzie, którzy są w holu i idą do 2, 5 i 10, winda jedzie do 10, następnie 5, a następnie 2, wysadzając ludzi w kolejności, ile płacą czynsz. Ale oczywiście, gdy osoby w wieku 10 lat opuszczają swoje mieszkanie, częściej będą musiały czekać dłużej, aby dostać się do lobby.

Jeśli szukasz wydajnego rozwiązania, opracuj metrykę kosztu, zaimplementuj kilka różnych algorytmów i uruchom symulacje. Pamiętaj, aby mierzyć nie tylko średni koszt, ale także mierniki, takie jak najdłuższy czas potrzebny na obsługę dowolnego żądania. Optymalizacja pod kątem średnich średnich może czasem dezoptymalizować najgorszy przypadek, który jest zły.

— Eric Lippert
źródło

Wydaje się być rzadkie (inne alogirthms)

— FindOutIslamNow

Należy pamiętać, że windy używają tych samych algorytmów planowania, co niektóre kontrolery dysków twardych. Standardowy algorytm SCAN jest nawet znany jako algorytm windy . Myślę, że w praktyce algorytm LOOK jest bardziej powszechny, ponieważ jest nieco bardziej wydajny niż SCAN.

— ogrodnik
źródło

Czy kiedy mówisz tak pewnie, masz doświadczenie zawodowe we wdrażaniu kodu do wind? Zwłaszcza nowsze systemy wind? Jestem ciekawy, czy po 11 września w Nowym Jorku wyższy priorytet miał wysyłanie pasażerów niż ich wychowywanie.

— John Zabroski