Как я могу доказать, что проблема планирования класса в классе была правильно выполнена?

Question

У меня возникла проблема, касающаяся планирования n классов в k комнатах в школе, и это проблема решения, потому что мы хотим спросить, можем ли мы организовать эти n классов в этих k комнатах, чтобы данный timelimit t (общее время занятий по определенному плановому пути не должно превышать t).

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

Я думал об использовании проблемы с Traveling Salesman для уменьшения, но я не уверен, как интерпретировать мою задачу планирования класса в графе с учетом символики. Моя первая попытка интерпретировать мою проблему как график - рассматривать классы как вершины, комнаты как цвета и время для класса, обозначенного взвешенным краем между двумя классами (последние две интерпретации полностью не уверены). Но я не знаю, соответствует ли это стандартным шаблонам для какой-либо проблемы с планированием, или я даже не знаю, является ли проблема с Traveling Salesman проблемой для NP-полной проблемы, которая сводится к проблеме планирования класса. В последнем случае, я хотел бы узнать примеры более подходящих NP-полных проблем, которые уменьшатся в моем случае.

Заранее благодарен!

Answer 1

Для этого вы можете использовать map-coloring (graph-coloring). Вам просто нужно определить правила для ребер и узлов. Узлы будут классами, комнаты будут цветами, а вы соединяете классы, которые не могут быть в одно и то же время. Это на самом деле проблема k-раскраски, где вам нужно окрасить определенный граф с помощью k цветов, чтобы минимизировать количество классов в цвете. Однако в этом специальном случае вам просто нужно иметь меньше или равно t за цвет. Вы можете добиться этого, перейдя по стандартному правилу окраски и переключитесь на новый цвет, как только у него будет t количество классов.

Это еще проблема с NP-полным. Единственное исключение - когда у вас 1 или 2 класса, а затем в течение полиномиального времени. Когда у вас есть 1 номер, вам просто нужно проверить, есть ли n<=t. Когда у вас есть 2 комнаты, вам просто нужно проверить, может ли он быть окрашен в 2 цвета. Вы можете достичь этого с помощью DFS (но сначала проверьте, есть ли n < = 2t), а цветные нечетные шаги с первым цветом и четными шагами со вторым цветом. Если можно покрасить все узлы этой тактикой, у вас будет положительное решение. Когда k>=3, его NP-complete.