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

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

2、e start(MatrixNode 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); MatrixNode down_move(MatrixNode M_Matrix); Mat

3、rixNode left_move(MatrixNode M_Matrix); MatrixNode right_move(MatrixNode M_Matrix); MatrixNode updata_m(MatrixNode M_Matrix); / 初始矩阵 / 查找在位数 / 坐标差绝对值之和 / 找出空格的横坐标 / 找出空格的纵坐标 / 判断是否有解 ,奇偶性相同则 / 空格上移 / 空格下移 / 空格左移 / 空格右移 / 移动后更新状态 MatrixNode parents(deque ilist,MatrixNode M_Matrix); 该节点的父亲 / 找到 ; /= M

4、atrixNode:MatrixNode() placetrue00 = 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 8e

5、ndl; cout 八数码的初始状态如下 : endl; for(int a = 0;a 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

6、=0; int b=0; for(int m = 0;m M;m+) for(int n = 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(targ

7、etjtargeti) count_target+; 精选文档，供参考！ 0 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 + 1; return NumT_pla

8、ce; / 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(Pb - 1); if(P_place

9、.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(Pb - 1);

10、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+) if(find_kongx.placei

11、j = 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 up_m = M

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

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

14、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: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; 精选文档，供参考！ / 精选文档，供参考！ / 移动后更新状态 / 查找在位数 / 距离和 / 深度加 1 / 估价值 / 找出空格的横坐 / 找出空格的纵坐 Matr

16、ixNode 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; 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,Matr

17、ixNode 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_Matrix.placea1b1) m+; if(m = 9) return true; up_m=M_Matrix1.down_move(M_Matrix1); m = 0; for(int

18、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.placea3b3 = M_Matrix.placea3b3) m+; if(m = 9) return true; up_m=M_Matri

19、x1.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; 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;

20、/ 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 = 0;i M;i+) for(j = 0;j M;j+ ) if(*Vi).placeij = M_Matrix.pl

21、aceij) 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); deque 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 / 向下移 mat_trn2 = mat_trn; if(mat_trn2.f_kongx(mat_trn2) = 1) mat_trn3 = mat_trn3.left_move(mat_trn