学习回溯算法

Question

我想学习回溯算法。有人能教我一些吗？我试着从一些网站上学习，但不起作用。有没有人可以教我。谢谢!

Answer 1

虽然语言不可知，但this教程很不错，并提供了几个可能提供必要直觉的示例。

也就是说，回溯背后的想法并不难理解。回溯算法本质上探索所有的解空间，就像执行暴力一样，除了(这使它更有效)一旦意识到不可行，它就从部分解回溯到。

示例

考虑一下众所周知的eight queens problem的部分解决方案。

​

​

前四列中的皇后已经定位，但最后一列在一个无效的正方形中。暴力解决方案将继续为其余列放置皇后，而忽略了这样一个事实，即无论如何增加这个部分解决方案，结果都将是无效的。

回溯算法将变得“更聪明”：它将意识到第四个女王的位置不正确，并“回到”考虑它的其他方块。

Answer 2

Fundamentals Of Computer Algorithms包含了一个关于回溯的很好的章节。但是您还没有具体说明您对正式的算法文本和数据结构有多熟悉。如果你不熟悉像复杂性分析这样的基本算法，或者不知道什么是树，那么你在阅读这本书时可能会遇到一些问题。我的意思是，在这种情况下，你需要从头开始阅读这本书，直接跳到回溯章节不会有太大帮助。