,因为我们假设可以独立移动一个方块到我们想要的位置,而暂不考虑会移到其他方块的问题。
给我们一群合理的启发式函式h1(n),h2(n),...,hi(n),而函式h(n) = max{h1(n),h2(n),...,hi(n)}则是
个可预测这些函式的启发式函式。
一个在1993年由A.E. Prieditis写出的程式ABSOLVER就运用了这些技术,这程式可以自动为问题产生启发
式算法。ABSOLVER为8-puzzle产生的启发式算法优于任何先前存在的!而且它也发现了第一个有用的解魔
术方块的启发式程式。
4.2、启发式算法对运算效能的影响
任何的搜寻问题中,每个节点都有b个选择以及到达目标的深度d,一个毫无技巧的算法通常都要搜寻bd个
节点才能找到答案。
启发式算法借由使用某种切割机制降低了分叉率(branching factor)以改进搜寻效率,由b降到较低的b。分叉率可以用来定义启发式算法的偏序关系,例如:若在一个n节点的搜寻树上,
h1(n)的分叉率较h2(n)低,则 h1(n) < h2(n)。
启发式为每个要解决特定问题的搜寻树的每个节点提供了较低的分叉率,因此它们拥有较佳效率的计算能力。
完。