[新手篇] 深度优先搜索求解数字华容道

2024-07-13 00:05| 来源: 网络整理| 查看: 265

[问题描述]：采用深度优先搜索的方法求解数字华容道，如图所示（用“0”代表空白块）：

GitHub代码地址：点击打开链接

一、由于要求以深度优先搜索的方法求解华容道，故，第一步建立用于搜索的树结构。为了使树中的上下层相邻的节点之间保持一个规则的联系，考虑到华容道的每次只能改变数字‘0’（或空白块）一次，故每次产生新节点都移动一次数字“0”。如下图所示： https://github.com/nblianyan/solve_klotski_use_deepFirst_search.git

在上图中，“0”可以往两个移动，所以，该节点可以产生两个子节点。但是，上图中的左图的产生有三种情况需要考虑，a、“0”从位置(2,3) (注：第二行，第三列，下同)上移；b、“0”从位置（1,2）右移；c、该图是输入的状态。上述三种情况中，c情况不用考虑，在其他两种情况，如果我们直接生成两个子节点，必然会重复一个，而作为树结构，如果在较为接近顶层的层上产生一个重复节点，那么将会产生巨多重复的子树，故我们需要在某节点生成子节点时，要避免生成和该节点的父节点具有相同矩阵的节点。于是乎，我们定义节点所需的结构体：

/* 名称：struct klotski_struct_1 功能：用以描述深度优先搜索所使用的“树”中的节点 */ typedef struct klotski_struct_1 Type_KlotskiNode; struct klotski_struct_1 { int NodeID; //节点ID，每个节点ID全局唯一 int TreeDepth; //当前节点所在的树中的位置的深度 Enum_Operate lastOperation; //上一层生成本节点所使用的操作 short Array[3][3]; //核心部分，记录本节点的矩阵 Type_KlotskiNode * preNode; //指针，指向父节点 Type_KlotskiNode * nextNode[4]; //指针数组，用以指向子节点 };

在上面的结构体中，我们用 Enum_Operate类型枚举变量 lastOperation记录生成该节点所对“0”执行的操作：左移、上移、下移、右移。Enum_Operate枚举类型如下所示：

/* 名称：enum klotski_enum_1 功能：用以描述某节点生成子节点所执行的操作 */ typedef enum klotski_enum_1 Enum_Operate; enum klotski_enum_1 { OperationDown = 0, //数字“0” 向下移动 OperationUp = 1, //数字“0” 向上移动 OperationRight= 2, //数字“0” 向右移动 OperationLeft = 3, //数字“0” 向左移动 OperationNone = 4 //数字“0” 无操作 };

其中OperationNone用于最初的、第一个、最顶层的节点初始化，因为该节点是由我们输入的最初状态，它不会出现上述的重复节点的问题。

再说回Type_KlotskiNode结构体，其中Type_KlotskiNode * preNode指向父节点，Type_KlotskiNode * nextNode[4]指向子节点（由矩阵图可以看见，每个节点最多只可能由四个子节点，最少一个），由此构成树。

如何生成下一节点？在函数 int klotski_tree_create_child_node(Type_KlotskiNode * FatherNode) 中，由于各个位置的操作均不相同，智商不够，体力来凑，于是我将各个点独立讨论，我们截取一部分讨论，其他类同： switch(PositionX) //判断“0”在哪一行 { case 0: //如果"0"在第一行 { if(PositionY == 0) //如果“0”在第一列 { if(FatherNode->lastOperation == OperationNone) //如果生成此节点的时候，没有对"0"执行任何移位操作， { //也就意味着该节点是输入的，不是中间生成的 for(i=0;inextNode[i] = klotski_tree_malloc_2_child_node(); //在这种情况下，只能生成 FatherNode->nextNode[i]->preNode = FatherNode; //两个子节点，分别为他们申请 } //内存，并使子节点的preNode for(i=2;inextNode[i] = NULL; //对于没用的指针，使其指向NULL klotski_tree_init_node(FatherNode->nextNode[0], PositionX,PositionY,OperationRight); //对生成的两个子节点分别对其中的 klotski_tree_init_node(FatherNode->nextNode[1], //参数初始化 PositionX,PositionY,OperationDown); } else if(FatherNode->lastOperation == OperationLeft) { ........ //如上 } else if(FatherNode->lastOperation == OperationUp) { ....... } }

如何生成树？生成树的过程必然要用到递归，也可以理解为，每一棵树都是由以它的子节点为顶点的子树构成。我在生成树的同时，确定新生成的节点的矩阵是不是和我们的目标矩阵相同。

int klotski_tree_create_tree(Type_KlotskiNode * TreeHead, int TreeDepth) { int i; if(PUBLIC_IsFinDCorret) //由于使用的是递归，当子树已经找到了答案时，我们直接退回到上层，递归至完全退出建树的函数 return 0; if(TreeDepth TreeDepth >= 12 ) //如果子节点的深度已经到达了12层，我们需要在该子节点的父系节点中找重复的节点 { //如果存在，则无需在该节点下建树，因为一定会重复， if(klotski_seek_same_node(TreeHead,TreeHead->preNode) == 0) klotski_tree_create_tree(TreeHead->nextNode[i],TreeDepth-1); else return 0; } else klotski_tree_create_tree(TreeHead->nextNode[i],TreeDepth-1); //在该处递归创建子树 } } return 0; } }

以上即为解题所需的核心思想，其他辅助代码请自行阅读代码。

【本文地址】

公司简介

联系我们