c++ - 人工智能拼图程序

Question

我有一个初始状态的谜题

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) 复杂度的已访问状态。

所以我很困惑我将如何开始实施这个难题的解决方案。谁能指导我？我可以在空白处应用的运算符是上、下、左、右。

Answer 1

最简单的想法是用初始状态初始化根节点。然后填充下一层；编写一个根据空格移动规则生成子节点的程序。你应该在这里小心；当空白在棋盘边缘时，有些动作无效。在这种情况下，可以像这样绘制 A* 算法的草图： 将您与初始状态的距离定义为 g(n)。在给定当前状态的情况下，这可能是与初始状态相比不同位置字母的数量。定义一个启发式 h(n)，它给出了您当前与目标状态的距离，这可能是与目标状态相比不同位置的字母的数量。然后在树中的当前位置，尝试选择下一个状态，使 f(n)=g(n)+h(n) 最小化。