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?
źródło
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ć:
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.
źródło
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.
źródło
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.
źródło