人工智能A星算法(C++).docx

1、#include#include#include#includeusing namespace std;#define M 3class MatrixNode/ 定义 MatrixNode 类public:int m;/ 在位个数int d;/ 深度int p;/ 牌与其目标位置直接步数之和int f;/f=d+p ，估价函数int placeMM;/ 当前矩阵int placetrueMM; /目标矩阵int kong_x;/ 空位的横坐标int kong_y;/ 空位的纵坐标/-public:MatrixNode();MatrixNode start(MatrixNode M_Matrix

2、);/ 初始矩阵int TruePlace(MatrixNode T_place );/ 查找在位数int p_place(MatrixNode P_place);/ 坐标差绝对值之和int f_kongx(MatrixNode find_kongx);/ 找出空格的横坐标int f_kongy(MatrixNode find_kongy);/ 找出空格的纵坐标bool solved(MatrixNode M_Matrix);/ 判断是否有解 ,奇偶性相同则有解，否则无解MatrixNode up_move(MatrixNode M_Matrix);/ 空格上移MatrixNode down_

3、move(MatrixNode M_Matrix);/ 空格下移MatrixNode left_move(MatrixNode M_Matrix);/ 空格左移MatrixNode right_move(MatrixNode M_Matrix);/ 空格右移MatrixNode updata_m(MatrixNode M_Matrix);/ 移动后更新状态MatrixNode parents(deque ilist,MatrixNode M_Matrix);/ 找到该节点的父亲;/=MatrixNode:MatrixNode() / 目标矩阵 placetrue00 = 1;placetrue

4、01 = 2;placetrue02 = 3;placetrue10 = 8;placetrue11 = -1;placetrue12 = 4;placetrue20 = 7;placetrue21 = 6;placetrue22 = 5;/-MatrixNode MatrixNode:start(MatrixNode M_Matrix)/ 初始矩阵cout 请按如下格式输入初始矩阵(空位用0 表示 )：endl;cout1 2 3n4 5 6n7 0 8endl;cout 八数码的初始状态如下: endl;for(int a = 0;a M;a+)for(int b = 0;b M_Matr

5、ix.placeab;M_Matrix.d = 0;M_Matrix = M_Matrix.updata_m( M_Matrix );M_Matrix.d=M_Matrix.d-1;/ 初始更新时深度多加1，应该减去M_Matrix.f=M_Matrix.f-1;return M_Matrix;/-bool solved(MatrixNode M_Matrix)/ 判断是否可解int num8;int target8;int a=0;int b=0;for(int m = 0;m M;m+)for(int n = 0;n M;n+ )if(M_Matrix.placemn != 0)/ 不考虑

6、空格numa+=M_Matrix.placemn;if(M_Matrix.placetruemn != -1)targetb+=M_Matrix.placetruemn;int i,j;int count_num = 0,count_target = 0;for (i = 0;i (8-1);i+)for (j = i+1;j 8;j+)if(numj numi)count_num+;if(targetjtargeti)count_target+;if(count_num%2 = 0&count_target%2 = 0)|(count_num%2 = 1&count_target%2 = 1

7、)return true;elsereturn false;/-int MatrixNode:TruePlace(MatrixNode T_place ) T_place.m = 0;int NumT_place = 0;/查找在位数for(int i = 0;i M;i+)for(int j = 0;j M;j+ )if( T_place.placeij = placetrueij) T_place.m = T_place.m + 1;NumT_place = NumT_place + 1;return NumT_place;/-int MatrixNode:p_place(MatrixNo

8、deP_place)/ 坐标差的绝对值之和P_place.p = 0;int num = 0;for(int Pa = 0;Pa M;Pa+)for(int Pb = 0;Pb M;Pb+)if(P_place.placePaPb = 1)P_place.p = P_place.p+ (abs(Pa - 0)+abs(Pb - 0);if(P_place.placePaPb = 2)P_place.p = P_place.p+ (abs(Pa - 0)+abs(Pb - 1);if(P_place.placePaPb = 3)P_place.p = P_place.p+ (abs(Pa - 0

9、)+abs(Pb - 2);if(P_place.placePaPb = 4)P_place.p = P_place.p+ (abs(Pa - 1)+abs(Pb - 2);if(P_place.placePaPb = 5)P_place.p = P_place.p+ (abs(Pa - 2)+abs(Pb - 2);if(P_place.placePaPb = 6)P_place.p = P_place.p+ (abs(Pa - 2)+abs(Pb - 1);if(P_place.placePaPb = 7)P_place.p = P_place.p+ (abs(Pa - 2)+abs(Pb

10、 - 0);if(P_place.placePaPb = 8)P_place.p = P_place.p+ (abs(Pa - 1)+abs(Pb - 0);num =P_place.p;return num;/-int MatrixNode:f_kongx(MatrixNode find_kongx)int num;for(int i = 0;i M;i+)for(int j = 0;j M;j+)if(find_kongx.placeij = 0)num = i;/ 返回空格横坐标return num;/-int MatrixNode:f_kongy(MatrixNode find_kon

11、gy)int num;for(int i = 0;i M;i+)for(int j = 0;j M;j+)if(find_kongy.placeij = 0)num = j;/ 返回空格纵坐标return num;/-MatrixNode MatrixNode:up_move(MatrixNode M_Matrix)/ 空格上移int num;/num为交换的中间变量MatrixNode up_m = M_Matrix;num = up_m.placeup_m.kong_xup_m.kong_y;up_m.placeup_m.kong_xup_m.kong_y=up_m.placeup_m.k

12、ong_x-1up_m.kong_y ;up_m.placeup_m.kong_x - 1up_m.kong_y = num;up_m = up_m.updata_m(up_m);return up_m;/-MatrixNode MatrixNode:down_move(MatrixNode M_Matrix)/ 空格下移int num;MatrixNode up_m = M_Matrix;num = up_m.placeup_m.kong_xup_m.kong_y;up_m.placeup_m.kong_xup_m.kong_y=up_m.placeup_m.kong_x1up_m.kong

13、_y ;+up_m.placeup_m.kong_x + 1up_m.kong_y = num;up_m = up_m.updata_m(up_m);return up_m;/-MatrixNode MatrixNode:left_move(MatrixNode M_Matrix)/ 空格左移int num;MatrixNode up_m = M_Matrix;num = up_m.placeup_m.kong_xup_m.kong_y;up_m.placeup_m.kong_xup_m.kong_y=up_m.placeup_m.kong_x up_m.kong_y - 1 ;up_m.pl

14、aceup_m.kong_x up_m.kong_y - 1 = num;up_m = up_m.updata_m(up_m);return up_m;/-MatrixNode MatrixNode:right_move(MatrixNode M_Matrix)/ 空格右移int num;MatrixNode up_m = M_Matrix;num = up_m.placeup_m.kong_xup_m.kong_y;up_m.placeup_m.kong_xup_m.kong_y=up_m.placeup_m.kong_x up_m.kong_y + 1 ;up_m.placeup_m.ko

15、ng_x up_m.kong_y + 1 = num;up_m = up_m.updata_m(up_m);return up_m;/-MatrixNode MatrixNode:updata_m(MatrixNode M_Matrix)MatrixNode up_m = M_Matrix;/ 移动后更新状态up_m.m = up_m.TruePlace(up_m);up_m.p = up_m.p_place(up_m);up_m.d = M_Matrix.d+1;/查找在位数/ 距离和/ 深度加 1up_m.f = up_m.p + up_m.d;up_m.kong_x = up_m.f_k

16、ongx(up_m);/ 估价值/ 找出空格的横坐标up_m.kong_y = up_m.f_kongy(up_m);/ 找出空格的纵坐标return up_m;/-boolfather(deque ilist,MatrixNode M_Matrix)MatrixNode M_Matrix1 = ilist.front();MatrixNode up_m;int m;up_m = M_Matrix1.up_move(M_Matrix1);m = 0;for(int a1 = 0;a1 M;a1+)for(int b1 = 0;b1 M;b1+ )if(up_m.placea1b1 = M_Ma

17、trix.placea1b1)m+;/ 寻找父节点if(m = 9)return true;up_m=M_Matrix1.down_move(M_Matrix1);m = 0;for(int a2 = 0;a2 M;a2+)for(int b2 = 0;b2 M;b2+ )if(up_m.placea2b2 = M_Matrix.placea2b2)m+;if(m = 9)return true;up_m=M_Matrix1.left_move(M_Matrix1);m = 0;for(int a3 = 0;a3 M;a3+)for(int b3 = 0;b3 M;b3+ )if(up_m.p

18、lacea3b3 = M_Matrix.placea3b3)m+;if(m = 9)return true;up_m=M_Matrix1.right_move(M_Matrix1);m = 0;for(int a4 = 0;a4 M;a4+)for(int b4 = 0;b4 M;b4+ )if(up_m.placea4b4 = M_Matrix.placea4b4)m+;if(m = 9)return true;elsereturn false;/-void printMatrix(const MatrixNode Matrix)for(int i = 0;i M;i+)for(int j

19、= 0;j M;j+ )coutMatrix.placeij,;/ 输出矩阵coutendl;coutendl;/-bool less_f(const MatrixNode M_Matrix1, const MatrixNode M_Matrix2) return M_Matrix1.f M_Matrix2.f;/- -bool lookout(deque ilist, MatrixNode M_Matrix)/ 检查新生成的节点是否已扩展deque:iterator Vi = ilist.begin();int i,j,m;while(Vi != ilist.end()m=0;for(i =

20、 0;i M;i+)for(j = 0;j M;j+ )if(*Vi).placeij = M_Matrix.placeij)m+;if(m = 9)return true;Vi+;/ 不是新扩展的return false;/ 是新扩展的/= void main()int step = 0;MatrixNode mat;MatrixNode mat_trn;MatrixNode mat_trn1;MatrixNode mat_trn2;MatrixNode mat_trn3;MatrixNode mat_trn4;MatrixNode parent;mat = mat.start(mat);d

21、eque openlist;openlist.push_front(mat);deque closedlist;if(solved(mat) = false)cout 无法找到路径!= 1)mat_trn1 = mat_trn1.up_move(mat_trn1);if(lookout(openlist,mat_trn1)=false&lookout(closedlist,mat_trn1)=false)/ 检查新节点是否已扩展openlist.push_front(mat_trn1);/-向下移mat_trn2 = mat_trn;if(mat_trn2.f_kongx(mat_trn2) = 1)mat_trn3 = mat_trn3.left_move(mat_trn3);if(lookout(openlist,mat_