Npc Problems: Vertex Coloring

Npc Problems: Vertex Coloring - минималистическая игра-головоломка о реальной вычислительной задаче.

Нетрадиционная головоломка.
Проблема, которую может решить только искусственный интеллект.
Решите ручные экземпляры задачи Npc vertex coloring.
Наслаждайтесь расслабляющей средой с неоновой графикой и оригинальной синт-волновой музыкой.

Связанные круги не могут иметь одинаковый цвет, можно ли окрасить все круги с помощью минимального количества цветов?

Дополнительная информация:
Проблема окраски вершины представлена графом, представляющим собой набор узлов и линий. Линии соединяют вершины и называются краями.

Проблема окраски вершины является одной из полных неполиномиальных (NP-полных) проблем. Эти проблемы не могут быть решены современными компьютерами, они могут потратить несколько лет, чтобы получить решение, в зависимости от размера экземпляра. Чтобы иметь возможность решать большие задачи, необходимо использование машинного обучения и искусственного интеллекта. В этой игре представлены небольшие относительные экземпляры для решения игроком.

Существует много реальных применений проблемы окраски вершины:

1) Составление расписания или таблицы времени: Предположим, что мы хотим составить расписание экзаменов для университета. У нас есть список различных предметов и студентов, обучающихся по каждому предмету. У многих предметов были бы общие студенты (одна и та же партия, некоторые студенты с отставанием и т. Д.). Как запланировать экзамен так, чтобы не было запланировано одновременно двух экзаменов с обычным студентом? Сколько минимальных временных интервалов необходимо для планирования всех экзаменов? Эта проблема может быть представлена в виде графика, где каждая вершина является предметом, а край между двумя вершинами означает, что есть общий ученик. Так что это проблема окраски графа, где минимальное количество временных интервалов равно хроматическому числу графа.

2) Назначение частоты подвижного радиосвязи: При назначении частот башням частоты, назначенные всем башням в одном и том же месте, должны быть разными. Как определить частоты с этим ограничением? Какое минимальное количество частот необходимо? Эта проблема также является примером проблемы окраски графа, когда каждая башня представляет вершину, а край между двумя башнями представляет, что они находятся в диапазоне друг от друга.

3) Судоку: Судоку также является вариацией проблемы окраски графов, когда каждая клетка представляет собой вершину. Существует край между двумя вершинами, если они находятся в одном ряду или в одном столбце или в одном блоке.

4) Картографическая окраска: Географические карты стран или государств, в которых нет двух соседних городов, не могут быть присвоены одинаковые цвета. Четырех цветов достаточно, чтобы окрасить любую карту.

Источник: