algorithm - 使用搜索算法解决难题

Question

几天前我遇到了一个难题。它很容易用手解决。但我试图建立一个算法来解决它。但我不知道我应该如何进行。

在这里你可以看到我必须连接所有成对的彩色点。例如，我需要将黄点连接到另一个黄点，将绿色连接到其他绿色，将蓝色连接到蓝色等等。

这是一个应该如何解决的例子。如果描述不清楚。

所以你可以看到我将黄点与另一个黄点相连。蓝色与另一种蓝色。但这会导致一个问题。如您所见，我已经阻挡了浅绿色的路径。我希望你明白这一点。

所以我想解决它。蛮力方法会起作用，但需要很长时间，我对此不感兴趣。我尝试实现广度优先搜索、深度优先搜索和 Dijkstra 算法。但我认为他们在这种情况下不会很好。如果我错了，请纠正我。 A* 搜索可能有效，但启发式方法是什么？

谁能给我一些解决问题的直觉？

Answer 1

I 遗传算法可能是获得解决方案的合适方法。适应度函数和交叉必须专门针对该问题进行调整。

染色体:

• 9x9 二维整数数组(基因)
• 您的 18 种独特颜色的棋子将被静态设置为 512|1、512|2、512|4、512|8、512|16、512|32、512|64、512|128、512|256，代表9种独特的颜色； 512 (2^9) 将是表示它们为静态/不可更改基因的标志。
• 彩色连接方 block 将有 2^0-2^8 个值，这些基因可以改变和组合，值 3 (011b) 表示 2 种颜色(1 和 2)共享同一个方 block 。

健身功能不在我的脑海中

• 具有 1 种独特颜色的空间为 +8、2 种颜色 +6、3 种颜色 +4、4 种颜色 +2、5 种颜色 +0、6 种颜色 -2、7 种颜色 -4、8 种颜色 -6、所有 9 种颜色-8
• 与匹配的彩色静态空间相连(左、右、上、下)的空间为 +9
• 在 1 个方向 +4、2 个方向 +3、3 个方向 +2、4 个方向 +1 上与匹配的彩色空间相连的空间

突变

• 逻辑异或随机颜色位 (1 << Floor(Random() * 9)) 与随机非静态基因

跨界/育种超出我的想象

• 复制你的 2 条候选染色体
• 清除包含 5 个或更多重叠颜色的副本中的基因
• 逻辑或将两条染色体放在一起得到结果