Какой лучший алгоритм сортировки зарезервированных мест?

Question

Я пытаюсь найти лучший алгоритм для следующей задачи сортировки.

В зале имеется N = K × M мест с одним проходом, K рядов и M мест на проход. Предполагается, что K больше, чем M , но я не думаю, что это очень важно. Есть N людей, которые находятся в Биекция с местами (назначенные места). Предполагая, что люди не как ожидание, какой самый быстрый способ выстроить их в ряд, чтобы получить их всех на своих местах как можно быстрее?

Я провел несколько простых экспериментов (используя случайные перестановки), и это казалось, что позволить им выстроиться в линию случайным образом быстрее, чем иметь люди в первой трети (далее по проходу) выстраиваются в очередь сначала, затем средняя треть, затем третья спина. Это кажется мне неправильным.

Я пишу это в MatLab, если это вообще имеет значение. Есть идеи или ответы?

Answer 1

Существует очень хорошая статья Бахмата, Беренда, Сапира, Шиены и Столярова, озаглавленная Анализ посадки самолета с помощью геометрии пространства-времени и теории случайных матриц , которая моделирует эту точную проблему для посадки самолета. Из их аннотации:

Покажем, что посадку в самолет можно асимптотически моделируется 2-мерная лоренцева геометрия. Время посадки дается максимальным правильное время среди кривых в модели. Расхождения между моделью и Результаты моделирования тесно связаны к теории случайных матриц. Затем мы покажем как такие модели могут быть использованы для объяснения почему некоторые часто практикуемые авиакомпании политика посадки неэффективна и даже вредно.

Выводы статьи:

• ЛУЧШИЙ: Окно-Средний проход
• РЯДОМ ОПТИМАЛЬНО: Случайная посадка
• ДЕЙСТВИТЕЛЬНО ПЛОХО: задний ход

Для вашей установки, я думаю, это означает, что вы должны игнорировать как далеко вниз по проходу люди и вместо этого сосредоточиться на как далеко от прохода они находятся. Эта модель также учитывает время для хранения багажа, поэтому вам, возможно, придется скорректировать это в зависимости от ситуации. В любом случае, я думаю, это подтверждает то, что вы находите в своей модели.