c - 使用回溯递归的自回避行走

Question

就目前情况而言，这个问题不太适合我们的问答形式。我们希望答案得到事实、引用资料或专业知识的支持，但这个问题可能会引发辩论、争论、民意调查或扩展讨论。如果您觉得这个问题可以改进并可能重新开放， visit the help center以获得指导。

已关闭 11 年前。

给定:网格 m×n
我需要使用回溯和递归枚举所有不超过一个交点且在右上角结束的路径!？有什么建议 。？
Self-Avoiding Walk

Answer 1

非递归方式是保留一堆先前的位置以及该位置需要决策的信息。每次做出决定时，将需要保存的信息推送到堆栈顶部。

然后，当您的前向搜索发现问题时，它会弹出堆栈并跳回到最近的决策点并做出不同的决策。最终你要么成功，要么消除所有可能的路径。

对于递归解决方案，它是相同的，只不过不是将信息推送到堆栈上，而是在递归调用中做出决定后传递新位置。如果递归调用返回失败，您将在当前位置尝试下一个可能的决策。如果您在当前位置没有选择，则将失败返回到上面的级别。只有当递归调用返回成功时，该级别才会返回成功。

同样，最终整个调用链都会返回成功，或者消除所有可能的路径。

由于这是家庭作业，您必须自己决定哪些信息需要从一个级别传递到下一个级别，以及如何将最终的成功路径返回到应用程序。

您需要的所有新想法都在上面的段落中。实现仍然取决于您。

-杰西