·1.2.1_當(dāng)一切充滿不可知的時候，我們都是盲目的擂啥。
? ? ? 盡管一切皆不可知哄陶，但我們并不能喪失面對未知的勇氣，所以讓我們勇敢且驕傲地探索這未知的一切吧哺壶。
1屋吨，2，3這三個數(shù)的全排列是顯而易得的：123山宾，132至扰，213，231塌碌，312渊胸，321
即使是在程序中也是如此旬盯，我們只需要用三個for循環(huán)嵌套就能完成此全排列台妆。
但如果是9個數(shù)的全排列呢翎猛？
我猜有一些讀者或許會想到，那用9個for循環(huán)嵌套就可以辣~接剩。
誒切厘，雖然您是對的，但我不敢茍同懊缺，畢竟這太蠢了疫稿。
而且，如果是N個數(shù)的全排列就沒轍了啊鹃两，畢竟您不能N個for循環(huán)嵌套遗座。
（此處忽略一些奇奇怪怪的方法！這是正經(jīng)的算法入門教程翱“狻Ｍ窘！馋记！親）
所以号坡，我們要用一個方法，叫盲目搜索法梯醒。它到底有多盲目呢宽堆？就像明知道是錯的，仍然去愛的愛情那么盲目吧茸习，這只是舉例子哇畜隶。
盲目搜索法旗下有很多方法，但此文中會也僅會提到兩種号胚。
? ? ? ? ①深度優(yōu)先搜索代箭。簡稱dfs。
啊哈算法這本書中是這樣形容的涕刚，不撞南墻不回頭嗡综。嗯，這很盲目杜漠，很像愛情极景，或者夢想。這個東西通常用遞歸或者棧來實現(xiàn)驾茴。
? ? ? ? ②廣度優(yōu)先搜索盼樟。簡稱bfs。
這個算法符合就近原則锈至，大概是一只吃窩邊草的兔子吧晨缴。實現(xiàn)的話，通常得借助隊列峡捡。
盲目搜索可以讓程序?qū)η巴疚床返那闆r下击碗，去進(jìn)行搜索筑悴，他會把所有可能情況都枚舉一遍。
·1.2.2_關(guān)于遞歸稍途。
? ? ? ?無論各位學(xué)過或者沒學(xué)過遞歸阁吝，我都建議認(rèn)真看一次。因為這很簡潔械拍，除了我個人的經(jīng)驗積累突勇，沒有其他任何東西。
? ? ? 什么是遞歸坷虑？在程序當(dāng)中甲馋，遞歸通常指函數(shù)或者方法在函數(shù)體內(nèi)調(diào)用其自身。
? ? ? 在寫遞歸時迄损，你必須思考的是什么摔刁？
? ? ? ? ? ? ? ? ? ? ?①確定遞歸狀態(tài)轉(zhuǎn)移。
? ? ? ? ? ? ? ? ? ? ?②確定遞歸邊界海蔽。
例子共屈，
void recursion(Object object){
? ? if( isBoundary(object) ){ ? //判斷是否為遞歸邊界。
? ? ? ? ? ? ?//do something?
? ? ?}else{
? ? ? ? ? ?//遞歸狀態(tài)轉(zhuǎn)移
? ? ? ? ? object = transfer_state_function(object);
? ? ? ? ? recursion(object);
? ? }
}
引申：深度優(yōu)先搜索能通過棧來實現(xiàn)的原因是党窜，高級語言中拗引，遞歸是通過函數(shù)棧來實現(xiàn)的，我們能通過棧來模擬函數(shù)棧的行為從而實現(xiàn)遞歸幌衣，對此有興趣的讀者可以自行嘗試矾削。
·1.2.3_深度優(yōu)先搜索。
之前提到了深度優(yōu)先搜索是由遞歸實現(xiàn)的豁护，那我們該如何借助遞歸去搜索呢哼凯？
在有一顆二叉樹，深度優(yōu)先搜索可以類比為后序遍歷楚里。
此時，邊界為 是否擁有子節(jié)點(diǎn)。狀態(tài)轉(zhuǎn)移為不同節(jié)點(diǎn)的轉(zhuǎn)移径簿。
實現(xiàn)例子： ?假設(shè)Node為樹中的節(jié)點(diǎn)罢屈，haveSon()能判斷是否具有子節(jié)點(diǎn)，haveLeftSon()是否具有左節(jié)點(diǎn)牍帚，haveRightSon()同理儡遮。
void dfs(Node node){
? ? ? ?if( !node.haveSon() ){ //搜索邊界
? ? ? ?}else{ ? ?//節(jié)點(diǎn)轉(zhuǎn)移乳蛾。偏好為 先選左子樹
? ? ? ? ? ? ? ?if( node.haveLeftSon() ) dfs(node.leftSon);
? ? ? ? ? ? ? ?if( node.haveRightSon() ) dfs(node.rightSon);
? ? ? }
}
也例如我們要實現(xiàn)N個元素的全排列暗赶，且N個元素分別為1，2肃叶，3蹂随，4，……N-1因惭，N岳锁。
先選一個，然后有N種選法蹦魔，再選一個激率，有N-1種選法，如此類推勿决，則可得所有可能的情況為 N! 種乒躺。
設(shè)第一種為 123456.....N，（即假設(shè)該算法的偏好為先選較械退酢）
則代碼實現(xiàn)：
假設(shè)?
一嘉冒，存在數(shù)組choice 且下標(biāo)為 i 時記錄了當(dāng)前第i個元素的選擇的數(shù)。如第一種被輸出時咆繁，數(shù)組為 [1,2,3,4,5,6,....,N]
二讳推，存在數(shù)組 is_arr_beChoiced 且下標(biāo)為 i 時記錄了當(dāng)前數(shù) i 是否被選擇。
void dfs(int index){
? ? ? if(index == N){
? ? ? ? ? ? ? //輸出 choice數(shù)組中選擇的數(shù)玩般。
? ? ? }else{//搜索狀態(tài)轉(zhuǎn)移
? ? ? ? ? ? for(int i = 1 ; i<=N ; i++){
? ? ? ? ? ? ? ?if( !is_arr_beChoiced[i] ){
? ? ? ? ? ? ? ? ? ?is_arr_beChoiced[i] = true;choice[index] = i;
? ? ? ? ? ? ? ? ? ?dfs(index+1);
? ? ? ? ? ? ? ? ? ? is_arr_beChoiced[i] = false;
? ? ? ? ? ? ? }
? ? ? ? ? }
? ? ?}
}
如果你看懂了上面的兩個例子银觅，那我們來總結(jié)一下深度優(yōu)先搜索的特點(diǎn)。
①無論如何坏为，總需要有一個初始狀態(tài)设拟。開始搜索的時候的狀態(tài)成為搜索狀態(tài)，例如久脯，第一個例子的根節(jié)點(diǎn)時的狀態(tài)纳胧。
②搜索的過程中伴隨著狀態(tài)的轉(zhuǎn)換。
③一定有搜索邊界帘撰。
④他堅持著某種偏好跑慕。這或許就是他的夢想了吧。
....關(guān)于深度優(yōu)先搜索還未完，諸君晚安核行，以后見牢硅。2017.1.17.4:42..
