我正試圖改進當前的8皇后問題算法，這是我第一次真正處理算法設計/算法。我想實現一個深度優先搜索與此處描述的不同Y值的排列組合： http://en.wikipedia.org/wiki/Eight_queens_puzzle#The_eight_queens_puzzle_as_an_exercise_in_algorithm_design深度優先搜索基礎知識
我已經實現了置換部分來解決這個問題，但我有一個小麻煩纏繞我的心圍繞深度優先搜索。它被描述爲遍歷樹/圖的一種方式，但它會生成樹圖嗎？似乎只有通過深度優先搜索生成要遍歷的樹結構，通過實現一些邏輯來僅生成樹的某些部分，該方法纔會更有效。
所以基本上，我將不得不創建一個算法，生成一個修剪的詞法排列樹。我知道如何實現修剪邏輯，但我只是不確定如何將它與排列生成器配合使用，因爲我一直在使用next_permutation。
是否有可以幫助我的深度優先搜索或創建在樹的形式lexigraphic排列的基本知識的任何資源？
在一般情況下，是的，深度優先搜索的想法是，你不會有產生（或「訪問」或「擴展」）的每一個節點。
在八個皇后問題的情況下，如果你把一個女王，使得它可以攻擊其他的女王，則可以中止該分支;它不能導致解決方案。
如果您正在解決Eight Queens的變體，以便您的目標是找到一個解決方案，而不是全部92個，那麼只要找到一個解決方案，就可以立即退出。更一般地說，如果你正在解決一個不太離散的問題，比如根據某種方法尋找皇后的「最佳」安排，那麼只要你知道它不能導致最終狀態更好，你就可以放棄一個分支而不是您在另一個分支上已經找到的最終狀態。這與A* search algorithm有關。
更普遍的是，如果您正在攻擊一個非常大的問題（如國際象棋），您可能會對某個解決方案非常滿意，因此您可以放棄一個可能不會導致解決方案的解決方案你已經找到了。
DFS算法本身不生成樹/圖。如果你想構建樹和圖，就像執行搜索一樣簡單。如果你只想找到一個soution，像鏈表這樣的扁平LIFO數據結構就足夠了：當你訪問一個新節點時，將它附加到列表中。當您在搜索中使節點返回時，請關閉該節點。
一本名爲「算法導論」的書由一位李維坦撰寫，爲您的理解提供了合適的解釋。他還提供瞭解決8皇后問題的解決方案，就像你描述它的方式一樣。它肯定會幫助你。
正如我的理解，爲了找到一個解決方案，你不需要任何置換，所有你需要的是dfs.That孤獨就足以找到解決方案