廣度優先演算法和深度優先演算法

『壹』 狀態空間盲目搜索演算法中廣度優先搜索和深度優先搜索的區別是什麼

摘要 很明顯的搜索策略不同，一個是深度，一個是廣度^-^,這個大家都知道~

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

一、指代不同

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

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

二、特點不同

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

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

三、演算法不同

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

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

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

在說它之前先提提狀態空間搜索。狀態空間搜索，如果按專業點的說法就是將問題求解過程表現為從初始狀態到目標狀態尋找這個路徑的過程。通俗點說，就是 在解一個問題時，找到一條解題的過程可以從求解的開始到問題的結果（好象並不通俗哦）。由於求解問題的過程中分枝有很多，主要是求解過程中求解條件的不確 定性，不完備性造成的，使得求解的路徑很多這就構成了一個圖，我們說這個圖就是狀態空間。問題的求解實際上就是在這個圖中找到一條路徑可以從開始到結果。 這個尋找的過程就是狀態空間搜索。 常用的狀態空間搜索有深度優先和廣度優先。廣度優先是從初始狀態一層一層向下找，直到找到目標為止。深度優先是按照一定的順序前查找完一個分支，再查找另一個分支，以至找到目標為止。這兩種演算法在數據結構書中都有描述，可以參看這些書得到更詳細的解釋。 前面說的廣度和深度優先搜索有一個很大的缺陷就是他們都是在一個給定的狀態空間中窮舉。這在狀態空間不大的情況下是很合適的演算法，可是當狀態空間十分大，且不預測的情況下就不可取了。他的效率實在太低，甚至不可完成。在這里就要用到啟發式搜索了。 啟發中的估價是用估價函數表示的，如： f(n) = g(n) + h(n) 其中f(n) 是節點n的估價函數，g(n)實在狀態空間中從初始節點到n節點的實際代價，h(n)是從n到目標節點最佳路徑的估計代價。在這里主要是h(n)體現了搜 索的啟發信息，因為g(n)是已知的。如果說詳細點，g(n)代表了搜索的廣度的優先趨勢。但是當h(n) >> g(n)時，可以省略g(n)，而提高效率。這些就深了，不懂也不影響啦！我們繼續看看何謂A*演算法。 2、初識A*演算法 啟發式搜索其實有很多的演算法，比如：局部擇優搜索法、最好優先搜索法等等。當然A*也是。這些演算法都使用了啟發函數，但在具體的選取最佳搜索節點時的 策略不同。象局部擇優搜索法，就是在搜索的過程中選取「最佳節點」後舍棄其他的兄弟節點，父親節點，而一直得搜索下去。這種搜索的結果很明顯，由於舍棄了 其他的節點，可能也把最好的節點都舍棄了，因為求解的最佳節點只是在該階段的最佳並不一定是全局的最佳。最好優先就聰明多了，他在搜索時，便沒有舍棄節點 （除非該節點是死節點），在每一步的估價中都把當前的節點和以前的節點的估價值比較得到一個「最佳的節點」。這樣可以有效的防止「最佳節點」的丟失。那麼 A*演算法又是一種什麼樣的演算法呢？其實A*演算法也是一種最好優先的演算法。只不過要加上一些約束條件罷了。由於在一些問題求解時，我們希望能夠求解出狀態空 間搜索的最短路徑，也就是用最快的方法求解問題，A*就是干這種事情的！我們先下個定義，如果一個估價函數可以找出最短的路徑，我們稱之為可採納性。A* 演算法是一個可採納的最好優先演算法。A*演算法的估價函數可表示為： f'(n) = g'(n) + h'(n) 這里，f'(n)是估價函數，g'(n)是起點到終點的最短路徑值，h'(n)是n到目標的最斷路經的啟發值。由於這個f'(n)其實是無法預先知道 的，所以我們用前面的估價函數f(n)做近似。g(n)代替g'(n)，但 g(n)>=g'(n)才可（大多數情況下都是滿足的，可以不用考慮），h(n)代替h'(n)，但h(n)<=h'(n)才可（這一點特別 的重要）。可以證明應用這樣的估價函數是可以找到最短路徑的，也就是可採納的。我們說應用這種估價函數的最好優先演算法就是A*演算法。哈。你懂了嗎？肯定沒 懂。接著看。 舉一個例子，其實廣度優先演算法就是A*演算法的特例。其中g(n)是節點所在的層數，h(n)=0，這種h(n)肯定小於h'(n)，所以由前述可知廣度優先演算法是一種可採納的。實際也是。當然它是一種最臭的A*演算法。 再說一個問題，就是有關h(n)啟發函數的信息性。h(n)的信息性通俗點說其實就是在估計一個節點的值時的約束條件，如果信息越多或約束條件越多則排除 的節點就越多，估價函數越好或說這個演算法越好。這就是為什麼廣度優先演算法的那麼臭的原因了，誰叫它的h(n)=0，一點啟發信息都沒有。但在游戲開發中由 於實時性的問題，h(n)的信息越多，它的計算量就越大，耗費的時間就越多。就應該適當的減小h(n)的信息，即減小約束條件。但演算法的准確性就差了，這 里就有一個平衡的問題。可難了，這就看你的了！ 好了我的話也說得差不多了，我想你肯定是一頭的霧水了，其實這是寫給懂A*演算法的同志看的。哈哈。你還是找一本人工智慧的書仔細看看吧！我這幾百字是不足以將A*演算法講清楚的。只是起到拋磚引玉的作用希望大家熱情參與嗎。

『肆』 廣度優先演算法和深度優先演算法哪個可以求無向圖的所有連通分量，具體什麼原理

你好，廣度優先和深度優先都可以求出無向圖的所有連通分量，他們的原理都是遍歷，一個是先按廣度進行遍歷，另外一個是先按深度進行遍歷。

『伍』 深度優先演算法 和 寬度優先演算法 的優缺點

1、深度優先演算法佔內存少但速度較慢，廣度優先演算法佔內存多但速度較快，在距離和深度成正比的情況下能較快地求出最優解。
2、深度優先與廣度優先的控制結構和產生系統很相似，唯一的區別在於對擴展節點選取上。由於其保留了所有的前繼節點，所以在產生後繼節點時可以去掉一部分重復的節點，從而提高了搜索效率。
3、這兩種演算法每次都擴展一個節點的所有子節點，而不同的是，深度優先下一次擴展的是本次擴展出來的子節點中的一個，而廣度優先擴展的則是本次擴展的節點的兄弟點。在具體實現上為了提高效率,所以採用了不同的數據結構。

『陸』 數據結構題目，廣度優先和深度優先

（一）深度優先搜索的特點是：

（1）從上面幾個實例看出，可以用深度優先搜索的方法處理的題目是各種
各樣的。
有的搜索深度是已知和固定的，如例題2-4，2-5，2-6；有的是未知的，如例題2-7、例題2-8；
有的搜索深度是有限制的，但達到目標的深度是不定的。
但也看到，無論問題的內容和性質以及求解要求如何不同，它們的程序結構
都是相同的，即都是深度優先演算法（一）和深度優先演算法（二）中描述的演算法結
構，不相同的僅僅是存儲結點數據結構和產生規則以及輸出要求。
（2）深度優先搜索法有遞歸以及非遞歸兩種設計方法。一般的，當搜索深度較小、問題遞歸方式比較明顯時，用遞歸方法設計好，它可以使得程序結構更簡捷易懂。當搜索深度較大時，如例題2-5、2-6。當數據量較大時，由於系統堆棧容量的限制，遞歸容易產生溢出，用非遞歸方法設計比較好。
（3）深度優先搜索方法有廣義和狹義兩種理解。廣義的理解是，只要最新產生的結點（即深度最大的結點）先進行擴展的方法，就稱為深度優先搜索方法。在這種理解情況下，深度優先搜索演算法有全部保留和不全部保留產生的結點的兩種情況。而狹義的理解是，僅僅只保留全部產生結點的演算法。本書取前一種廣義的理解。
不保留全部結點的演算法屬於一般的回溯演算法范疇。
保留全部結點的演算法，
實際上是在資料庫中產生一個結點之間的搜索樹，
因此也屬於圖搜索演算法的范疇。
（4）不保留全部結點的深度優先搜索法，由於把擴展望的結點從資料庫中彈出刪除，這樣，一般在資料庫中存儲的結點數就是深度值，因此它佔用的空間較少，所以，當搜索樹的結點較多，用其他方法易產生內存溢出時，深度優先搜索不失為一種有效的演算法。
（5）從輸出結果可看出，深度優先搜索找到的第一個解並不一定是最優解。例如例題2-8得最優解為13，但第一個解卻是17。如果要求出最優解的話，一種方法將是後面要介紹的動態規劃法，另一種方法是修改原演算法：把原輸出過程的地方改為記錄過程，即記錄達到當前目標的路徑和相應的路程值，並與前面已記錄的值進行比較，保留其中最優的，等全部搜索完成後，才把保留的最優解輸出。
二、廣度優先搜索法的顯著特點是：
（1）在產生新的子結點時，深度越小的結點越先得到擴展，即先產生它的子結點。為使演算法便於實現，存放結點的資料庫一般用隊列的結構。
（2）無論問題性質如何不同，利用廣度優先搜索法解題的基本演算法是相同的，但資料庫中每一結點內容，產生式規則，根據不同的問題，有不同的內容和結構，就是同一問題也可以有不同的表示方法。
（3）當結點到跟結點的費用（有的書稱為耗散值）和結點的深度成正比時，特別是當每一結到根結點的費用等於深度時，用廣度優先法得到的解是最優解，但如果不成正比，則得到的解不一定是最優解。這一類問題要求出最優解，一種方法是使用後面要介紹的其他方法求解，另外一種方法是改進前面深度（或廣度）優先搜索演算法：找到一個目標後，不是立即退出，而是記錄下目標結點的路徑和費用，如果有多個目標結點，就加以比較，留下較優的結點。把所有可能的路徑
都搜索完後，才輸出記錄的最優路徑。
（4）廣度優先搜索演算法，一般需要存儲產生的所有結點，占的存儲空間要比深度優先大得多，因此程序設計中，必須考慮溢出和節省內存空間得問題。
（5）比較深度優先和廣度優先兩種搜索法，廣度優先搜索法一般無回溯操作，即入棧和出棧的操作，所以運行速度比深度優先搜索演算法法要快些。
總之，一般情況下，深度優先搜索法佔內存少但速度較慢，廣度優先搜索演算法佔內存多但速度較快，在距離和深度成正比的情況下能較快地求出最優解。因此在選擇用哪種演算法時，要綜合考慮。決定取捨

『柒』 深度優先和廣度優先 的區別 ，用法。

1、主體區別

深度優先搜索是一種在開發爬蟲早期使用較多的方法。它的目的是要達到被搜索結構的葉結點(即那些不包含任何超鏈的HTML文件)。

寬度優先搜索演算法（又稱廣度優先搜索）是最簡便的圖的搜索演算法之一，這一演算法也是很多重要的圖的演算法的原型。

2、演算法區別

深度優先搜索是每次從棧中彈出一個元素，搜索所有在它下一級的元素，把這些元素壓入棧中。並把這個元素記為它下一級元素的前驅，找到所要找的元素時結束程序。

廣度優先搜索是每次從隊列的頭部取出一個元素，查看這個元素所有的下一級元素，把它們放到隊列的末尾。並把這個元素記為它下一級元素的前驅，找到所要找的元素時結束程序。

3、用法

廣度優先屬於一種盲目搜尋法，目的是系統地展開並檢查圖中的所有節點，以找尋結果。換句話說，它並不考慮結果的可能位置，徹底地搜索整張圖，直到找到結果為止。

深度優先即在搜索其餘的超鏈結果之前必須先完整地搜索單獨的一條鏈。深度優先搜索沿著HTML文件上的超鏈走到不能再深入為止，然後返回到某一個HTML文件，再繼續選擇該HTML文件中的其他超鏈。

(7)廣度優先演算法和深度優先演算法擴展閱讀：

實際應用

BFS在求解最短路徑或者最短步數上有很多的應用，應用最多的是在走迷宮上，單獨寫代碼有點泛化，取來自九度1335闖迷宮一例說明，並給出C++/Java的具體實現。

在一個n*n的矩陣里走，從原點（0,0）開始走到終點（n-1,n-1），只能上下左右4個方向走，只能在給定的矩陣里走，求最短步數。n*n是01矩陣，0代表該格子沒有障礙，為1表示有障礙物。

int mazeArr[maxn][maxn]; //表示的是01矩陣int stepArr = {{-1,0},{1,0},{0,-1},{0,1}}; //表示上下左右4個方向，int visit[maxn][maxn]; //表示該點是否被訪問過，防止回溯，回溯很耗時。核心代碼。基本上所有的BFS問題都可以使用類似的代碼來解決。

『捌』 深度優先搜索和廣度優先搜索的區別。 請講的詳細點，最好能用例子，謝謝啦

深度優先搜索所遵循的搜索策略是盡可能「深」地搜索圖。在深度優先搜索中，對於最新發現的結點，如果它還有以此為起點而未搜過的邊，就沿著邊繼續搜索下去。當結點v的所有邊都已被探尋過，搜索將回溯到發現結點v有那條邊的始結點。這一過程一直進行到已發現從源結點可達的所有結點為止。如果還存在未被發現的結點，則選擇其中一個作為源結點並重復以上過程，整個過程反復進行直到所有結點都被發現為止。

深度優先搜索基本演算法如下{遞歸演算法}：
PROCEDURE dfs_try(i);
FOR i:=1 to maxr DO
BEGIN
IF 子結點 mr 符合條件 THEN
BEGIN
產生的子結點mr入棧；
IF 子結點mr是目標結點
THEN 輸出
ELSE dfs_try(i+1);
棧頂元素出棧;
END;
END; 寬度優先搜索演算法（又稱廣度優先搜索演算法）是最簡單的圖的搜索演算法之一，這一演算法也是很多重要的圖的演算法的原型。Dijksta單源最短路徑演算法和Prim最小生成樹演算法都採用了與寬度優先搜索類似的思想。
寬度優先搜索的核心思想是：從初始結點開始，應用算符生成第一層結點，檢查目標結點是否在這些後繼結點中，若沒有，再用產生式規則將所有第一層的結點逐一擴展，得到第二層結點，並逐一檢查第二層結點中是否包含目標結點。若沒有，再用算符逐一擴展第二層所有結點……，如此依次擴展，直到發現目標結點為止。

寬度優先搜索基本演算法如下：
list[1]:=source; {加入初始結點，list為待擴展結點的表}
head:=0; {隊首指針}
foot:=1; {隊尾指針}
REPEAT
head:=head+1;
FOR x:=1 to 規則數 DO
BEGIN
根據規則產生新結點nw;
IF not_appear(nw,list) THEN {若新結點隊列中不存在，則加到隊尾}
BEGIN
foot:=foot+1;
list[foot]:=nw;
list[foot].father:=head;
IF list[foot]=目標結點 THEN 輸出；
END；
END；
UNTIL head>foot; {隊列為空表明再無結點可擴展}
望採納

『玖』 怎樣理解深度優先演算法和廣度優先演算法

胡說八道.... 深度優先:前序遍歷 廣度優先:按層遍歷