algorithm - 最好的预留座位排序算法是什么？

Question

我正在尝试为以下排序问题找到最佳算法。

礼堂有 N = K × M 个座位，只有一个过道，K 排，每个过道有 M 个座位。假设 K 比 M 大，但我认为这不是很重要。有 N 人在与座位(分配的座位)的双射。假设人们不就像等待一样，什么是最快的方式来排列它们以得到它们尽快坐在他们的座位上？

我进行了一些简单的实验(使用随机排列)并且它似乎让他们随机排队比让他们排队更快前面三分之一的人(过道更远的地方)先排队，然后中间三分之一，然后是后三分之一。这对我来说似乎是错误的。

如果这很重要的话，我会在 MatLab 中写这篇文章。有什么想法或答案吗？

Answer 1

Bachmat、Berend、Sapir、Skiena 和 Stolyarov 有一篇非常好的文章，标题为 Analysis of airplane boarding via space-time geometry and random matrix theory这模拟了飞机登机的确切问题。来自他们的摘要:

We show that airplane boarding can be asymptotically modeled by 2-dimensional Lorentzian geometry. Boarding time is given by the maximal proper time among curves in the model. Discrepancies between the model and simulation results are closely related to random matrix theory. We then show how such models can be used to explain why some commonly practiced airline boarding policies are ineffective and even detrimental.

论文的结论是:

• 最佳:靠窗-中间过道
• 接近最优:随机登机
• 非常糟糕:从头到尾

对于您的设置，我认为这意味着您应该忽略人们离过道有多远，而是关注他们离过道有多远。此模型还考虑了存放行李的时间，因此您可能需要根据自己的情况进行一些调整。无论如何，我认为这证实了您通过模型发现的内容。