一點dfs搜索小結

    首先說說兩個經典的搜索策略，dfs和bfs，dfs對于是按照深度進行搜索，它主要就是對于當前可行節點馬上擴展，直到不可行的那個節點，那么就進行回朔，那么在回朔那里我們可以保存全局變量的值，以便供其他中可行的方案進行擴展，那九宮格來說，也就是數獨游戲，

   現在我們按照dfs來遍歷，假設我們從dfs（0,0)開始，然后按行進行擴展，如果當前已經有值，那么我們遞歸進入下一個節點，而對于本層次我們要保存一些信息，比如此時map里放入的具體值是多少，因為我們不知道此次遞歸是否是正確的遞歸，如果不正確的話，我們還要在這里回朔，如果當前沒有值，那么我們一次從1...9進行試探，對于可行的節點馬上進入下一次遞歸，當然這里同樣要保存節點信息，以便下一次回朔！

 我們知道對于搜索來說，一開始的時候，往往具有很多分支，往往是有多種可能性，但是隨著遞歸深度的增加，分支數就會逐漸減少，然后最后就可能出現滿足條件和不滿足條件的情況，對于滿足條件的情況，那么我們就可以直接退出了，表示我們已經搜索到了我們要的結果，可以退出了，同樣，如果不滿足條件，那么我們知道，此時是不行的，那么我們想回到上一層的遞歸，此時就要回朔了，但是此時如果我們沒有對于遞歸的臨時棧沒有保存的話，那么我們也不會知道何時應該回朔，何時是正確結果本該退出！所以一般來說，這里往往是需要一個臨時變量來保存下一次遞歸的結果，然后根據這個結果，來決定是回朔，還是已經是正確的結果可以退出了！ 此時往往是這樣 對于 dfs(i)  那么var=dfs(i+1)，如果。。否則又，這里要注意的是，因為在一開始我們可能對于每一層遞歸都有很多種情況，所以在回朔的時候，一定要注意回朔的位置一定要是相應的位置！

  1.poj1011 sticks 經典的一題，是我一開始的一題

  我的大體思路是這樣：

  1.首先對于可能的長度len，首先求出總共的棍的數目num，然后對len 

  進行dfs，在數組里找合適的木棍填充len，填充完畢后，num數減少1，在繼續在里面找，

  如果在當前層次上面找不到后，那么就退出此時的查找，說明len是不可能的長度(這里要對數組

  元素降序排序。。

  這里問題就是如何每一次對len的dfs，找出合適的棍子，以及如果不合適，怎么回到上一層

  這里主要的是考察優化的

 2.poj 2362 這一題和sticks一題很相似

  思路大致是這樣，首先判斷棍子是否能被4正除，若能，求出棍子的長度，然后在里面找起組合，若能組成4條這樣的那么就行了 

 3. 素數環，這一題就是簡單的dfs了，非常好寫，只要滿足相鄰數的和就可以繼續擴展了！

 4.  poj1416 對于這一題，要求是分解一個數，要他們的和，比目標數小而且最好是盡量接近，而要用dfs搜索的話，這里每一層涉及到的遞歸信息比較多，因為要多次求值，每次我們都要保存一些臨時的值，對于這些遞歸來說，在某些層次遞歸的步驟比較多，我們往往會在遞歸的條件里在套一個遞歸，對于這些，理解起來會有難度，一個好的做法就是在每一部遞歸的過程中輸出相應的臨時變量，這樣便可以跟蹤遞歸時一些量的變化！這個題目到目前還沒有解決，只有過幾天再看看了，主要原因是dfs的過程中設計到的臨時變量很多，不知道如何來設計這個回朔！

 ———————————————————————————————————————
 具體代碼在我的csdnhttp://blog.csdn.net/pzz837157806?viewmode=contents