价函数,它用来评价子结点的好坏,因为准确评价是不可能的,所以称为估值。
这就是我们所谓的有信息搜索。
如果估值函数只考虑结点的某种性能上的价值,而不考虑深度,比较有名的就是有序搜索(Ordered-Search),它着重看好能否找出解,而不看解离起始结点的距离(深度)。
如果估值函数考虑了深度,或者是带权距离(从起始结点 ,那就是 A如果不考虑深度,就是说不要求最少步数,移动一步到目标结点的距离加权和)就相当于向后多展开一层结点,深度多算一层,如果要求最少步数,那就需要用 A。
简单的来说 A就是将估值函数分成两个部分,一个部分是路径价值,另一个部分是一般性启发价值,合在一起算估整个结点的价值, 考虑到八数码问题的特点,在本实验中使用 A算法求解。
A搜索是一种效的搜索算法,它把到达节点的耗散 gn和从该节点到目标节点的消耗 hn结合起来对节点进行评价:fngnhn。
当 hn是可采纳时,使用 Tree-Search 的 A算法将是最优的。
2.2 算法伪代码 算法的功能:产生 8 数码问题的解由初始状态到达目标状态的过程) 输入:初始状态,目标状态 输出:从初始状态到目标状态的一系列过程 算法描述: Begin: 读入初始状态和目标状态,并计算初始状态评价函数值 f; 根据初始状态和目标状态,判断问题是否可解; If问题可解 把初始状态假如 open 表中; While(未找到解状态表非空) ①在 open 表中找到评价值最小的节点,作为当前结点; ②判断当前结点状态和目标状态是否一致,若一致,跳出循环;否则跳转 到③; ③对当前结点,分别按照上、下、左、右方向移动空格位置来扩展新的状 态结点,并计算新扩展结点的评价值 f 并记录其父节点; ④对于新扩展的状态结点,判断其是否重复,若不重复,把其加入到 open 表中; ⑤把当前结点从 open 表中移除; End while End if 输出结果; End 算法流程如下: 开始 读入棋局初始状态 否 是否可解 是 初始状态加入 open 表 在 open 表中找到评价值最小的节点,作为当前结点 是 是目标节点 否 扩展新状态,把不重复的新状态加入 open 表中 当前结点从 open 表移除 输出结果 结束3 算法实现3.1 实验环境与问题规模实验环境:硬件环境:PC 机。
软件环境:Windows XP VC 6.0。
问题规模:2)问题规模 对于任一给定可解初始状态,状态空间有 9/2181440 个状态;当采用不在位棋子 数作为启发函数时,深度超过 20 时,算法求解速度缓慢;3.2 数据结构 static int target9123804765 全局静态变量,表示目标状态class eight_numprivate: int num9 定义八数码的初始状态 int not_in_position_num 定义不在正确位置八数码的个数 int deapth 定义了搜索的深度 int eva_function 评价函数的值,每次选取最小的进行扩展public: eight_num parent 指向节点的父节点 eight_num leaf_next 指向 open 表的下一个节点 eight_num leaf_pre 指向 open 表的前一个节点 初始状态的构造函数 eight_numint init_num9 eight_numint num1int num2int num3int num4int num5int num6int num7int num8intnum9eight_numvoid 计算启发函数 gn的值void eight_num::cul_paravoid显示当前节点的状态void eight_num::show复制当前节点状态到一个另数组中void eight_num::get_numbers_toint other_num9设置当前节点状态欲设置的状态记录的 other 数组中void eight_num::set_numint other_num9eight_num eight_num::operatoreight_num another_8numeight_num eight_num::operatorint other_num9int eight_num::operatoreight_num another_8numint eight_num::operatorint other_num9空格向上移int move_upint num9空格向下移int move_downint num9空格向左移int move_leftint num9空格向右移int move_rightint num9判断可否解出int icansolveint num9int target9判断有无重复int existedint num9eight_num where寻找估价函数最小的叶子节点eight_num find_OK_leafeight_num start3.3 实验结果h: 启发函数(不在位将牌数) 初始状态 目标状态 是否有解 启发函数 用时 步数 321 123 否 h -- 804 804 765 765 104 123 是 h 2875ms