我正在尝试为以下排序问题找到最佳算法。什么是最好的预留座位排序算法？
有Ñ= 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