3A星算法试验报告

1、人工智能实验报告实验二A舟算法实验I、实验目的：熟悉和掌握启发式搜索的定义、估价函数和算法过程，并利用A*算法求解N数码难题，理解求解流程和搜索顺序。二、实验原理：A*算法是一种启发式图搜索算法，其特点在于对估价函数的定义上。对于一般的 启发式图搜索，总是选择估价函数f值最小的节点作为扩展节点。因此，f是根据需要找 到一条最小代价路径的观点来估算节点的，所以，可考虑每个节点n的估价函数值为两 个分量：从起始节点到节点n的实际代价以及从节点n到达目标节点的估价代价o、实验内容：1 参考A*算法核心代码，以8数码问题为例实现A*算法的求解程序（编程语 言不限），要求设计两种不同的估价函数。2在求解

2、8数码问题的/V算法程序中，设置相同的初始状态和目标状态，针对不同的估 价函数，求得问题的解，并比较它们对搜索算法性能的影响，包括扩展节点数、生成节 点数等。3对于8数码问题，设置与上述2相同的初始状态和目标状态，用宽度优先搜 索算法 （即令估计代价h （n）二0的X算法）求得问题的解，以及搜索过程中的扩展节点 数、生成节点数。4上交源程序四、实验结果：1 A*算法求解框图:开始)入袁中梅耳点加人rlost 表辛嗚与傅节Q M 近的不在dotr表 申的节申ill人到 超一个毂申潭尢的节戌没有背径對这弊 点理累矢敢结柬j找到业逐坯程和妙2 在求解8数码问题的A*算法程序中，设置相同的初始状态和目

3、标状态，针 对不同的估价函数，求得问题的解，并比较它们对搜索算法性能的影响，包括扩展节点数、 生成节点数等。：int calw(string s) 计算该状态的不在位数h(n)int re=0;for(i nt i=0;iv9;i+) if(si!=ti) re+;/ 取一格局与目的格局位置不符的数码数目return re;幘输入测试的组数1Case 1:456012378原图：4 5 61 23 7 8移动过程：Step 1 4 5 63 127 8Step 2 :4 5 63 1278Step 3:4 5 63 127 8Step 22：138 2 47 6 5Step 23:12 38

4、47 6 5搜索节点数：8423b按任意键继续：int calw(string s) 计算该状态的不在位数h(n)int re=O, i;int ss92;for(i = 0;i9; +i) /计算各数码移到目的位置所需移动的距离总和sssi - 480 = i / 3;sssi - 481 = i % 3;for(i = 0; i 9; +i)re += (abs(ssi0 - sourcei0) + abs(ssi1-sourcei1);return re;:int calw(string s) 计算该状态的不在位数h(n)return 0; /宽度优先鹽入測试组数JCas el：输入0福

5、数码：456012378原图：456123 ?8Step 20：13 48 27 6 5移动过程:Step 21；1 38 2 47 6 SStep 1:4 563 1278Step 22：138 2 47 6 5Step 2 :4 563 127SStep 23:187Step 3 ; 4 5 3 1278歉斃蠶:115532情按任意键继续.3 根据宽度优先搜索算法和A*算法，分析启发式搜索的特点。启发式搜索算法使得搜索的效率好几倍地提高。而不同的启发式搜索算 法差 异也较大。总之启发式搜索算法是由h(n)决定的，好的估价函数将决定算法性能的 好坏。五、实验心得与体会通过这次实验，使我对启发式搜索算法有了更进一步的理解，特别是估计函数h(n)所起到的巨大重用