什么是最佳的预留座位排序算法？
什么是最佳的预留座位排序算法？
提问于 2011-03-15 19:46:48
我试图为下面的排序问题找到最佳算法。
每个过道有N =K×M座位，K排座位和M座位。假设K比M大，但我不认为这很重要。有N的人，他们都与座位(指定的座位)相关联。假设人们不喜欢等待，最快的方法是让他们排好队，让他们尽快坐到座位上。
我做了一些简单的体验(使用随机排列)，似乎让他们随机排队比让前面的人排第三(沿着过道的更远)先排第三排，然后是中间的第三排，然后是后面的第三排更快。这在我看来是不对的。
如果这真的很重要的话，我是用MatLab写的。有什么想法或答案吗？
回答 1
Stack Overflow用户
回答已采纳
发布于 2011-03-15 20:04:40
Bachmat，Berend，Sapir，Skiena和Stolyarov写了一篇很好的文章，题为基于时空几何和随机矩阵理论的飞机登机分析，它为飞机登机建立了精确的模型。从其摘要来看：
我们证明了飞机登机可以用二维洛伦兹几何渐近建模.登船时间由模型中曲线间的最大合适时间来确定。模型与仿真结果的差异与随机矩阵理论密切相关。然后我们将展示如何使用这些模型来解释为什么一些常见的航空登机政策是无效的，甚至是有害的。
本文件的结论如下：
- 最佳:橱窗-中间通道
- 近最优:随机登船
- 非常糟糕:背靠背
对于您的设置，我认为这意味着您应该忽略在过道上的人有多远，而应该关注离过道有多远。这个模型也说明了存放行李的时间，因此您可能需要根据您的情况对此进行一些调整。无论如何，我认为这证实了你通过你的模型所发现的东西。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/5317135
复制相关文章
相似问题
腾讯云开发者
