中期进展报告 ————九宫格重移——搜索 成员：余

俊2014704161 张向量2014704163 赵亮波2014704164

1. A*算法的学习

A* 算法实际是一种启发式搜索，所谓启发式搜索，就是利用一个估价函数评估每次的的决策的价值，决定先尝试哪一种方案，这样可以极大的优化普通的广度优先搜索。一般来说，从出发点(A)到目的地(B)的最短距离是固定的，我们可以写一个函数 judge() 估计 A 到 B 的最短距离，如果程序已经尝试着从出发点 A 沿着某条路线移动到了 C 点, 那么我们认为这个方案的 A B 间的估计距离为 A 到 C 实际已经行走了的距离 H 加上用 judge() 估计出的 C 到 B 的距离。

如此，无论我们的程序搜索展开到哪一步，都会算出一个评估值，每一次决策后，将评估值和等待处理的方案一起排序，然后挑出待处理的各个方案中最有可能是最短路线的一部分的方案展开到下一步，一直循环到对象移动到目的地，或所有方案都尝试过却没有找到一条通向目的地的路径则结束。 A*算法是一个可采纳的最好优先算法。A*算法的估价函数可表示为： f'(n) = g'(n) + h'(n)

这里，f'(n)是估价函数，g'(n)是起点到终点的最短路径值，h'(n)是n到目标的最断路经的启发值。由于这个f'(n)其实是无法预先知道的，所以我们用前面的估价函数f(n)做近似。g(n)代替g'(n)，但g(n)>=g'(n)才可（大多数情况下都是满足的，可以不用考虑），h(n)代替h'(n)，但h(n)<=h'(n)才可。可以证明应用这样的估价函数是可以找到最短路径的，也就是可采纳的。 2. A*算法的伪代码

创建两个表，OPEN表保存所有已生成而未考察的节点，CLOSED表中记录已访问过的节点。

算起点的估价值;

将起点放入OPEN表;

while(OPEN!=NULL)

{

从OPEN表中取估价值f最小的节点n;

if(n节点==目标节点){

break;

}

for(当前节点n 的每个子节点X)

{

算X的估价值;

if(X in OPEN)

{

if( X的估价值小于OPEN表的X估价值 ){

把n设置为X的父亲;

更新OPEN表中的估价值; //取最小路径的估价值

}

}

if(X inCLOSE) {

if( X的估价值小于CLOSE表的X估价值 ){

把n设置为X的父亲;

将该节点从close表中除去

把X节点放入OPEN //取最小路径的估价值

}

}

if(X not inboth){

把n设置为X的父亲;

求X的估价值;

并将X插入OPEN表中; //升序排列open

}

}//end for

将n节点插入CLOSE表中;

按照估价值将OPEN表中的节点排序; //实际上是比较OPEN表内节点f的大小，从最小路径的节点向下进行。

}//end while(OPEN!=NULL)

保存路径，即从终点开始，每个节点沿着父节点移动直至起点，这就是你的路径。

3. 建立合适的启发式

A*算法有个计算公式 f(x) = g(x)+h(x)

其中g(x)为从起始状态到当前状态所消耗的步数，h(x)为一个启发值，估算从当前状态到目标状态所需的步数，一般h(x)小于等于实际需要步数为好，这样不会将最优解忽略，因为h(x)和解空间有一些关系，如果h(x)设置的比实

际需要的步数多，那么解空间就有可能将最优解忽略。举个例子吧，宽度优先搜索就是h(x)=0带来的效果，深度优先搜索就是g(x)=0带来的效果，不过h(x)距离h*(x)[实际需要的步数]的程度不能过大，否则h(x)就没有过强的区分能力，算法效率并不会很高。对一个好的h(x)的评价是：h(x)在h*(n)[实际需要的步数]的下界之下，并且尽量接近h*(n)[实际需要的步数].

那么8数码问题g(x) 为经过上下左右移动空格附近的数字来得到新状态所需步数，h(x)为当前状态与目标状态的距离，就是所有不在目标位置的数字总和，必然小于h*(x)。

4. 下一步工作

收集资料进一步完善八数码的规则库，结合上述算法将源代码尽量完善，运用其他方法来提高效率。

 

第二篇：20xx级中期进展报告

中南大学研究生学位论文中期进展报告