给定：网格 m×n
我需要使用回溯和递归枚举所有不超过一个交叉点并且在右上角结束的路径！？有什么建议么 。？
自我避免的步行
问问题
549 次
1 回答
3
非递归方式是保留一堆先前的位置以及需要在该位置做出决定的信息。每次做出决定时，将需要保存的信息推送到堆栈顶部。
然后，当您的向前搜索发现问题时，它会弹出堆栈并跳回最近的决策点并做出不同的决策。最终，您要么成功，要么将所有可能的路径视为不可能的路径。
对于递归解决方案，它是相同的，除了不是将信息压入堆栈，而是在递归调用中做出决定后传递新位置。如果递归调用返回失败，则在当前位置尝试下一个可能的决定。如果您在当前位置没有选择，则将失败返回到上述级别。只有当递归调用返回成功时，此级别才会返回成功。
同样，最终成功返回整个调用链，或者消除所有可能的路径。
而且由于这是家庭作业，您必须自己决定哪些信息需要从一个级别传递到下一个级别，以及您的最终成功路径如何返回到应用程序。
您需要的所有新想法都在上面的段落中。实施仍取决于您。
-杰西
于 2012-06-17T14:30:02.633 回答