广度优先搜索可能会导致内存不够用采用启发式搜索启.doc

上人工智能课的时候 老师布置了一道编程题要我们解决八数码问题,广度优先搜索可能会导致内存不够用 , 采用启发式搜索 ,启发函数为 f(x)=g(x)+h(x);g(x) 为该结点不同于目标结点的个数,h(x) 为该结点的深度 , 选择那 f(x) 结点最小的那个结点进行扩展 , 引入了一个 扩展数组4( 因为扩展的结点最多只有 4 个 ), 该数组保存着某个结点的 0 点向各个方向的扩展的结点对象 ,然后对该扩展数组进行分析 , 利用启发函数在进行递归扩展 .以下是我的算法基本流程,其中还有很多地方可以做的更好, 偶没有时间在做下去了,原程序放在这里只是记录一下我的思考的过程,希望同仁们能批评指正.:)扩展数组 4;/全局变量int f =0;/ 扩展数组的下标初始化 open 表;初始化 closed 表;扩展并查找 ( 结点 n)found = false; while(!found)if( 扩展 (n) = tru