我有一个初始状态的谜题
R R R G R
R G G R R
R G G R G
R G G R R
R R R B R
哪里 R = Red ， G = Green 和 B = Moveable Blank
和目标国家
R R R R R
R G G G R
R G B G R
R G G G R
R R R R R
我知道为了移动空白我必须应用搜索算法，如 DFS, BFS, A* etc
我知道我必须创建类：
节点
class Node {
char board[5][5];
Node *parent;
};
树
class Tree {
Node *root;
};
像Hash Table这样的前沿来检测O（1）复杂度中的访问状态 .
所以我很困惑，我将如何开始实施这个难题的解决方案 . 谁能指导我？我可以在空白处应用的操作员是向上，向下，向左，向右 .
1 回答
最简单的想法是使用初始状态初始化根节点 . 然后填充下一层;根据空白空间移动规则编写生成子节点的过程 . 你在这应该小心;当空白区域位于板的边界时，某些移动将无效 . 在这种情况下，可以绘制A *算法的草图：将初始状态的距离定义为g（n） . 在给定当前状态的情况下，这可以是与初始状态相比放置的不同字母的数量 . 定义一个启发式h（n），它给出了目标状态的当前距离，这可能是与目标状态相比放置的字母数量 . 然后在树中的当前位置，尝试选择下一个状态，最小化f（n）= g（n）h（n） . 我现在无法对此进行深入分析，但我相信这种方法可能比蛮力DFS或BFS方法更有效 .