用盲目搜索技术解决八数码问题

题目

在3×3的棋盘，有八个棋子，每个棋子上标有1至8的某一数字，不同棋子上标的数字不相同。棋盘上还有一个空格，与空格相邻的棋子可以移到空格中。要解决的问题是：任意给出一个初始状态和一个目标状态，找出一种从初始转变成目标状态的移动棋子步数最少的移动步骤。算法流程

使用宽度优先搜索

从初始节点开始，向下逐层对节点进形依次扩展，并考察它是否为目标节点，再对下层节点进行扩展（或搜索）之前，必须完成对当层的所有节点的扩展。再搜索过程中，未扩展节点表OPEN中的节点排序准则是：先进入的节点排在前面，后进入的节点排在后面。

宽度优先算法如下：

把初始结点S0放入OPEN表中

若OPEN表为空，则搜索失败，问题无解

取OPEN表中最前面的结点N放在CLOSE表中，并冠以顺序编号n 若目标结点Sg?N，则搜索成功，问题有解若N无子结点，则转2

扩展结点N，将其所有子结点配上指向N的放回指针，依次放入OPEN表的尾部，转2 源程序

#include #include #include using namespace std;

constint ROW = 3;//行数 constint COL = 3;//列数

constint MAXDISTANCE = 10000;//最多可以有的表的数目

constint MAXNUM = 10000;

typedefstruct _Node{ int digit[ROW][COL];

intdist;//distance between one state and the destination 一个表和目的表的距离 intdep; // the depth of node深度

// So the comment function = dist + dep.估价函数值 int index; // point to the location of parent父节点的位置 } Node;

Node src, dest;// 父节表目的表

vectornode_v; // store the nodes存储节点

boolisEmptyOfOPEN() //open表是否为空 {

for (int i = 0; i

boolisEqual(intindex,int digit[][COL]) //判断这个最优的节点是否和目的节点一样

{

for (int i = 0; i < ROW; i++) for (int j = 0; j < COL; j++) {

if (node_v[index].digit[i][j] != digit[i][j]) return false;

} return true; }

ostream& operator<<(ostream&os, Node& node) {

for (int i = 0; i < ROW; i++) { for (int j = 0; j < COL; j++) os<

void PrintSteps(int index, vector&rstep_v)//输出每一个遍历的节点深度遍历

{

rstep_v.push_back(node_v[index]); index = node_v[index].index; while (index != 0) {

rstep_v.push_back(node_v[index]); index = node_v[index].index; }

for (int i=rstep_v.size()-1;i>=0;i--)//输出每一步的探索过程 cout<< \