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

用盲目搜索技术解决八数码问题题目在33的棋盘，有八个棋子，每个棋子上标有1至8的某一数字，不同棋子上标的数字不相同。棋盘上还有一个空格，与空格相邻的棋子可以移到空格中。要解决的问题是：任意给出一个初始状态和一个目标状态，找出一种从初始转变成目标状态的移动棋子步数最少的移动步骤。算法流程使用宽度优先搜索从初始节点开始，向下逐层对节点进形依次扩展，并考察它是否为目标节点，再对下层节点进行扩展（或搜索）之前，必须完成对当层的所有节点的扩展。再搜索过程中，未扩展节点表OPEN中的节点排序准则是：先进入的节点排在前面，后进入的节点排在后面。宽度优先算法如下： 把初始结点S0放入OPEN表中 若OPEN表为空，则搜索失败，问题无解 取OPEN表中最前面的结点N放在CLOSE表中，并冠以顺序编号n 若目标结点，则搜索成功，问题有解 若N无子结点，则转2 扩展结点N，将其所有子结点配上指向N的放回指针，依次放 入OPEN表的尾部，转2源程序#include #include #include using namespace std; const int ROW = 3;/行数 const int COL = 3;/列数const int MAXDISTANCE = 10000;/最多可以有的表的数目 const int MAXNUM = 10000; typedef struct _Node int digitROWCOL; int dist;/distance between one state and the destination一个表和目的表的距离int dep; / the depth of node深度 / So the comment function = dist + dep.估价函数值int index; / point to the location of parent父节点的位置 Node; Node src, dest;/ 父节表 目的表 vector node_v; / store the nodes存储节点 bool isEmptyOfOPEN() /open表是否为空 for (int i = 0; i node_v.size(); i+) if (node_vi.dist != MAXNUM) return false; return true; bool isEqual(int index,int digitCOL) /判断这个最优的节点是否和目的节点一样 for (int i = 0; i ROW; i+) for (int j = 0; j COL; j+) if (node_vindex.digitij != digitij) 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 node.digitij ; os endl; return os; void PrintSteps(int index, vector& rstep_v)/输出每一个遍历的节点 深度遍历 rstep_v.push_back(node_vindex); index = node_vindex.index; while (index != 0) rstep_v.push_back(node_vindex); index = node_vindex.index; for (int i=rstep_v.size()-1;i=0;i-)/输出每一步的探索过程cout Step rstep_v.size() - i endl rstep_vi endl; void Swap(int& a, int& b) int t; t = a; a = b; b = t; void Assign(Node& node, int index) for (int i = 0; i ROW; i+) for (int j = 0; j COL; j+) node.digitij = node_vindex.digitij; int GetMinNode() /找到最小的节点的位置即最优节点 int dist = MAXNUM; int loc; / the location of minimize node for (int i = 0; i node_v.size(); i+) if (node_vi.dist = MAXNUM) continue; else if (node_vi.dist + node_vi.dep) dist) loc = i; dist = node_vi.dist + node_vi.dep; return loc; bool isExpandable(Node& node) for(int i=0;inode_v.size();i+) if (isEqual(i, node.digit) return false; return true; int Distance(Node& node, int digitCOL) int distance = 0; bool flag = false; for(int i = 0; i ROW; i+) for (int j = 0; j COL; j+) for (int k = 0; k ROW; k+) for (int l = 0; l COL; l+) if (node.digitij = digitkl) distance += abs(i - k) + abs(j - l); flag = true; break; else flag = false; if(flag) break; return distance; int MinDistance(int a,int b) return (ab?a:b); void ProcessNode(int index) int x, y; bool flag; for (int i = 0; i ROW; i+) for (int j = 0; j 0) Swap(node_up.digitxy, node_up.digitx - 1y); if (isExpandable(node_up) dist_up = Distance(node_up, dest.digit); node_up.index = index; node_up.dist = dist_up; node_up.dep = node_vindex.dep + 1; node_v.push_back(node_up); Node node_down; Assign(node_down, index);/向下扩展的节点int dist_down = MAXDISTANCE; if (x 0) Swap(node_left.digitxy, node_left.digitxy - 1); if (isExpandable(node_left) dist_left = Distance(node_left, dest.digit); node_left.index = index; node_left.dist = dist_left; node_left.dep = node_vindex.dep + 1; node_v.push_back(node_left); Node node_right; Assign(node_right, index);/向右扩展的节点int dist_right = MAXDISTANCE; if (y 2) Swap(node_right.digitxy, node_right.digitxy + 1); if (isExpandable(node_right) dist_right = Distance(node_right, dest.digit); node_right.index = index; node_right.dist = dist_right; node_right.dep = node_vindex.dep + 1; node_v.push_back(node_right); node_vindex.dist = MAXNUM; int main() / 主函数 int number; cout Input source: endl; for (int i = 0; i ROW; i+)/输入初始的表 for (int j = 0; j number; src.digitij = number; src.index = 0; src.dep = 1; cout Input destination: endl;/输入目的表for (int m = 0; m ROW; m+) for (int n = 0; n number; dest.digitmn = number; node_v.push_back(src);/在容器的尾部加一个数据 cout Search. endl; clock_t start = clock(); while (1) if (isEmptyOfOPEN() cout Cannt solve this statement! endl; return -1; else int loc; / the location of the minimize node最优节点的位置 loc = GetMinNode(); if(isEqual(