-4

我查看了互联网和其他地方（包括我的书），但我似乎并没有真正得到我正在寻找的答案。让我熬到这个可怕的时刻（早上 5 点 25 分）的主要部分是回溯。这甚至是如何工作的？当我四面受阻时，我只是放了“return”，它神奇地撤消了我的最后一步？我不敢相信地摇头，因为我一直认为只要你“回来”，你的递归就会完全展开。

我也有点恼火我的代码太长了。我的老师告诉全班同学，这应该是一个简短的解决方案。好吧，我必须加载迷宫，检查东西，编写检查方向的算法（我只是将它修改为递归，但我几乎 100% 确定它是错误的）。更不用说初始化对象数组并编写专门的方法来寻找要传送到的超空间点。不管怎样，就在这里。我知道其中一些没有任何作用。毕竟，我还没有完成它。http://pastebin.com/5wknVCWa是的，我将它粘贴在那里，因为它确实有点大。超过300行。

4

1 回答 1

3

回溯算法很短。它不必是递归的（但这样看起来好多了）。你做的主要工作是编写一个拒绝函数，它检查当前的决定是否仍然正常。如果不是，那么你回溯（即从单级递归返回）到上一个决定。

在迷宫中，拒绝功能可能是您刚刚走进一堵墙 - 或者被格鲁吃掉了。接受功能可能意味着您完成了迷宫并完成了（或救出了王子等）

http://en.wikipedia.org/wiki/Backtracking

 procedure bt(c)
   if reject(P,c) then return
   if accept(P,c) then output(P,c)
   s ← first(P,c)
   while s ≠ Λ do
     bt(s)
     s ← next(P,s)
于 2013-05-16T10:57:08.640 回答