目标是使用 A* 搜索解决颜色迷宫难题。这是游戏的示例https://www.mathplayground.com/logic_color_maze。基本上，您希望最小化移动成本，目标是为穿过单元格的所有迷宫着色。为了使用 A* 搜索来实现它，我们需要启发式函数。我想看看左边彩色单元格的数量，但这毫无意义。难道它不应该是目标状态的估计成本（每个单元格都被着色）吗？有什么想法可以解决这个问题吗？
要实现 A* 搜索的可接受，启发式函数不得高估剩余距离。就是说低估也可以，但是高估是不行的。
因此，考虑到这一点，您需要决定要尽量减少搜索的内容。是整个地图着色之前走过的方格数吗？在这种情况下，剩下的无色方块的数量将是一个可接受的启发式，因为您当然需要移动所有剩余的无色方块才能完成拼图。
另一方面，如果您要测量所需的直线移动次数，则需要更奇特的启发式方法，因为一次移动即可对许多方块进行着色。我没有什么好主意，但也许无色方块的唯一 X 坐标和唯一 Y 坐标的最小值（或总和？）可以工作。
有很多可能可接受的启发式方法，因此请选择一种，看看它是否足够适合您的用例。它可能不是“最好的”启发式，但这只是意味着搜索效率会降低一些，而不是最终找不到最佳路线。在最坏的情况下，您最终会得到Dijkstra 算法（相当于带有始终返回 0 的启发式函数的 A*）。使用良好的启发式方法只会加快速度，因为您不会检查尽可能多的可能比最佳解决方案慢的部分解决方案。