14启发式图搜索内容摘要：
5 6 7 1 2 3 8 4 5 6 7 (2) (4) 1 2 3 8 4 5 6 7 1 2 3 8 4 5 6 7 (3) (4) 1 2 3 8 4 5 6 7 (1) 8 1 3 2 4 5 6 7 1 2 3 8 4 5 6 7 (0) (2) 八数码魔方的最佳优先搜索树 1 2 3 8 4 6 (4) ⑦ 搜索得到的路径如黄线所示 • 本题采用了简单的估价函数 f(n)=W(n) 其中： W(n)用来计算对应于节点 n的数据库中错放的棋子个数。 因此 ， 初始节点棋局 的 f(n)值等于 4。 1 2 3 8 4 5 6 7 • 第 ② 步有三种情况 ,我们选择其中f(n)最小的 : • 其它依次类推 .最后用了 7步得出了结果 . 1 2 3 8 4 5 6 7 1 2 3 8 4 5 6 7 1 2 3 8 4 5 6 7 (3) (5) (5) 3. A算法 • 最佳优先算法有时无法得到最优解，因为它的估价函数 f的选取时，忽略了从初始节点到目前节点的代价值。 所以，可考虑每个节点 n的估价函数 f(n)分为两个分量：从起始节点到节点 n的代价 g(n)以及从节点 n到达目标节点代价的估算值 h(n)。 f(n)=g(n)+h(n) • f(n)——节点 n的估价函数； g(n)——评价函数， 从初始节点 S到 n节点的实际代价； h(n)——启发函数， 从 n到目标节点 Sg最佳路径的估计 代价。 • 这里 h(n)体现了搜索的启发信息，因为 g(n)是已知的。 如果说详细点， g(n)代表了搜索的宽度优先趋势。 但是当 h(n)g(n) 时，可以省略 g(n),而提高效率。 A算法的引入： g(n)的计算方法： • g(n)就是在搜索树中从 S到 n。阅读剩余 0%
本站所有文章资讯、展示的图片素材等内容均为注册用户上传(部分报媒/平媒内容转载自网络合作媒体)，仅供学习参考。
用户通过本站上传、发布的任何内容的知识产权归属用户或原始著作权人所有。如有侵犯您的版权，请联系我们反馈本站将在三个工作日内改正。