«Frenemies», или Как сделать подростков счастливыми на вечеринке с днем ​​рождения

Question

У меня есть проблема комбинаторной оптимизации, с которой я борюсь. Технические детали проблемы громоздки, поэтому я перевел что-то с точки зрения фиктивного сладкого дня рождения 16. Очевидно, подростки NP трудны, но это отдельно от реальной проблемы, которую я пытаюсь решить.

Скажем, у меня есть сын, которому вот-вот исполнится 16 лет. Он приглашает всех своих друзей на свой день рождения, но не всех его друзей, как друг друга. На самом деле, у каждого друга моего сына есть хотя бы один человек, которого они не любят, а у некоторых больше. Эти «frenemies» отказываются сидеть за одним столом, если один или несколько присяжных «frenemy» сидят за одним столом. Мой сын предоставил мне список всех его приглашенных друзей, а также кому не нравится кто. Эта информация симметрична (если другу A не нравится друг B, друг B не любит друга A), но он НЕ транзитивен (если друг A не любит друга B, но любит друга C, друг C все еще свободно любить или не любить друга B). Мой вопрос: как определить минимальное количество таблиц, удовлетворяющих условию, что две «frenemies» не сидят за одной таблицей?

Answer 1

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

• одной переменной в другом, то значение будет таблица,
• дополнительные ограничения (согласно списку) вида friendX !- friendY сказать, что эти два не могут сидеть за одним столом.

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

В зависимости от размера проблемы (т. Е. Количества друзей и таблиц) это может работать или не работать. Что-то, что вам, возможно, придется учитывать, это симметрия проблемы (т. Е. Люди из таблицы A могут перейти к таблице B и наоборот, и это все еще решение), которые могут быть нарушены дополнительными ограничениями.

Answer 2

Это комбинаторная проблема оптимизации, а не проблема машинного обучения.

На самом деле, это проблема окраски: Создайте граф G, где каждая вершина соответствует человеку. Край (u, v) существует, если два человека u и v не любят друг друга. Теперь вы запрашиваете наименьший k, так что G - k -colorable. Раскраска c(v) сообщает, какой стол человек v сидит на.

Теперь у вас есть только pick an algorithm.