使用搜索算法解决难题

Question

几天前我遇到了一个谜题.它可以轻松地手动解决.但我试图建立一个解决它的算法.但我不知道该怎么办.

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

这是一个如何解决它的例子.如果描述不清楚.

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

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

谁能给我一些关于如何解决问题的直觉？

Answer 1

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

染色体：

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

健身功能在我脑海中浮现

具有 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 上连接的空间

突变

交叉/繁殖脱离我的头顶