深度搜索演算法

『壹』 深度優先搜索

深度優先搜索是一種在開發爬蟲早期使用較多的方法。它的目的是要達到被搜索結構的葉結點(即那些不包含任何超鏈的HTML文件) 。在一個HTML文件中，當一個超鏈被選擇後，被鏈接的HTML文件將執行深度優先搜索，即在搜索其餘的超鏈結果之前必須先完整地搜索單獨的一條鏈。深度優先搜索沿著HTML文件上的超鏈走到不能再深入為止，然後返回到某一個HTML文件，再繼續選擇該HTML文件中的其他超鏈。當不再有其他超鏈可選擇時，說明搜索已經結束.事實上,深度優先搜索屬於圖演算法的一種,英文縮寫為DFS即Depth First Search.其過程簡要來說是對每一個可能的分支路徑深入到不能再深入為止,而且每個節點只能訪問一次. 在我們遇到的一些問題當中，有些問題我們不能夠確切的找出數學模型，即找不出一種直接求解的方法，解決這一類問題，我們一般採用搜索的方法解決。搜索就是用問題的所有可能去試探，按照一定的順序、規則，不斷去試探，直到找到問題的解，試完了也沒有找到解，那就是無解，試探時一定要試探完所有的情況（實際上就是窮舉）； 對於問題的第一個狀態，叫初始狀態，要求的狀態叫目標狀態。 搜索就是把規則應用於實始狀態，在其產生的狀態中，直到得到一個目標狀態為止。 產生新的狀態的過程叫擴展（由一個狀態，應用規則，產生新狀態的過程） 搜索的要點：（1）初始狀態； （2）重復產生新狀態； （3）檢查新狀態是否為目標，是結束，否轉（2）； 如果搜索是以接近起始狀態的程序依次擴展狀態的，叫寬度優先搜索。 如果擴展是首先擴展新產生的狀態，則叫深度優先搜索。 深度優先搜索 深度優先搜索用一個數組存放產生的所有狀態。 （1） 把初始狀態放入數組中，設為當前狀態； （2） 擴展當前的狀態，產生一個新的狀態放入數組中，同時把新產生的狀態設為當前狀態； （3） 判斷當前狀態是否和前面的重復，如果重復則回到上一個狀態，產生它的另一狀態； （4） 判斷當前狀態是否為目標狀態，如果是目標，則找到一個解答，結束演算法。 （5） 如果數組為空，說明無解。 對於pascal語言來講，它支持遞歸，在遞歸時可以自動實現回溯（利用局部變數）所以使用遞歸編寫深度優先搜索程序相對簡單，當然也有非遞歸實現的演算法。 搜索是人工智慧中的一種基本方法，是一項非常普遍使用的演算法策略，能夠解決許許多多的常見問題，在某些情況下我們很難想到高效的解法時，搜索往往是可選的唯一選擇。按照標準的話來講：搜索演算法是利用計算機的高性能來有目的的窮舉一個問題的部分或所有的可能情況，從而求出問題的解的一種方法。 搜索雖然簡單易學易於理解，但要掌握好並寫出速度快效率高優化好的程序卻又相當困難，總而言之，搜索演算法靈活多變，一般的框架很容易寫出，但合適的優化卻要根據實際情況來確定。在搜索演算法中，深度優先搜索（也可以稱為回溯法）是搜索演算法里最簡單也最常見的，今天我們就從這里講起，下面的內容假設讀者已經知道最基本的程序設計和簡單的遞歸演算法。 這是我找的資料，希望能幫到你~~

『貳』 關於廣度搜索演算法，和深度搜索演算法的C++簡單例子，要讓C++初學者都能盡量看懂

http://hi..com/probill/blog/item/c4db7e1bcabeaed2ac6e757c.html
這是我整理的「尋路演算法整理」，初學者應該可以看懂。

『叄』 深度優先搜索和廣度優先搜索，A星演算法三種演算法的區別和聯系

在說它之前先提提狀態空間搜索.狀態空間搜索,如果按專業點的說法就是將問題求解過程表現為從初始狀態到目標狀態尋找這個路徑的過程.通俗點說,就是 在解一個問題時,找到一條解題的過程可以從求解的開始到問題的結果（好象並不通俗哦）.由於求解問題的過程中分枝有很多,定性,不完備性造成的,使得求解的路徑很多這就構成了一個圖,我們說這個圖就是狀態空間.問題的求解實際上就是在這個圖中找到一條路徑可以從開始到結果.這個尋找的過程就是狀態空間搜索.

『肆』 深度優先搜索的系統演算法

所有的搜索演算法從其最終的演算法實現上來看，都可以劃分成兩個部分──控制結構和產生系統。正如前面所說的，搜索演算法簡而言之就是窮舉所有可能情況並找到合適的答案，所以最基本的問題就是羅列出所有可能的情況，這其實就是一種產生式系統。
我們將所要解答的問題劃分成若干個階段或者步驟，當一個階段計算完畢，下面往往有多種可選選擇，所有的選擇共同組成了問題的解空間，對搜索演算法而言，將所有的階段或步驟畫出來就類似是樹的結構（如圖）。
從根開始計算，到找到位於某個節點的解，回溯法（深度優先搜索）作為最基本的搜索演算法，其採用了一種「一隻向下走，走不通就掉頭」的思想（體會「回溯」二字），相當於採用了先根遍歷的方法來構造搜索樹。
上面的話可能難於理解，沒關系，我們通過基本框架和例子來闡述這個演算法，你會發現其中的原理非常簡單自然。

『伍』 一道數據結構題，深度搜索法和寬度搜索法的

深度搜索就是只要前面沒走過，一條路走到黑。 D是深度優先，a-e-d--走到頭才訪問b
寬度是搜索完自己的孩子再搜孩子的孩子。 C是寬度優先，a-接下來是孩子b e c-接下來是三代孩子d f。

望採納

『陸』 常見的搜索演算法有哪幾種

• 廣度優先搜索（BFS）

• 深度優先搜索（DFS）

• 爬山法（Hill Climbing）

• 最佳優先演算法（Best-first search strategy）

• 回溯法 （Backtracking）

• 分支限界演算法（Branch-and-bound Search Algorithm）

『柒』 深度優先演算法的定義

深度優先搜索演算法（Depth-First-Search），是搜索演算法的一種。是沿著樹的深度遍歷樹的節點，盡可能深的搜索樹的分支。當節點v的所有邊都己被探尋過，搜索將回溯到發現節點v的那條邊的起始節點。這一過程一直進行到已發現從源節點可達的所有節點為止。如果還存在未被發現的節點，則選擇其中一個作為源節點並重復以上過程，整個進程反復進行直到所有節點都被訪問為止。屬於盲目搜索。
深度優先搜索是圖論中的經典演算法，利用深度優先搜索演算法可以產生目標圖的相應拓撲排序表，利用拓撲排序表可以方便的解決很多相關的圖論問題，如最大路徑問題等等。
因發明「深度優先搜索演算法」，霍普克洛夫特與陶爾揚共同獲得計算機領域的最高獎：圖靈獎.

『捌』 搜索演算法:這個既不是深度優先,也不是廣度優先,這叫什麼搜索演算法

廣度優先
dijkstra(迪傑斯特拉)演算法是典型的單源最短路徑演算法，用於計算一個節點到其他所有節點的最短路徑。主要特點是以起始點為中心向外層層擴展，直到擴展到終點為止。

『玖』 深度優先遍歷與廣度優先遍歷的區別

一、指代不同

1、深度優先遍歷：是對每一個可能的分支路徑深入到不能再深入為止，而且每個節點只能訪問一次。

2、廣度優先遍歷：系統地展開並檢查圖中的所有節點，以找尋結果。

二、特點不同

1、深度優先遍歷：所有的搜索演算法從其最終的演算法實現上來看，都可以劃分成兩個部分──控制結構和產生系統。正如前面所說的，搜索演算法簡而言之就是窮舉所有可能情況並找到合適的答案，所以最基本的問題就是羅列出所有可能的情況，這其實就是一種產生式系統。

2、廣度優先遍歷：並不考慮結果的可能位置，徹底地搜索整張圖，直到找到結果為止。

三、演算法不同

1、深度優先遍歷：把根節點壓入棧中。每次從棧中彈出一個元素，搜索所有在它下一級的元素，把這些元素壓入棧中。並把這個元素記為它下一級元素的前驅。找到所要找的元素時結束程序。如果遍歷整個樹還沒有找到，結束程序。

2、廣度優先遍歷：把根節點放到隊列的末尾。每次從隊列的頭部取出一個元素，查看這個元素所有的下一級元素，把它們放到隊列的末尾。並把這個元素記為它下一級元素的前驅。找到所要找的元素時結束程序。如果遍歷整個樹還沒有找到，結束程序。

『拾』 廣度搜索演算法與深度搜索演算法有什麼區別

廣度的話是先搜橫向
深度是縱向的