algorithm - 合并图的相邻顶点，直到以尽可能少的步骤留下单个顶点

Question

我有一个游戏系统，可以表示为一个无向、未加权的图，其中每个顶点都有一个(相关)属性:颜色。就图形表示而言，游戏的目标是以尽可能少的“步骤”将其减少到一个顶点。在每一步中，玩家可以改变任何一个顶点的颜色，并且所有相邻的相同颜色的顶点都与之合并。 (请注意，在下面的示例中，我只是碰巧显示用户在整个游戏中只更改一个特定的顶点，但用户可以在每个步骤中选择任何顶点。)

我所追求的是一种方法来计算按照上述过程“打败”给定图形所需的最少步数，并提供这样做所需的具体 Action 。我熟悉寻路、BFS 和类似性质的基础知识，但我很难根据“最快路径”解决方案来解决这个问题。

我无法在 Google 上的任何地方找到同样的问题，甚至找不到封装该问题的图论术语。有没有人至少知道如何开始解决这个问题？谁能指出我正确的方向？

编辑 由于这个问题似乎真的很难有效解决，也许我可以改变我的问题的目的。有人能描述一下我什至会如何设置蛮力，广度优先搜索吗？ (蛮力可能没问题，因为实际上这些图最多只有 20 个顶点。)我知道如何为普通链接图数据结构编写 BFS ......但在这种情况下它看起来很奇怪，因为每个顶点必须在其内部包含一个完整的图，并且搜索图中的下一个顶点必须基于可能在顶点内的图中进行的移动来生成。如何设置数据结构和搜索算法来实现这一目标？

EDIT 2 这是一个老问题，但我认为直截了本地说明游戏是什么可能会有所帮助。该游戏本质上是对Kami 2 for iOS的剽窃。 , 除了我的自定义拼图编辑器会自动找出最快的方法来解决你的拼图，而不是必须自己通过反复试验找到最短的移动数。我不确定 Kami 是否是一个完全原创的游戏概念，或者是否有一整类游戏都具有我不知道的相同“洪水填充”机制。如果这是一种常见的游戏类型，也许知道它的名称可以让我找到更多关于我正在寻找的算法的文献。

编辑 3 This Stack Overflow question似乎它可能有一些相关的见解。

Answer 1

直觉上，解决方案似乎是全局性的。例如，如果您采用更大的图，您首先选择的点将对直接邻居产生影响，直接邻居将对其邻居产生影响，依此类推。

听起来好像它与 map 着色问题属于同一类问题。不是因为颜色，而是因为本地选择对图表另一端的影响。在 map 着色中，你必须决定用什么颜色来绘制一个国家和它的邻国，这样两个接触的国家就不会有相同的颜色。第一组选择会影响后续迭代中是否有解决方案。