解决8-益智游戏
解决8-益智游戏
提问于 2013-03-26 21:37:31
我正试着用C++编写一个包含8个益智游戏的解算器，但我在做的时候遇到了很多问题。该程序目前正在工作，但它需要太多的步骤来解决这个难题。我的意思是，有时它可以找到最优解，有时它需要400步才能解决它。我的主要疑问如下..假设我有这样的图表(这只是一个草稿)：
我使用曼哈顿距离作为启发式函数。在第一步之后，我们有了两个状态，其中f(n)=5，所以我扩展了树。在展开后，我仍然得到了f(n)=2的两个状态。这是我的疑问。我是否仍然需要扩展树，直到得到唯一的最低f(n)？
提前感谢！
回答 2
Stack Overflow用户
回答已采纳
发布于 2013-03-27 05:04:16
我还需要展开树吗
你不能贪婪地解决这个难题:总是选择启发式值较低的分支并不会每次都引导你找到最终解。因此，您必须保留其他状态以进行回溯。展开它们的顺序，无论是简单的BFS还是基于启发式的A*，都由您决定。
Stack Overflow用户
发布于 2013-04-03 17:49:59
here您可以找到使用A*算法查找从初始状态到目标状态的最短路径的处理小程序。applet中的代码是免费提供的。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/15638450
复制相关文章
相似问题
腾讯云开发者
