Jakiego algorytmu używają windy, aby znaleźć najkrótszą ścieżkę do zamówień na piętro?
On 15 lutego, 2021 by adminPróbuję zasymulować windę, jak zwykle zacząłem bardzo prosto, przyjmując tylko jedno zamówienie na raz, a następnie dodałem pamięć do windy w forma kolejek tak, aby podłogi były przemieszczane w kolejności, w jakiej zostały wciśnięte, co oczywiście nie jest najlepszym rozwiązaniem.
W tej chwili używam bardzo prostego i „krótkowzrocznego” logika, która polega na tym, że dla bieżącego piętra znajdź piętro najbliżej mnie i ustaw je jako następne miejsce docelowe i zapętlaj, aż na liście nie będzie więcej pięter.
Ale to nie zawsze działa, na przykład Winda znajdowała się na 3 piętrze w 5-piętrowym budynku i otrzymała zamówienia 4,5,2 najkrótsza ścieżka to 2-> 4-> 5, która kosztuje 4 piętra, ale używając tej logiki 4-> 5-> 2, która kosztuje 5 ma taka sama szansa na wybranie, w zależności od kodu.
Jak znaleźć najkrótszą ścieżkę i zwiększyć wydajność windy?
Komentarze
- Dość powiązane: programmers.stackexchange.com/q/96278/149904
- ' Chciałbym zaprosić cię do mojego biura i wymyślić algorytm, którego tam używają windy. Ponieważ absolutnie mogę ' t.
- @ gnasher729 Och, mogę, chociaż nie ' cię nie znam , ponieważ ' jest z pewnością tak samo jak w moim biurze: nigdy nie zatrzymuj się na piętrze, w którym ' m, chyba że już jest pełen ludzie. Mam rację?
- Niezupełnie. Istnieją cztery windy. Naciskasz przycisk, przez bardzo długi czas nic się nie rusza. Jeśli ktoś się poruszy, zatrzymuje się tuż przed twoją podłogą i czeka przez wieki, aż zostanie wyprzedzony przez inny, który minie twoją podłogę, a następnie spadnie. W drodze na ziemię zatrzymuje się co najmniej trzy razy i nikt nie wchodzi.
- Odpowiednia gra / wyzwanie programistyczne: play.elevatorsaga.com
Odpowiedź
„Wydajność” nie jest najważniejszą cechą, najważniejsze jest upewnienie się, że każda przestrzega się porządku, że nie ma głodu. Jeśli ktoś naciska 100, a ludzie wciąż naciskają 1 i 2, może być efektywne przechodzenie między tymi piętrami, ale byłoby miło, gdyby w pewnym momencie odwiedzono 100.
Myślę / em> (z osobistych obserwacji, gdy byłem zainteresowany ustaleniem), że większość z nich to robi:
- Zacznij iść w kierunku pierwszego naciśniętego przycisku, śledź, w którym kierunku jesteśmy idę
- Po osiągnięciu piętra i naciśnięciu tego przycisku zatrzymaj się i otwórz drzwi, zaznacz przyciski tego piętra jako nieużywane.
-
- Jeśli jest jeszcze więcej pięter, które musimy odwiedzić w tym samym kierunku, jedź dalej w tym kierunku .
- Jeśli nie, a są jeszcze piętra, które musimy odwiedzić, przejdź w tym kierunku.
- Jeśli nie, to skończymy i zaczniemy od 1 po ponownym naciśnięciu przycisku.
Uwaga że wiele wind ma przyciski „Chcę jechać w górę” i „Chcę zejść na dół” obok drzwi zamiast jednego przycisku. Algorytm wymaga tylko małej zmiany: w 2, jeśli jedynym przyciskiem wciśniętym dla tego piętra jest jeden z przycisków obok drzwi, zatrzymaj i otwórz drzwi tylko wtedy, gdy zmierzamy w tym kierunku. Prawdopodobnie trzymaj przycisk wciśnięty, jeśli drzwi są otwarte z powodu przycisku wciśniętego w windzie i jedzie w złym kierunku.
Nigdy nie musisz wymyślać całej ścieżki , tylko w którym kierunku pójść dalej.
Komentarze
- to całkowicie pominęło mi myśl, byłem tak skupiony na wydajności i zapomniałem, że inne rzeczy też są ważne . ' nadal nie jest skuteczny, aby powiedzieć od 2 do > 100 iz powrotem do 1, po prostu dlatego, że był w tym samym kierunku, ale w przynajmniej zapewnia brak głodu. i zupełnie nie na temat, być może dlatego ' często spotyka się dwie windy z taką logiką? co sprawia, że zastanawiam się, czy ' częściej spotyka się windy jadące w przeciwnym kierunku w danym momencie. w każdym razie ' nadal ciekawi mnie, jak znaleźć najkrótszą całą ścieżkę, ale to bardzo ładnie odpowiada na moje pytanie. Dziękuję.
- Zauważ, że kiedy już dotrzesz budynek o 100 piętrach, zazwyczaj będziesz mieć windy obsługujące tylko określony zakres pięter (np. 0-19, 20-39,…), a także windy ekspresowe, które obsługują tylko duże odległości (np. od 0 do 50, od 0 do 100 , Od 50 do 100, ale bez pięter pomiędzy nimi), więc aby dotrzeć do celu, może być konieczna zmiana windy. Możesz również mieć wiele wind na szyb, które oczywiście nie mogą się mijać.Zupełnie nie na temat: IIRC, pojawiło się pytanie o skuteczność przycisków strzałek w górę iw dół w witrynie User Experience , która była bardzo fascynująca.
- dzięki, nie ' tego nie wiedziałem. podział wydaje się dobrą strategią, jeśli jedna część psuje cały system, ' t, a także w celu rozłożenia obciążenia, co jest ważne dla mechanicznego zużycia. Zastanawiam się, czy te ekspresowe windy powstały z powodu logicznych niedociągnięć algorytmu windy Knutha '.
- Jedyna inna rzecz i ' d dodać jest to, że często mają ' domowe ' piętro, na które wracają, gdy nie są używane, może to być różne dla różnych wind, a może nawet zmieniać się w zależności od pory dnia i oczekiwanych wzorców użytkowania
- Mam tendencję do naciskania przycisku w górę / w dół pół losowo, niezależnie od tego, w którym kierunku m faktycznie podróżuję. W moim przypadku zawsze mam tylko jedno miejsce docelowe, więc winda zabiera mnie w to miejsce, niezależnie od tego, czy wybrałem w górę czy w dół. Podejrzewam, że gdybym wcisnął przycisk w dół, wybrał piętro nade mną, a potem piętro niżej, zanim winda ruszyłaby, zabrałbym mnie na piętro niżej, a nie na to, które pchnąłem jako pierwsze. Mogę się mylić, ' z pewnością przetestuję go następnym razem, gdy znajdę się w windzie.
Odpowiedź
Druga odpowiedź poprawnie podaje standardowy algorytm windy, który zasadniczo brzmi: „jedź w tym samym kierunku tak długo, jak to możliwe i rób każdy konieczny przystanek po drodze”.
Istnieją inne algorytmy windy. Weźmy na przykład pod uwagę budynek mieszkalny, w którym mieszkania stają się droższe w miarę wchodzenia na górę. Właściciele budynku mogą zdecydować się na zmodyfikowanie algorytmu windy tak, 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 jadą do 2, 5 i 10, winda jedzie do 10, potem 5, potem 2, wysadzając ludzi w kolejności płacenia czynszu. Ale oczywiście, gdy ludzie w wieku 10 lat opuszczają swoje mieszkanie, częściej będą musieli czekać dłużej, aby dostać się do lobby.
Jeśli szukasz wydajnego rozwiązania następnie opracuj miernik kosztów, zaimplementuj kilka różnych algorytmów i przeprowadź symulacje. Pamiętaj, aby mierzyć nie tylko średni koszt, ale także metryki, takie jak najdłuższy czas obsługi każdego żądania. Optymalizacja pod kątem niskich średnich może czasami deoptymalizować najgorszy przypadek, co jest złe.
Komentarze
- Wydaje się rzadkie (inne alogirthms)
Odpowiedź
Zauważ, ż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 wydajniejszy niż SCAN.
Komentarze
- Mówiąc tak zdecydowanie, czy masz doświadczenie zawodowe we wdrażaniu kodu wind? Szczególnie nowsze systemy wind? Ciekaw jestem, czy po 11 września w Nowym Jorku nadano wyższy priorytet wysyłaniu pasażerów na dół niż ich przywiezieniu.
- Wyprowadź pasażerów, a nie na dół. Często korzystam z windy na parkingu, gdzie trzecie piętro na piętrach od 1 do 6 to parter, więc do ucieczki najlepiej byłoby skorzystać z piętra 3.
Odpowiedź
Ta odpowiedź dotyczy bardziej zaawansowanego systemu kontroli przeznaczenia . W budynku z wieloma windami, gdzie ludzie wskazują, na które piętro chcą się udać, a system przypisuje im windę.
Pomysł jest dość prosty, teoretycznie wiesz, dokąd jadą wszyscy i każda winda. Więc możesz dla każdej windy obliczyć, kiedy jest spodziewany czas przyjazdu i jak bardzo spowolni pozostałe. Chciwie wybierz najszybszą windę.
Istnieją ograniczenia, takie jak grupy naciskające przycisk tylko raz i ludzie naciskający przycisk kilka razy.
Dodaj komentarz