一、实验目的 1、 熟悉和掌握启发式搜索的定义、估价函数和算法过程。 2、 利用 A*算法求解 N 数码难题，理解求解流程和搜索顺序。 二、实验内容 以八数码为例实现 A 或 A*算法 。 1、分析算法中的OPEN表CLOSE表的生成过程。 1）建立一个队列，计算初始结点的估价函数 f，并将初始结点入队，设置队列头和尾指针。 2）取出队列头（队列头指针所指）的结点，如果该结点是目标结点，则输出路径，程序结束。否则对结点进行扩展。 3）检查扩展出的新结点是否与队列中的结点重复，若与不能再扩展的结点重复（位于队列头指针之前），则将它抛弃；若新结点与待扩展的结点重复（位于队列头指针之后），则比较两个结点的估价函数中 g 的大小，保留较小 g 值的结点。跳至第五步。 4）如果扩展出的新结点与队列中的结点不重复，则按照它的估价函数 f 大小将它插入队列中的头结点后待扩展结点的适当位置，使它们按从小到大的顺序排列，最后更新队列尾指针。 5）如果队列头的结点还可以扩展，直接返回第二步。否则将队列头指针指向下一结点，再返回第二步。 2、分析估价函数对搜索算法的影响。 3、分析启发式搜索算法的特点。 广度优先搜索和双向广度优先搜索都属于盲目搜索，这在状态空间不大的情况下是很合适的算法，可是当状态空间十分庞大时，它们的效率实在太低，往往都是在搜索了大量无关的状态结点后才碰到解答，甚至更本不能碰到解答。 搜索是一种试探性的查寻过程，为了减少搜索的盲目性引，增加试探的准确性，就要采用启发式搜索了。所谓启发式搜索就是在搜索中要对每一个搜索的位置进行评估，从中选择最好、可能容易到达目标的位置，再从这个位置向前进行搜索，这样就可以在搜索中省略大量无关的结点，提高了效率。 启发式函数选取为：f*(n)=g*(n)+ h*(n) 其中： g*(n)是搜索树中节点n的深度 h*(n)用来计算对应于节点n的数据中错放的棋子个数。 三、实验结果 四、程序 function [a1,b1]=shang(a) [x,y]=find(a==0); a1=a; a1(x,y)=a(x-1,y); a1(x-1,y)=0; b1=zhao(a1); %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% function [a1,b1]=xia(a) [x,y]=find(a==0); a1=a; a1(x,y)=a(x+1,y); a1(x+1,y)=0; b1=zhao(a1); %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% function [a1,b1]=zuo(a) [x,y]=find(a==0); a1=a; a1(x,y)=a(x,y-1); a1(x,y-1)=0; b1=zhao(a1); %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%...
