用盲目搜索技术解决八数码问题(8页).doc
-用盲目搜索技术解决八数码问题-第 8 页用盲目搜索技术解决八数码问题题目在3×3的棋盘，有八个棋子，每个棋子上标有1至8的某一数字，不同棋子上标的数字不相同。棋盘上还有一个空格，与空格相邻的棋子可以移到空格中。要解决的问题是：任意给出一个初始状态和一个目标状态，找出一种从初始转变成目标状态的移动棋子步数最少的移动步骤。算法流程使用宽度优先搜索从初始节点开始，向下逐层对节点进形依次扩展，并考察它是否为目标节点，再对下层节点进行扩展（或搜索）之前，必须完成对当层的所有节点的扩展。再搜索过程中，未扩展节点表OPEN中的节点排序准则是：先进入的节点排在前面，后进入的节点排在后面。宽度优先算法如下： 把初始结点S0放入OPEN表中 若OPEN表为空，则搜索失败，问题无解 取OPEN表中最前面的结点N放在CLOSE表中，并冠以顺序编号n 若目标结点，则搜索成功，问题有解 若N无子结点，则转2 扩展结点N，将其所有子结点配上指向N的放回指针，依次放 入OPEN表的尾部，转2源程序#include <iostream> #include <ctime> #include <vector> 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> node_v; / store the nodes存储节点bool isEmptyOfOPEN() /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<<(ostream& 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<Node>& 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-)/输出每一步的探索过程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 minimize 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 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 (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 b) return (a<b?a:b); void ProcessNode(int index) int x, y; bool flag; for (int i = 0; i < ROW; i+) for (int j = 0; j < COL; j+) if (node_vindex.digitij = 0) x =i; y = j; flag = true; break; else flag = false; if(flag) break; Node node_up; Assign(node_up, index);/向上扩展的节点int dist_up = MAXDISTANCE; if (x > 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);/向下扩展的节点int dist_down = MAXDISTANCE; if (x < 2) Swap(xy, x + 1y); if (isExpandable(node_down) dist_down = Distance(node_down, ); = index; = dist_down; = node_vindex.dep + 1; back(node_down); Node node_left; Assign(node_left, index);/向左扩展的节点 int dist_left = MAXDISTANCE; if (y > 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 (isExpandable(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 < COL; j+) cin >> number; ij = number; = 0; = 1; cout << "Input destination:" << endl;/输入目的表for (int m = 0; m < ROW; m+) for (int n = 0; n < COL; n+) cin >> number; mn = number; (src);/在容器的尾部加一个数据cout << "Search." << endl; clock_t start = clock(); while (1) if (isEmptyOfOPEN() cout << "Cann't solve this statement!" << endl; return -1; else int loc; / the location of the minimize node最优节点的位置 loc = GetMinNode(); if(isEqual(loc, ) vector<Node> 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;
