NPC问题：顶点着色NPC问题：顶点着色

Npc Problems: Vertex Coloring 是一款关于真实计算问题的极简主义解谜游戏。

• 一款非传统的解谜游戏。
  
• 一个只有人工智能才能解决的问题。
  
• 解决 Npc 问题顶点着色中精心设计的实例。
  
• 在拥有霓虹画面和原创合成波音乐的轻松环境中享受游戏乐趣。

相连的圆圈不能颜色相同，你能用最少的颜色为所有圆圈上色吗？


附加信息：
顶点着色问题由图表示，图是一组节点和连线。连线连接顶点，称为边。

顶点着色问题是完全非多项式（NP 完全）问题之一。这些问题无法由当今的计算机解决，根据实例的大小，可能需要花费数年时间才能得到解。为了能够解决大型实例，必须使用机器学习和人工智能。在本游戏中，为玩家呈现的是相对较小的实例以供解决。

顶点着色问题在现实世界中有许多应用：

1) 制定日程或时间表：假设我们要为大学制定考试时间表。我们有不同科目的列表以及每个科目注册的学生名单。许多科目会有共同的学生（同一批次、一些补考学生等）。我们如何安排考试，使得没有两名有共同学生的考试在同一时间进行？安排所有考试最少需要多少个时间段？这个问题可以表示为一个图，其中每个顶点代表一个科目，两个顶点之间的边表示存在共同的学生。因此，这是一个图着色问题，其中最少的时间段数量等于图的色数。

2) 移动无线电频率分配：当为基站分配频率时，位于同一地点的所有基站分配的频率必须不同。如何在满足此约束的情况下分配频率？最少需要多少种频率？这也是图着色问题的一个实例，其中每个基站代表一个顶点，两个基站之间的边表示它们在彼此的范围内。

3) 数独：数独也是图着色问题的一种变体，其中每个单元格代表一个顶点。如果两个顶点位于同一行、同一列或同一宫格内，则它们之间有一条边。

4) 地图着色：国家或州的地理地图中，任何两个相邻的城市不能被分配相同的颜色。四种颜色足以给任何地图着色。

来源：