Рекомендации программного обеспечения плана рассадки (такой зверь вообще существует?)

Question

Я скоро женюсь и занимаюсь планом рассадки, и сталкиваюсь с обычными вопросами о том, кто сидит, где: X и Y должны сидеть вместе, но А и В не могут стоять друг против друга и т.д.

Числа, с которыми я имею дело, не огромны (так что ручной вариант будет работать просто отлично), но, будучи убежденным, мне было интересно, есть ли какое-нибудь программное обеспечение, способное сделать это для меня?

Если точное совпадение не найдено, что я должен искать (проблемное место, книги, справочный код), чтобы настроить его для моих целей?

Answer 1

Я разработчик PerfectTablePlan. Я публикую здесь, а также Бизнес программного обеспечения Джоэла . ; 0)

Комбинаторные проблемы, такие как распределение мест, являются довольно неприятными алгоритмически. NP-hard на самом деле. Количество способов разместить 60 гостей на 60 мест - 60! (60 факторных), и это больше, чем число атомов в известной вселенной.

PerfectTablePlan позволяет вам указать, что A должен сидеть рядом с B, но не рядом с C. Он использует генетический алгоритм для автоматического назначения мест. На практике это работает довольно хорошо - обычно за несколько секунд найдется достойное решение для 100 гостей. Возможно, вам придется приготовить кофе для 1000+ гостей. На практике обычно требуется некоторая подстройка перетаскивания, чтобы справиться с капризами местных обычаев и семейной политики (дядя Боб немного глух, нам лучше поставить его ближе к верхнему столу).

Вы можете узнать немного больше о генетическом алгоритме здесь .

Ps / Автоматическое распределение мест - лишь малая часть создания хорошего плана сидения. Для получения дополнительной информации см. Страницу PerfectTablePlan и страницу tips .

Answer 2

http://www.perfecttableplan.com/

Я полагаю, что это от парня, который обычно пишет в Joel On Software.

Никогда не пробовал, хотя. Надеюсь, это поможет.

Answer 3

Мой личный фаворит - не назначать места: разрешайте людям сидеть там, где они хотят.

Это может привести к [не] преднамеренной заторможенности, но это означает, что вам не нужно об этом беспокоиться.

Answer 4

Попробуйте смоделировать это с помощью GLPK. Целочисленное линейное программирование поддается введению ограничений в задачи на основе графа с множеством возможных результатов.

Answer 5

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

Надеемся, что есть тот, который имеет простой интерфейс на вашем любимом языке для ввода и вывода данных.

Answer 6

Некоторое время назад я использовал программу, которая идеально подходила бы для этого ... Это было приложение Java, вы могли определять правила и создавать тестовые случаи, которые удовлетворяли правилам. Расширение файла было .als

fact GateRules {
   all g:Gate | one g.loc // Gates have 1 Location

Я продолжу ломать голову над названием программы.

РЕДАКТИРОВАТЬ: Это был Сплав Теперь, когда я думаю об этом, он может быть не идеальным - понятие «места в фиксированной конфигурации» будет немного сложным для моделирования. Я использовал его по-другому: определяя правила (ворота аэропорта находятся в одном месте, на взлетно-посадочной полосе только один самолет), и проверяя предварительные и последующие условия для функций (после того, как я посадил самолет, могу ли я даже иметь более одного самолета на взлетно-посадочная полоса?).

Answer 7

Я ожидаю, что это не очень хороший ответ, но вы могли бы исследовать стадное поведение

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