一點(diǎn)dfs搜索小結(jié)
首先說說兩個(gè)經(jīng)典的搜索策略，dfs和bfs，dfs對(duì)于是按照深度進(jìn)行搜索，它主要就是對(duì)于當(dāng)前可行節(jié)點(diǎn)馬上擴(kuò)展，直到不可行的那個(gè)節(jié)點(diǎn)，那么就進(jìn)行回朔，那么在回朔那里我們可以保存全局變量的值，以便供其他中可行的方案進(jìn)行擴(kuò)展，那九宮格來說，也就是數(shù)獨(dú)游戲，
現(xiàn)在我們按照dfs來遍歷，假設(shè)我們從dfs（0,0)開始，然后按行進(jìn)行擴(kuò)展，如果當(dāng)前已經(jīng)有值，那么我們遞歸進(jìn)入下一個(gè)節(jié)點(diǎn)，而對(duì)于本層次我們要保存一些信息，比如此時(shí)map里放入的具體值是多少，因?yàn)槲覀儾恢来舜芜f歸是否是正確的遞歸，如果不正確的話，我們還要在這里回朔，如果當(dāng)前沒有值，那么我們一次從1...9進(jìn)行試探，對(duì)于可行的節(jié)點(diǎn)馬上進(jìn)入下一次遞歸，當(dāng)然這里同樣要保存節(jié)點(diǎn)信息，以便下一次回朔！
我們知道對(duì)于搜索來說，一開始的時(shí)候，往往具有很多分支，往往是有多種可能性，但是隨著遞歸深度的增加，分支數(shù)就會(huì)逐漸減少，然后最后就可能出現(xiàn)滿足條件和不滿足條件的情況，對(duì)于滿足條件的情況，那么我們就可以直接退出了，表示我們已經(jīng)搜索到了我們要的結(jié)果，可以退出了，同樣，如果不滿足條件，那么我們知道，此時(shí)是不行的，那么我們想回到上一層的遞歸，此時(shí)就要回朔了，但是此時(shí)如果我們沒有對(duì)于遞歸的臨時(shí)棧沒有保存的話，那么我們也不會(huì)知道何時(shí)應(yīng)該回朔，何時(shí)是正確結(jié)果本該退出！所以一般來說，這里往往是需要一個(gè)臨時(shí)變量來保存下一次遞歸的結(jié)果，然后根據(jù)這個(gè)結(jié)果，來決定是回朔，還是已經(jīng)是正確的結(jié)果可以退出了！ 此時(shí)往往是這樣 對(duì)于 dfs(i) 那么var=dfs(i+1)，如果。。否則又，這里要注意的是，因?yàn)樵谝婚_始我們可能對(duì)于每一層遞歸都有很多種情況，所以在回朔的時(shí)候，一定要注意回朔的位置一定要是相應(yīng)的位置！
1.poj1011 sticks 經(jīng)典的一題，是我一開始的一題
我的大體思路是這樣：
1.首先對(duì)于可能的長度len，首先求出總共的棍的數(shù)目num，然后對(duì)len
進(jìn)行dfs，在數(shù)組里找合適的木棍填充len，填充完畢后，num數(shù)減少1，在繼續(xù)在里面找，
如果在當(dāng)前層次上面找不到后，那么就退出此時(shí)的查找，說明len是不可能的長度(這里要對(duì)數(shù)組
元素降序排序。。
這里問題就是如何每一次對(duì)len的dfs，找出合適的棍子，以及如果不合適，怎么回到上一層
這里主要的是考察優(yōu)化的
2.poj 2362 這一題和sticks一題很相似
思路大致是這樣，首先判斷棍子是否能被4正除，若能，求出棍子的長度，然后在里面找起組合，若能組成4條這樣的那么就行了
3. 素?cái)?shù)環(huán)，這一題就是簡單的dfs了，非常好寫，只要滿足相鄰數(shù)的和就可以繼續(xù)擴(kuò)展了！
4. poj1416 對(duì)于這一題，要求是分解一個(gè)數(shù)，要他們的和，比目標(biāo)數(shù)小而且最好是盡量接近，而要用dfs搜索的話，這里每一層涉及到的遞歸信息比較多，因?yàn)橐啻吻笾担看挝覀兌家４嬉恍┡R時(shí)的值，對(duì)于這些遞歸來說，在某些層次遞歸的步驟比較多，我們往往會(huì)在遞歸的條件里在套一個(gè)遞歸，對(duì)于這些，理解起來會(huì)有難度，一個(gè)好的做法就是在每一部遞歸的過程中輸出相應(yīng)的臨時(shí)變量，這樣便可以跟蹤遞歸時(shí)一些量的變化！這個(gè)題目到目前還沒有解決，只有過幾天再看看了，主要原因是dfs的過程中設(shè)計(jì)到的臨時(shí)變量很多，不知道如何來設(shè)計(jì)這個(gè)回朔！
———————————————————————————————————————
具體代碼在我的csdnhttp://blog.csdn.net/pzz837157806?viewmode=contents