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

[poster]

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

礼堂中有N = K脳M个座位，每个走道有一个座位， K行， M个座位。假设K大于M ，但我认为这并不重要。有N个人与席位（分配的席位）处于对立。假设人们不喜欢等待，最快速的排队方式就是让他们尽快坐在座位上？

我运行了一些简单的实验（使用随机排列），似乎让他们随机排队比让前面三分之一（靠过道走）的人首先排着队，然后排在中间三分之一，然后排在后面三排要快。对我来说这似乎是错误的。

如果这很重要，我将在MatLab中编写。有什么想法或答案吗？



回答：

巴赫马特（Bachmat），贝伦德（Berend），萨皮尔（Sapir），斯基埃纳（Skiena）和斯托利亚洛夫（Stolyarov）有一篇非常不错的文章，标题是通过时空几何学和随机矩阵理论对飞机登机进行分析，该模型为飞机登机问题建模。从他们的摘要：

我们表明，可以通过二维洛伦兹几何学渐近地对飞机登机建模。登机时间由模型中曲线之间的最大适当时间给出。模型与仿真结果之间的差异与随机矩阵理论密切相关。然后，我们将展示如何使用这种模型来解释为什么一些常用的航空公司登机政策无效且有害。

本文的结论是：

• 最佳：窗户中间走道
• 最佳：随机登机
• 真的很糟糕：从头到尾

对于您的设置，我认为这意味着您应该忽略人们过道的距离，而应该关注人们离过道的距离。该模型还考虑了存放行李的时间，因此您可能需要根据实际情况进行一些调整。无论如何，我认为这可以证实您在模型中找到的内容。



更多&回答...