我正在嘗試爲以下排序問題找到最佳算法。什麼是最好的預留座位排序算法？
有Ñ= K×M座椅與一個過道禮堂，ķ行，並且每過道中號座位。假定K是一個大於M，但我不認爲這是非常重要的。有N人在 與座位（指定座位）的雙向注視。假設人們不會像 那樣等待，那麼最快的方法是將他們排列在儘可能快的位置，以便讓他們全部坐在他們的座位上 ？
我進行了一些簡單的experiements（使用隨機排列），它 似乎讓他們排隊隨機大於具有 人在前面第三（進一步下跌的走道）第一排隊快，然後 中間三分之一，然後是第三名。這對我來說似乎是錯誤的。
我在MatLab中寫這個，如果這很重要的話。任何想法或答案？
Bachmat，Berend，Sapir，Skiena和Stolyarov撰寫了一篇非常不錯的文章，題目爲Analysis of airplane boarding via space-time geometry and random matrix theory，它模擬飛機登機的確切問題。從他們的摘要：
我們表明，飛機的登機可以通過二維洛倫茲幾何建模漸近。 登機時間由模型中曲線之間的最長時間給出。 模型與 模擬結果的差異與 與隨機矩陣理論密切相關。然後，我們表明 這種模式如何被用來解釋爲什麼 一些普遍實行航空 登機的政策是無效的 甚至是有害的。
本文的結論是：
對於您的設置，我認爲這意味着你應該忽略多遠沿着過道的人，轉而關注它們距離過道有多遠。這款車型還需要時間來存放行李，所以您可能需要根據自己的情況進行調整。無論如何，我認爲這證實了你通過你的模型找到的東西。
我覺得很難在不知道模型的情況下回答這個問題。那裏有多少個入口，它們位於哪裏？什麼導致人們不得不等待多久？是否需要更長的時間坐在自己的座位，如果你要通過有人誰是已經坐在同一行？人們總是直接去正確的座位，還是有時候會來回徘徊尋找正確的排？等等... – 2011-03-15 19:49:53
只有一個入口，需要一個單位的時間向下移動一排或一個座位。 – Daniel 2011-03-15 19:50:46
也許我看着這是錯誤的方式，但如果你有一羣高效率的人從來沒有停下來的方式到他們的座位上（包括不要拖延轉彎和走下島），它不會不管他們命令的順序如何。或者，你不可能每行都有一個人排隊（第一排=前排，最後一排=最後一排），他們都沿着小島走，然後全部轉向並一次走下各自的排（沖洗和重複）。 – 2011-03-15 19:50:58