Ich versuche den besten Algorithmus für das folgende Sortierproblem zu finden.
Es gibt N = K × M Sitze in einem Auditorium mit einem Gang, K Reihen und M Sitzen pro Gang. Es wird angenommen, dass K größer ist als M , aber das halte ich nicht für sehr wichtig. Es gibt N Leute, die drin sind Bijektion mit den Sitzen (zugewiesene Sitze). Angenommen, die Leute nicht Wie warte ich, was ist der schnellste Weg, sie aufzustellen, um sie alle zu bekommen? so schnell wie möglich in ihren Sitzen?
Ich habe einige einfache Experimente (mit zufälligen Permutationen) und es durchgeführt Es schien, dass es zufälliger ist, sie sich in einer zufälligen Reihenfolge aufstellen zu lassen die Leute im vorderen Drittel (weiter hinten am Gang) reihen sich zuerst an das mittlere Drittel, dann das hintere Drittel. Das scheint mir falsch zu sein.
Ich schreibe das in MatLab, wenn das überhaupt wichtig ist. Irgendwelche Ideen oder Antworten?
Es gibt einen sehr schönen Artikel von Bachmat, Berend, Sapir, Skiena und Stolyarov mit dem Titel Analyse von Flugzeug-Boarding über Raum-Zeit-Geometrie und Random-Matrix-Theorie , die genau dieses Problem für das Flugzeug-Boarding abbildet. Aus ihrer Zusammenfassung:
Wir zeigen, dass Flugzeug-Boarding sein kann asymptotisch modelliert von 2-dimensionale Lorentzsche Geometrie. Boarding-Zeit ist durch die maximale gegeben richtige Zeit zwischen den Kurven im Modell. Diskrepanzen zwischen dem Modell und Simulationsergebnisse sind eng miteinander verwandt zur Random-Matrix-Theorie. Wir zeigen es dann wie solche Modelle zur Erklärung verwendet werden können warum einige häufig praktizierte Fluggesellschaft Boarding-Richtlinien sind ineffektiv und sogar nachteilig.
Die Schlussfolgerungen des Papiers sind:
Für Ihre Einrichtung bedeutet das, dass Sie ignorieren sollten, wie weit die Leute gehen, und konzentrieren Sie sich stattdessen auf wie weit vom Gang sie sind. Dieses Modell berücksichtigt auch die Zeit, um Gepäck zu verstauen, also müssen Sie das vielleicht etwas für Ihre Situation anpassen. Auf jeden Fall bestätige ich, was Sie durch Ihr Modell herausfinden.
Tags und Links algorithm permutation matlab sorting