算法设计与分析 课件 第七章 分支限界 7.3.3 八数码问题.ppt

计算机算法设计与分析第7章分支限界法7.3.3八数码问题280163754123804765初始状态目标状态队列式分支限界法712345896101617182015191112131421目标2831047652031847652830147652831407650231847652301847651230847651238047651237841652341807650832147652837140652801437652831457608032147652837146052081437652831457062322283164705283164075283164750283064175283160754启发式函数：f(x)=g(x)+h(x)①从起始结点到结点x的已经损耗值g(x)；②从结点x到达目标的期望耗损值h(x)。我们选择根结点到当前结点x的深度（已走过的步数）作为g(x)。将当前结点x的数字与目标结点数字进行比较，统计当前结点x与目标结点的数字在位置上匹配的个数，越多表示距离目标越近。我们选择当前结点x状态中各数字不在目标位置的个数作为h(x)。f(x)=g(x)+h(x)f(x)=g(x)+h*(x)定义h*(x)为全部不在位数字与目标位置的距离之和，再加上当前有哪些信誉好的足球投注网站深度g(x)，来优化本问题的启发式函数f(x)=g(x)+h*(x)。与A算法的h(x)比较，A*算法的h*(x)不仅考虑了不在位数字的个数，也考虑了不在位数字距离目标数字位置之间的距离（移动次数），具有更快沿着目标解路径有哪些信誉好的足球投注网站能力，有哪些信誉好的足球投注网站效率更高效。f(x)=g(x)+h*(x)