Алгоритм поиска и сопоставления

Question

Я пытаюсь придумать алгоритм для следующего:

У меня есть всего 12 ячеек, которые мне нужно заполнить до остановки программы. У меня есть 3 строки, и в каждой строке 4 столбца.

В качестве примера позвольте мне проиллюстрировать это как на самолете. Таким образом, у вас есть 3 ряда, и у каждого ряда есть 4 столбца, и у вас есть места у окна / прохода. В каждом ряду будет сиденье у окна, у прохода, у прохода и у окна (| WA AW | Так же, как расположение сидений в самолете). На каждой итерации (разные группы пассажиров) будет определенное количество пассажиров (от 1 до 12), и мне нужно расположить их как можно ближе друг к другу (место вместе). И я делаю это для следующей группы (каждой итерации), пока программа не остановится (она остановится, когда я закончу с каждой группой).

Например, у меня есть 3 пассажира (A, B и C), и A хочет сесть в Окно, B хочет сесть в Проход, а C хочет сесть в Окно. Предполагая, что все места (все 12) доступны, я мог бы разместить их как | A # BC | или | CB #A | и пометить сиденья грязными (чтобы я не выбрал те же места для следующих пассажиров). И я делаю это для следующей группы (итерация). Я не уверен, что это правильный форум, но если кто-то может посоветовать мне, как мне это сделать, я был бы очень признателен.
Спасибо.

Answer 1

Если ввод поступает по порядку и при условии, что количество мест всегда до 12, есть только 2^12 способов, которыми места можно занять в каждом штате (группа пассажиров). Вы можете использовать это, чтобы сократить количество состояний для решения перебора / напоминания.

Псевдокод:

IsSeatingPossible( mask, passengers ) =
    if ( no more passengers ) return true
    return IsSeatingPossible =
        new_mask = mask + brute force on passenger constraints
        if any IsSeatingPossible( new_mask, 
                      passengers - just processed passengers )

Больше объяснений:

Маска в основном представляет собой массив из 12 логических значений, в котором указывается, берется ли seat_i для каждого i (вы можете легко преобразовать 2D (x,y) -> 1D (x)). Затем вы перебираете возможности. Полное размещение возможно, если для этого пассажирского набора (A_1, A_2, .., A_k) у каждого есть место, и у остальных пассажиров есть места.

Таким образом, маска, которая передается на английском языке, это места, которые заняты. Допустим, вы сидите (A_1, A_2, .., A_k) на сидениях (x_1, x_2, .., x_k). Есть несколько подмножеств, в которых могут сидеть пассажиры, ограниченные N choose k, что в данном случае мало. Это та часть, на которой ты грубой силой. Учитывая конкретный (x_1, x_2, .., x_k), это размещение возможно, если (x_1, x_2, .., x_k) не перекрывается с текущей маской (по существу, нет конфликтующих мест) и что возможно обрабатывать остальные запросы пассажиров, учитывая, что новая маска, который является просто установленным дополнением текущей маски и (x_1, x_2, .., x_k). (Новые наборы сидений, которые заняты.)

Это может быть или не быть достаточно быстрым. Замечательно отметить, что кроме того, какие места заняты и какие пассажиры были обработаны, решение для определенной подзадачи одинаково. Поэтому вы можете ускорить это тривиально, используя memoization . Это дает O(N 2^N) космическое решение.

Маска лучше всего реализована с использованием битовой маски, особенно для N = 12, отсюда и название. Для списка запросов пассажиров вам, вероятно, нужно просто отслеживать, какой индекс.

Answer 2

Это экземпляр типа задачи Рюкзак с ранее известными решениями.

Answer 3

Если на самом деле это всего 12 ячеек, а размеры групп известны заранее, то динамическое программирование, вероятно, подойдет. Вычислить для каждого набора занятых мест (2 ^ 12) и каждого k (0 <= k <= 12), могут ли первые k групп быть размещены надлежащим образом, чтобы занимать именно этот набор мест. (Как оптимизация, k определяется размером набора.) В конце, работайте в обратном направлении: если я помещу последнюю группу здесь, могу ли я разместить другие группы в оставшихся местах? И так далее. </p>