学习回溯算法

Question

9

我想学习回溯算法。有人可以教我一些吗？我尝试从一些网站学习，但没有成功。所以，有人可以教我吗？谢谢！

- Jeel Shah

你理解了多少？ - Anders Lindahl

我不太理解 =(. - Jeel Shah

2个回答

4

《计算机算法基础》一书中有一章非常详细地介绍了回溯算法。但是，如果您不熟悉正式的算法文本和数据结构，可能会在阅读此书时遇到一些问题。例如，如果您不熟悉复杂度分析或者不知道什么是树，那么您需要从头开始阅读这本书，直接跳转到回溯算法章节可能并不会有太大的帮助。

- taskinoor

你有电子书副本吗？或者你知道在哪里可以获取电子书吗？ - Jeel Shah

5

请谷歌搜索该内容。即使我知道也不会在这里发布，因为那是侵犯版权的行为。 - taskinoor

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- abeln · Accepted Answer

虽然不依赖于特定编程语言，this 教程很好，并提供了几个例子，可以提供必要的直觉。

话虽如此，回溯背后的思想并不难以理解。回溯算法本质上像执行暴力搜索一样探索所有解空间，但是（这使其更有效率），它在意识到一个部分解不可行时立即回溯。

一个例子

考虑这个著名的eight queens problem的部分解。

enter image description here

前四列中的皇后已经被放置，但最后一列在一个无效的方格中。暴力解决方案会继续为其余列放置皇后，而忽视这个部分解决方案不管如何增强都将是无效的事实。

回溯算法会更加"聪明"：它会意识到第四个皇后放置不正确，并"回到"考虑其他方格。