Search一類的問題通常是人工智能方面最先接觸到的話題，在小的時候大家想必都遇到過這樣的一類益智題目：
一個農(nóng)夫亲铡，一只羊才写，一頭狼，和一棵白菜〗甭現(xiàn)在有一條船赞草，這條船每次只能盛這四個中的兩個，當(dāng)然只有農(nóng)夫會開船锭硼。問：
農(nóng)夫怎樣才能把狼房资，樣，和白菜運(yùn)到河對岸檀头，有兩個限制條件：
狼和羊不能單獨在一起轰异，羊和白菜這兩樣也不能落單岖沛。
遇到這樣的問題，相信大家一定在腦補(bǔ)：農(nóng)夫先帶過去一只搭独，看看后面那兩個有沒有后果發(fā)生婴削，沒的話繼續(xù)，有的話退回一步重新考慮牙肝。嗯唉俗，羊不能與狼和白菜共存，所以先帶過去配椭，然后第二次隨便帶狼或者白菜虫溜，帶過去，然后把羊帶回來股缸，然后把第二次剩下的帶過去衡楞，把羊留下，這樣狼和白菜到了對岸敦姻，最后把羊帶過去瘾境。當(dāng)然這樣的問題很簡單，想一下就能找到方案镰惦。當(dāng)遇到比較復(fù)雜的問題迷守，比如：
路徑規(guī)劃問題，從一個城市到另一座城市旺入，根據(jù)你的目標(biāo)不同兑凿，可以搜尋最短的，最快的或者風(fēng)景最好的眨业，這是一個問題的目標(biāo)（objective）急膀，然后根據(jù)設(shè)計選擇不同的方向沮协，這是行動（action）龄捡，又或者：機(jī)器人機(jī)械臂的運(yùn)動，速度快慢慷暂，旋轉(zhuǎn)和移動聘殖，字謎游戲，機(jī)器翻譯等等行瑞。
對于一個classifier（分類器）奸腺，如果給定一個輸入，經(jīng)過一個轉(zhuǎn)換之后得出的是一個單一的操作血久，而對于search（搜索）問題突照，輸出是一系列的操作，重點是要根據(jù)現(xiàn)狀考慮未來的動作氧吐，并且是基于狀態(tài)的一種操作讹蘑。
再回到剛剛提到的那個過河的問題末盔，其實從初始狀態(tài)可以畫一棵樹，初始狀態(tài)分別有三種選擇座慰，這樣每做出一個選擇可以畫出子分支陨舱，最后會發(fā)現(xiàn)能到達(dá)最終結(jié)果的就是剛剛跟大家分享的那兩種方案。歸結(jié)起來版仔，對于一個搜索問題游盲，包含：
初始狀態(tài)，動作蛮粮，對應(yīng)的動作的代價益缎，下一個狀態(tài)，和最終的狀態(tài)然想。
通常我們會用到數(shù)據(jù)結(jié)構(gòu)中常用的tree的概念链峭，構(gòu)建一個search tree：
根節(jié)點是初始狀態(tài)，葉節(jié)點是最終的狀態(tài)又沾，連接節(jié)點之間的邊就是一個action弊仪，并伴隨著一定的代價。從根節(jié)點到葉節(jié)點的所有路徑的和就是這個方案的代價杖刷，通常會找出一條代價最小的方案励饵。但是注意的是：
在編程中，我們通常不會用到樹這樣的數(shù)據(jù)結(jié)構(gòu)滑燃，樹在這里只是一種形象的表達(dá)役听，后面示例代碼中可以看到更多解釋。
在分析一棵樹的過程中表窘，通常會有這樣幾個參數(shù)：最大的深度D,也即每一條路徑包含D條邊典予，然后每個狀態(tài)可以有b 種動作，經(jīng)常把這個叫做branching factor乐严。想找到一個最少代價的路徑瘤袖，存儲的成本是O(D)，每次從葉節(jié)點回溯即可昂验，時間成本就比較大捂敌，O（b的D次方），（1 + b + b*b ,,,, + b的D次方 既琴，等比數(shù)列求和占婉，最后結(jié)果是 O（b的D次方））。面對這樣一個指數(shù)級別的時間成本甫恩，通常會有兩種做法逆济，一是限定最大的搜索深度，而是對于之前到達(dá)過的狀態(tài)，不重復(fù)訪問奖慌。
最基本的：
回溯搜索：
先判斷是不是最終結(jié)束的狀態(tài)霎终，是的話，更新最小的代價路徑
對于當(dāng)前狀態(tài)的每一個action：
?????? 尋找這個狀態(tài)所有的子節(jié)點和到達(dá)子節(jié)點對應(yīng)的代價升薯。
?????? 對于當(dāng)前的狀態(tài)重新調(diào)用回溯搜索莱褒。
返回最小代價的路徑
深度優(yōu)先搜索（depth-first search, DFS）：
基于回溯搜索，當(dāng)遇到終止?fàn)顟B(tài)的時候即停止涎劈。
存儲的成本是O(D)广凸， 每次從葉節(jié)點回溯即可，時間成本就比較大蛛枚，O（b的D次方）谅海。
需要注意的是，這個時候并沒有考慮每一個action的代價蹦浦，比如從初始狀態(tài)到下一個狀態(tài)扭吁，默認(rèn)代價是0。這跟之前接觸的每一條邊都有賦值不同盲镶，后面會再提到考慮代價的問題侥袜。
深度優(yōu)先搜索適用于整個搜索樹中有很多方案的搜索辦法，這樣溉贿，能比較快的返回搜索結(jié)果枫吧。不然，如果整棵樹都沒有方案宇色，需要把整個樹搜索一遍九杂。
廣度優(yōu)先搜索(breadth-first search, BFS)：
假設(shè)每一個action有固定的一個代價值，c宣蠕，整個搜索過程是按照由樹的每一層進(jìn)行的例隆。
假設(shè)每個狀態(tài)有b種可能的操作，最后的方案深度是d,樹的深度是D, 那么：
存儲的成本是O(b的d次方)抢蚀，時間成本也是O（b的d次方）镀层，與D 沒有關(guān)系。
由于讀取搜索的方式的不同思币，一般鹿响，DFS使用堆棧存儲節(jié)點的信息羡微，這樣保證最后入棧的節(jié)點得以出棧谷饿，然后再入棧該節(jié)點的所有子節(jié)點。BFS用隊列存儲妈倔，這樣第一次存入的所有節(jié)點可以依次從頭部出隊列博投，然后再把所有的子節(jié)點壓入隊列。并且不難想象的是盯蝴，這樣的存儲方式毅哗，存儲的都是葉節(jié)點听怕，中間的節(jié)點在產(chǎn)生子節(jié)點之前都已經(jīng)出棧或者隊列了虑绵。
來看一下一個用python寫的簡單的例子：
好尿瞭，搜索是人工智能很基礎(chǔ)的一個分支，下次接著來看其他搜索的方式翅睛。
