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

《用盲目搜索技术解决八数码问题(8页).doc》由会员分享，可在线阅读，更多相关《用盲目搜索技术解决八数码问题(8页).doc（8页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、-用盲目搜索技术解决八数码问题-第 8 页用盲目搜索技术解决八数码问题题目在33的棋盘，有八个棋子，每个棋子上标有1至8的某一数字，不同棋子上标的数字不相同。棋盘上还有一个空格，与空格相邻的棋子可以移到空格中。要解决的问题是：任意给出一个初始状态和一个目标状态，找出一种从初始转变成目标状态的移动棋子步数最少的移动步骤。算法流程使用宽度优先搜索从初始节点开始，向下逐层对节点进形依次扩展，并考察它是否为目标节点，再对下层节点进行扩展（或搜索）之前，必须完成对当层的所有节点的扩展。再搜索过程中，未扩展节点表OPEN中的节点排序准则是：先进入的节点排在前面，后进入的节点排在后面。宽度优先算法如下： 把

2、初始结点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; ty

3、pedef 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 i

4、sEmptyOfOPEN() /open表是否为空for (int i = 0; i (); 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(os

5、tream& os, Node& node) for (int i = 0; i ROW; i+) for (int j = 0; j COL; j+) os ij ; os endl; return os; void PrintSteps(int index, vector& rstep_v)/输出每一个遍历的节点 深度遍历 back(node_vindex); index = node_vindex.index; while (index != 0) back(node_vindex); index = node_vindex.index; for (int i=()-1;i=0;i-)/

6、输出每一步的探索过程cout Step () - 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+) ij = node_vindex.digitij; int GetMinNode() /找到最小的节点的位置即最优节点int dist = MAXNUM; int loc; / the location of minim

7、ize node for (int i = 0; i (); 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;i();i+) if (isEqual(i, ) return false; return true; int Distance(Node& node, int digitC

8、OL) 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 (ij = digitkl) distance += abs(i - k) + abs(j - l); flag = true; break; else flag = false; if(flag) break; return distance; int MinDistance(int a,int

9、 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(xy, x - 1y); if (isExpandable(node_up) dist_up = Distance(node_up, ); = index; = dist_up; = node_vindex.dep + 1; back(node_up); Node node_down; Assign(node_down, index);/向下扩展的节点

10、int dist_down = MAXDISTANCE; if (x 0) Swap(xy, xy - 1); if (isExpandable(node_left) dist_left = Distance(node_left, ); = index; = dist_left; = node_vindex.dep + 1; back(node_left); Node node_right; Assign(node_right, index);/向右扩展的节点int dist_right = MAXDISTANCE; if (y 2) Swap(xy, xy + 1); if (isExpan

11、dable(node_right) dist_right = Distance(node_right, ); = index; = dist_right; = node_vindex.dep + 1; 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; ij = number; = 0; = 1; cout Input destin

12、ation: endl;/输入目的表for (int m = 0; m ROW; m+) for (int n = 0; n number; mn = number; (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(loc, ) vector rstep_v; cout Source: endl; cout src endl; PrintSteps(loc, rstep_v); cout Successful! endl; Cout Using (clock()-start)/CLOCKS_PER_SEC seconds. endl; break; else ProcessNode(loc); return 0;