启发式算法的新算法

2025-03-12 09:01:05

推荐回答（1个）

回答1：

如何找到一个分叉率较少又通用的合理启发式算法，已被人工智能社群深入探究过。他们使用几种常见技术：
部分问题的解答的代价通常可以评估解决整个问题的代价，通常很合理。例如一个10-puzzle拼盘，解题的代价应该与将1到5的方块移回正确位置的代价差不多。通常解题者会先建立一个储存部份问题所需代价的模式数据库(pattern database)以评估问题。解决较易的近似问题通常可以拿来合理评估原先问题。例如曼哈顿距离是一个简单版本的n-puzzle问题，因为我们假设可以独立移动一个方块到我们想要的位置，而暂不考虑会移到其他方块的问题。给我们一群合理的启发式函式h1(n),h2(n),...,hi(n)，而函式h(n) = max{h1(n),h2(n),...,hi(n)}则是个可预测这些函式的启发式函式。一个在1993年由A.E. Prieditis写出的程式ABSOLVER就运用了这些技术，这程式可以自动为问题产生启发式算法。ABSOLVER为8-puzzle产生的启发式算法优于任何先前存在的！而且它也发现了第一个有用的解魔术方块的启发式程式。