Peg solitare递归解
Peg solitare递归解
提问于 2015-04-20 14:29:52
每个人都知道饼干桶三角形钉纸牌游戏。你拿着一个钉子，跳到另一个洞里，目标是只剩下一个钉子。
在我的游戏板对象的代码中，我有一个sCpeg(int a, int b)函数，它可以更改您当前用于跳转的peg。我将它连接到一个moves变量来解决它。每次你改变当前的钉子并使用它来跳跃，这就算一次移动。这是一个非常基本的启发式方法，我希望它是一个搜索算法:用一个peg探索所有可能的跳转。如果未找到解决方案，请回溯，更新当前peg并重复此过程。
当我写出这个想法时，它听起来像是一个使用递归的完美例子，除了我不知道如何在这个场景中正确地使用递归。在回溯和更新当前的peg之间，我迷失了方向。
这一切听起来是不是太复杂了？我是否应该删除moves和sCpeg()选项，让搜索算法随机跳转，直到找到解决方案？
递归是解决这个难题的好方法吗？我的跳转功能目前只需要询问你想要跳转到的位置。我必须改变它，以获得每次跳跃所需的开始和结束位置，这很容易改变，但我不知道这对算法是更好还是更坏。
这是为了一个学校项目，所以我必须实现一个不知情的搜索和启发式搜索算法。更改我的jump()函数可能会影响我的启发式。
我用Java编写代码，但由于这有点含糊，我只希望得到伪代码答案。伪代码本身就足以让我走上正确的道路。。
回答 1
Stack Overflow用户
发布于 2015-04-20 16:01:27
下面是递归解决方案的框架：
// given a board description, outputs solution sequence string, or null if no soln
public String sCpeg(boardDescription bd)
if bd is solution state, return "" // termination of successful recursion
for each possible move m
calculate result of m on bd to obtain newbd
store result of sCpeg(newbd) in subresult
if subresult is not null, return m + subresult
end for
// if we're here, no move worked -- termination, unsuccessful
return null我想这就是全部了。
对于这类问题，还有另一个框架:图论。图中的节点是电路板状态。我们用箭头连接两个电路板状态，如果你能从另一个得到一个。然后你在图中搜索连接首尾的最短路径...在有向图算法中使用任何标准最短路径。
但是你的递归思想应该工作得很好。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/29740684
复制相关文章
相似问题
腾讯云开发者
