每个人都知道 cookies 桶三角钉接龙游戏。你拿起一个钉子,将其跳过另一个钉子,放入一个空洞中,目标是只剩下一个钉子。
在我的游戏板对象代码中,我有一个函数 sCpeg(int a, int b) ,它可以更改您当前用于跳跃的 Hook 。为了解决这个问题,我将其连接到一个 Moves 变量。每次你改变当前的钉子并用它来跳跃时,都算作一次移动。它是作为一种非常基本的启发式方法完成的,我希望成为一种搜索算法:探索一个钉子可用的所有可能的跳跃。如果找不到解决方案,则回溯,更新当前的 Hook 并重复该过程。
当我写下这个想法时,它听起来像是一个使用递归的完美示例,只是我不知道如何在这种情况下正确使用递归。在回溯和更新当前 Hook 之间我迷失了。
这一切听起来是不是太复杂了?我是否应该删除移动和 sCpeg() 选项并让搜索算法随机跳转直到找到解决方案?
递归是解决这个难题的好方法吗?我的跳转功能目前仅询问您想要跳转到的位置。我必须更改它以获取每次跳跃所需的开始和结束位置,这很容易更改,但我不知道它对算法来说是好是坏。
这是一个学校项目,所以我必须实现无信息搜索和启发式搜索算法。更改我的 jump()
函数可能会影响我的启发式方法。
我正在用 Java 编码,但由于这有点模糊,我只期待伪代码答案。仅伪代码就足以让我走上正轨。 。
最佳答案
这是递归解决方案的框架:
// 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
我想这就是全部内容了。
解决此类问题还有另一个框架:图论。图表的节点是棋盘状态。如果您可以从另一个棋盘状态中获得一个,我们会用箭头连接两个棋盘状态。然后,您在图中搜索连接起点到终点的最短路径...在有向图算法中使用任何标准最短路径。
但是你的递归想法应该可以正常工作。
关于algorithm - 钉子接龙递归解决方案,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/29740684/