Блог

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

Пример: Алиса, Боб, Чарли, Дэн, Ева, Фрэнк, Джерри и Хайди придут на ужин. Создайте случайное расположение мест таким образом, чтобы Элис не была рядом с Джерри, а Чарли не был рядом с Фрэнком.

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

Я предполагаю, что лучшее решение включает:

• Использование хвостовой рекурсии, чтобы я создавал резервные копии только настолько, насколько это необходимо для разрешения конфликтов, вместо того, чтобы перетасовывать весь список и надеяться на лучшее.
• Сортировка исходного списка по количеству исключений для каждой записи, чтобы сначала разрешались «более сложные» элементы, в то время как в хвосте остается больше вариантов.

Однако, пока я работаю над этим, мне интересно, есть ли способ заранее определить, невозможно ли выполнить исключения смежности определенного списка. Может быть, построив дерево «законных» опций и проверив, равна ли его глубина <длине списка?

Может быть чрезвычайно сложно добавить ограничения к выборке пространства без смещения распределения. Если вы выполняете частичное отслеживание назад, то вы предоставляете привилегии ранее размещенным элементам над размещенными позже, делая распределение ранее размещенных ближе к ожидаемому от (неограниченного) случайного перетасовки, одновременно увеличивая влияние ограничений на размещенные позже. Рассмотрим случай, когда только Алисе, Иоланде и Зельде разрешено сидеть рядом с Бет. Если вы назначаете места в алфавитном порядке, возвращаясь назад, когда сталкиваетесь с неразрешимыми ситуациями, вероятность того, что Алиса окажется рядом с Бет, намного меньше, чем у любой из двух других, поскольку Бет вряд ли будет изначально помещена рядом с Алисой, и ваше отслеживание назад никогда не заставит вас переместить Бет.

То, что вы называете «ленивым», известно как выборка отклонения, и это часто предпочтительный подход для такого рода проблем, поэтому не продавайте его коротким. Для ситуаций, когда вы собираетесь отклонять большую часть своего пространства, есть несколько вариантов выборки отклонения, которые могут хорошо работать, как только вы их обдумаете. Я также получил хорошие результаты, используя алгоритм Метрополиса-Гастингса, который (IMO) легче понять и использовать. Если вам нужен только один образец, вы должны выполнить этап записи, а затем просто взять текущее состояние.

Вы не описали никаких ограничений на свои ограничения. Таким образом, простой ответ «нет»: не существует метода определения того, существует ли решение, за исключением перебора всех допустимых последовательностей в поисках той, которая удовлетворяет всем ограничениям.

Если вы можете охарактеризовать свои ограничения, то вы можете направить поиск в зависимости от этих свойств. Если все ограничения имеют логические свойства, поддающиеся формальному доказательству, то у вас будет система, в которой у вас будет шанс получить результат «да / нет» при поиске в пространстве ограничений, а не в N! пространстве поиска методом перебора.

ВОЗМОЖНЫЙ ПОДХОД

Мы хотели бы сначала рассадить самых больших жалобщиков: начните с решения известных проблем, прежде чем они приведут к сбою размещения.

1. Инициализируйте seat_next список как пустой.
2. Выберите случайного невостребованного пользователя, указанного в ограничениях; добавьте к seat_next .
3. Извлеките человека из seat_next .
4. Найдите допустимое место для этого человека; если его нет, верните сбой (обратный путь).
5. Добавьте всех остальных, указанных в этом ограничении, в seat_next .
6. Если seat_next пусто, вернитесь к шагу 2; в противном случае вернитесь к шагу 3.

Есть еще много элементов настройки, которые необходимо учитывать, в зависимости от взаимодействия и типа ограничения. Например, вы можете взвешивать людей в соответствии с количеством ограничений, в которых они появляются; вы можете захотеть сложить или поставить в очередь ограничения, чтобы вы стремились удовлетворить одно ограничение, прежде чем переходить к следующему.