學習回溯算法

Question

我想學習回溯算法。有人可以教我一些嗎？我試圖從一些網站學習，但它沒有奏效。所以有人可以教我。謝謝！

Answer 1

雖然語言無關，this教程是很好的，並提出了幾個例子，可能提供必要的直覺。

也就是說，後面回溯的想法並不難把握都沒有。甲回溯算法基本上探索所有解空間只是進行蠻力，除了像時（並且這使得更有效）它從部分溶液儘快回溯，因爲它認識到它是不可行的。

一個例子

考慮爲衆所周知eight queens problem此部分解決方案。

在第一四列王后已經被定位，但最後一個是一個無效的廣場。蠻力解決方案將繼續爲其餘的列放置皇后，而忽視這樣一個事實，即不管這種局部解決方案如何增強，結果將是無效的。

回溯算法將是「聰明」：將實現第四女王被錯誤地放置和「返回」到考慮其他的廣場吧。

Answer 2

Fundamentals Of Computer Algorithms包含回溯一個不錯的篇章。但是你沒有指定你對正式的算法文本和數據結構有多熟悉。如果您不熟悉複雜性分析等基本算法或不知道樹是什麼，那麼在閱讀本書時可能會遇到一些問題。我的意思是在這種情況下，你需要從頭開始閱讀本書，直接跳到回溯章節不會有太大的幫助。