Рассадить гостей на основе приоритетных параметров

Question

Следующая модель данных представляет таблицы с местами и гостями в приложении, которое позволяет пользователю создавать столы и места визуально с использованием HTML5.

// The data model
var data = {
    guests: [], // id, name, tags
    tables: [], // id, seats
    seats: [], // id, guest
    tags: [] // id, name
};

У гостей есть теги (категории), прикрепленные к ним. Этим тегам можно присвоить приоритеты и установить их в качестве параметров «группировки» или «разгруппирования». Затем пользователь нажимает «Сиденье», и гости садятся (на первый взгляд случайным образом), в то время как приоритетные параметры соблюдаются.

Полноценный пример: http://jsfiddle.net/kBp49/2/ (см. «РЕШЕНИЕ ЗДЕСЬ» на панели JS)

Вопрос в следующем: Как реализовать функцию, которая размещает гостей за столами, учитывая при этом, что некоторые гости должны сидеть рядом друг с другом, а другие - отдельно друг от друга? для того, чтобы создать одну из лучших морских конфигураций? Количество гостей может превышать 1000, но не 2000.

Пример из реальной жизни, чтобы прояснить проблему

Допустим, у нас есть 3 таблицы. У них есть 4 места каждый. Давайте также скажем, что у нас есть 9 гостей, чтобы заполнить эти таблицы. Они заключаются в следующем:

1. Гость 1, еврей, из США
2. Гость 2, еврей, из Великобритании
3. Гость 3, Кристиан, из США
4. Гость 4, Кристиан, из Великобритании
5. Гость 5, Кристиан, из Швеции
6. Гость 6, Атеист, из Великобритании
7. Гость 7, Атеист, из Швеции
8. Гость 8, мусульманин, из Саудовской Аравии
9. Гость 9, мусульманин, из Великобритании

Теперь пользователь назначает приоритеты таким параметрам. Первый наиболее важен.

1. Я хочу, чтобы люди с одинаковой религией сидели отдельно друг от друга
2. Я хочу, чтобы люди с одинаковым географическим положением сидели рядом друг с другом

Это нормально:

1. Таблица 1: Гости: 1, 3, 7, 8
2. Таблица 2: Гости: 2, 4, 6, 9
3. Таблица 3: Гости: 5

Обновление Одним из решений может быть минимаксный алгоритм. Он рассчитал бы оценку для каждой возможности и представил бы лучшее найденное решение (найденное после, скажем, 10 секунд расчета). С этим алгоритмом мне нужна помощь, сама реализация, конечно, потребует решений, которые может принять только я.

Answer 1

Нет лучшего ответа на этот вопрос, потому что нет лучшего расположения сидений - на самом деле, я бы сказал, что расположение, которое вы говорите «ОК», вероятно, довольно плохое - если вы вынуждены использовать три стола, и вы можете Максимум 4 места за столом, вы, вероятно, должны сидеть по три за каждым столом, чтобы никто не сидел один. Это, однако, отнюдь не является основанием для вопроса.

Есть несколько алгоритмов, которые я могу представить.

Во-первых, вы можете рассматривать каждый «тег» как измерение в N-мерном пространстве (это звучит сложнее, чем есть). Например, в измерении региона вы можете назначить каждой стране целочисленное значение, и измерение для вашего регионального пространства будет иметь каждое из этих целых чисел в качестве потенциальных значений. Затем разместите каждого гостя как точку в этом N-мерном пространстве и выберите для каждого стола тех гостей, которые находятся ближе всего в этом пространстве. Вы можете поддерживать приоритеты, игнорируя некоторые особенности при построении пространства - например, если вы не хотите группировать по религии, не включаете религию при создании пространства или если вы активно хотите разделить людей с «единой» религией, вы Можно изменить расчет расстояния, чтобы иметь обратную зависимость в этом измерении. Этот алгоритм может иметь хорошую производительность в зависимости от количества функций (т. Е. Измерений) и количества точек - по сути, именно так они создают механизмы рекомендаций.

Если вы хотели что-то простое, но медленное, вы могли бы использовать алгоритм грубой силы: то есть для каждого гостя, посмотрите на каждый стол, на котором есть участники, если эти члены нежелательны с учетом ваших приоритетов, сядьте за свежий стол. Если свежих таблиц не существует, выберите таблицу с наименее нежелательными членами. Это, вероятно, так просто, как вы можете пойти!

Наконец, вы можете предварительно обработать своих гостей и посчитать: сколько из региона x, сколько из религии y, ... затем, когда у вас есть эта статистика, вы можете создавать таблицы ( в зависимости от приоритета), например: стол Канады, стол Великобритании, ..., а затем рассадить гостей за любым столом, который соответствует их описанию. Погода это возможно зависит от набора входных данных.

Надеюсь, это поможет и даст вам некоторые идеи о том, как решить эту проблему:)