二、 实验内容 迷宫问题可以表述为一个二维的网格，0表示点可走，1表示点不可以走，点用（x，y）表示，寻找从某一个给定的起始单元格出发， 经由行相邻或列相邻的单元格可以通过的，最终可以到达目标单元格的、所走过的单元格序列。在任一个单元格中，都只能看到与它邻近的4个单元格如果位于底边，则只有3个；
位于4个角上，则只有2个是否能通过。
A*算法是人工智能中的一种搜索算法，是一种启发式搜索算法，它不需遍历所有节点，只是利用包含问题启发式信息的评价函数对节点进行排序，使搜索方向朝着最有可能找到目标并产生最优解的方向。它的独特之处是检查最短路径中每个可能的节点时引入了全局信息，对当前节点距终点的距离做出估计，并作为评价节点处于最短路线上的可能性的度量。
A*算法中引入了评估函数，评估函数为f（n）g（n）h（n） 其中n是搜索中遇到的任意状态。gn是从起始状态到n的代价。hn是对n到目标状态代价的启发式估计。即评估函数f n 是从初始节点到达节点n 处已经付出的代价与节点n 到达目标节点的接近程度估价值的总和。
这里我们定义n点到目标点的最小实际距离为h（n）*，A*算法要满足的条件为h（n）_len_wid; _sealnew Seal*[_len1]; _mazenew unsigned char*[_len1]; forint i0;i_maze[i][j]; _seal[i][j].flagUNVISITED; _seal[i][j].pointNULL; } } cout_sx_sy_ex_ey; if_maze[_sx][_sy]1||_maze[_ex][_ey]1||bound_sx,_syfalse||bound_ex,_eyfalse { cout_G0; p_node-_x_sx; p_node-_y_sy; p_node-_Fp_node-_Hp_node-_G; _open.pushp_node; _seal[_sx][_sy].flagOPEN; _seal[_sx][_sy].pointp_node; while_open.empty { p_node_open.top; _open.pop; int xp_node-_x; int yp_node-_y; _seal[x][y].flagSEAL; forint i0;i_G1; temp-_xtx; temp-_yty; temp-_Hget_Htx,ty; temp-_Ftemp-_Gtemp-_H; _open.pushtemp; } else { Queue_Node *temp_seal[tx][ty].point; ifp_node-_G1_G { temp-_Gp_node-_G1; temp-prep_node; temp-_Ftemp-_Gtemp-_H; } } } } cout_F; } }; priority_queue _open;//最小堆开放列表 int _len,_wid;//迷宫左边长,上边宽 int _sx,_sy,_ex,_ey; Seal **_seal;//动态开辟封闭列表 unsigned char **_maze;//迷宫地图 }; int main { A_Star test; return 0; } 三、 实验目的 通过这次实验，使我对启发式搜索算法有了更进一步的理解，特别是估计函 数hn所起到的巨大重用。一个好的估计函数对于启发式搜索算法来说是十分关键的。