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

1、#include#include#include#includeusing namespace std;#define M 3 class 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

2、 M_Matrix); /初始矩阵 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); /空格上移 M

3、atrixNode down_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() /目标矩阵 placet

4、rue00 = 1; placetrue01 = 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

5、 M;a+) for(int b = 0;b M_Matrix.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 =

6、 0;n M;n+ ) if(M_Matrix.placemn != 0) /不考虑空格 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_t

7、arget%2 = 0)|(count_num%2 = 1&count_target%2 = 1)return true; else return 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

8、 + 1; return NumT_place; /- int MatrixNode:p_place(MatrixNode P_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

9、(Pb - 1); if(P_place.placePaPb = 3) P_place.p = P_place.p+ (abs(Pa - 0)+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

10、(Pb - 1); if(P_place.placePaPb = 7) P_place.p = P_place.p+ (abs(Pa - 2)+abs(Pb - 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+)

11、if(find_kongx.placeij = 0) num = i; return num; /- int MatrixNode:f_kongy(MatrixNode find_kongy) /返回空格纵坐标 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

12、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 - 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

13、_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 + 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:left_move(MatrixNode M_Matrix) /空格左移 int num; MatrixNode up_m

14、 = 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.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_

15、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.kong_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_M

16、atrix; up_m.m = up_m.TruePlace(up_m); / 查找在位数 up_m.p = up_m.p_place(up_m); /距离和 up_m.d = M_Matrix.d+1; /深度加1 up_m.f = up_m.p + up_m.d; /估价值 up_m.kong_x = up_m.f_kongx(up_m); /找出空格的横坐标 up_m.kong_y = up_m.f_kongy(up_m); /找出空格的纵坐标 return up_m; /- bool father(deque ilist,MatrixNode M_Matrix) /寻找父节点 Matr

17、ixNode 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_Matrix.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

18、= 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.placea3b3 = M_Matrix.placea3b3) m+; if(m = 9) return true; up_m=M_Matrix1.right_move(M_Matrix1); m = 0; for(int a4

19、= 0;a4 M;a4+) for(int b4 = 0;b4 M;b4+ ) if(up_m.placea4b4 = M_Matrix.placea4b4) m+; if(m = 9) return true; else return false; /- void printMatrix(const MatrixNode Matrix) /输出矩阵 for(int i = 0;i M;i+) for(int j = 0;j M;j+ ) coutMatrix.placeij,; coutendl; coutendl; /- bool less_f(const MatrixNode M_Mat

20、rix1, 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 = 0;i M;i+) for(j = 0;j M;j+ ) if(*Vi).placeij = M_Matrix.placeij) m+; if(m = 9) retur

21、n 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); deque openlist;openlist.push_front(mat); deque closedlist;if(solved(mat) =

22、 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,m