您所做的任何事情都從搜索開始！ 人工智能可以解決這些日常問題。 讓我們了解BFS，DFS等…

縱觀歷史，人類一直在尋找東西。 搜索使我們成為今天的我們。 在遠古時代，覓食者常常尋找生活必需品。 他們創建了一些工具來簡化搜索過程。 人腦也在這個過程中進化。 現在，它可以創建該地區的思維導圖，而覓食者可以將區域映射到他們自己的頭腦中，并可以更有效地進行搜索。 即使在現代，我們基本上也使用以前使用的相同策略。 但是現在，我們有了更先進的工具，我們的思想也有了更多發展。 我們使用地圖來尋找方法，例如Google Maps之類的工具就是我們如何發展自己以更高效地進行搜索的最佳示例。

我們在搜索中取得的最重大進步是由于技術的變化。 在計算機科學中，我們將此術語稱為算法。 隨著大腦能力的增強，我們創建了更復雜，更高效的算法。 我們開發了這些解決方案來解決更復雜的問題。 算法可以使我們的生活更簡單，并使我們更高效。 從日常任務到創建世界一流的人工智能，搜索算法都是所有人類工作的基礎。 在此博客中，我們將看到兩種最基本的搜索算法，它們將為我們對更復雜算法的理解奠定基礎。

不要讓這種解釋變得平淡無奇。 我們將以真實生活（LoL）為例來了解搜索本身的發展。 好的（？）

因此，顯然我有一個女友麗莎（至少在我的想象中）。 她對所有使用的東西都很聰明，而且非常挑剔。 前幾天，她在某處丟了口紅。 這是她最喜歡的陰影。 就像我說的她非常挑剔一樣，她不會適應其他陰影或任何其他品牌。 但是問題在于口紅非常稀有，而且嚇壞了。 現在，她計劃購買新的。 我們附近的商店非常寬敞； 如果他們沒有的話，他們會引導她去其他商店。 她可以通過幾種方法開始搜索，讓我們一一理解它們。

廣度優先搜索（BFS）

> fig 1. Step 1 in BFS

麗莎是一個有組織的女孩。 另外，知道她家附近的一些美容店。 她在紙上列出了他們的名字。 假設有一些商店A，商店B和商店C。她將在列表中輸入商店的名稱，并從上至下從A商店開始依次訪問A。！，A商店 沒有那種陰影，但他們建議她在其他商店購買。 她將這些名字列為Shop D和ShopE。她將緊隨其后。 下一站，商店B。他們又沒有了，但他們建議她去其他商店。 她也列出了它們，分別在F商店和G商店。接著，在C商店。現在她去了C商店。他們也沒有，但是他們不能向她推薦任何商店。 最后，Lisa的清單如下所示。

> fig 2. Step 2 in BFS

下一步，她將參觀商店A所有者建議的商店D。 如果他們沒有，他們也會建議她去其他商店。 她將這些商店添加到列表中，并繼續按順序逐個訪問商店，直到找到那該死的口紅。 她成功了。 她在商店G的老板建議的一家商店中找到了它。 那就是J店。讓我們畫一張她去過的所有這些商店的地圖。 兩個商店之間的連接表示該特定商店是另一商店建議的。 用正式術語來說，我們將此地圖稱為"圖形"，在這種情況下，稱為"樹"。

> fig 3. BFS MAP (The digits on the lines represents the sequence in which she visited those shops.)

這不是一件容易的事，但她得到了她最喜歡的口紅。 您可以觀察到，Lisa按順序依次去了同一位店主建議的商店。 我們將這種方法稱為廣度優先搜索（BFS）算法，因為我們首先搜索先前已知的所有可用選項，并添加新選項以供日后使用。 但是這種方法的問題在于它會產生冗余。 觀察商店K的情況，可以同時從商店F和商店G到達商店。而且她兩次拜訪商店的時間（請考慮自己是啞巴）。 BFS具有此規則以訪問方式訪問所有節點。 是否已經訪問過它們都沒關系。

深度優先搜索（DFS）

在我們以前的方法中，麗莎不得不走近10家商店才能獲得口紅。 讓我們看看是否可以使Lisa的搜索更加高效。 讓我們嘗試另一種方法。這次，Lisa將以不同于以往的方式列出建議的商店。 這次，當她從某個商店獲得建議時，會將其添加到列表的頂部。 最初的清單將有3家商店，與BFS相同。 參觀商店A后，她的清單如下所示。

> fig 4. step 1 in DFS

她將標記已經去過的商店。 她將遵循相同的自上而下的方法。 因此，她的下一站將是D商店。她將在頂部添加D商店和E商店。 商店D的老板告訴她去我的商店。她去了那里，但找不到唇膏，而我的老板的商店沒有告訴她任何其他商店。 麗莎參觀了E店上方的所有商店。現在她的清單看起來像這樣。

> fig 5. Step 2 in DFS

回到商店A的建議的過程正式稱為回溯。 商店E的所有者會告訴她去商店J（在列表頂部添加）和賓果游戲！ 她找到了她最喜歡的口紅。

讓我們再次放置該圖。

> fig 6. DFS MAP (The digits on the lines represents the sequence in which she visited those shops.)

麗莎走進了搜索樹的深處，而不是去同一層的商店。 我們稱這種方法為深度優先搜索算法。 從圖中可以看出，Lisa只需要拜訪5家商店，比我們的BFS方法要少得多。 因此，可以說我們的DFS方法比BFS更好。 另外，如果她本來要通過商店F訪問商店K，那么她就不會通過商店G訪問它。因為她已經標記了它。 因此，通過這種方法，她在那里不會多次訪問同一家商店。

Stack和Queue

讓我們關注麗莎的清單。 僅通過更改輸入新條目的方式，她就大大改善了搜索范圍。 我們將此列表稱為數據結構。 數據結構是一種將數據存儲在計算機內存中某處的方法。 就麗莎而言，她將其存儲在紙上。 但是，對于BFS和DFS，這種數據存儲方式是不同的。

在BFS中，她在列表的末尾添加了新元素，并以自上而下的方式遵循了列表。 在之前的列表（即先進先出（FIFO））之后，將訪問在她的列表中新添加的商店。 我們稱這種數據結構為隊列。 它的工作原理與我們在機場進行的排隊相同。 第一位客戶首先獲得服務。 在隊列中，從后面添加了新元素，而從前面刪除了舊元素，這正是Lisa在BFS中所做的。

在DFS中，Lisa在列表頂部添加了新元素。 她沒有更改自上而下的順序。 在這種方法中，較新的元素要先訪問較舊的元素，即后進先出（LIFO）。 我們將此數據結構稱為堆棧。 在堆棧中，從一端開始添加元素，然后從同一端刪除元素，就麗莎而言，這是她列表的頂部，在那里她添加了新商店并順序訪問了這些商店。

結論

由于兩個原因，DFS比BFS是更好的算法。

· 它不會在數據結構中創建冗余，因此不會訪問已經訪問過的同一節點。

· 它在計算上比BFS更輕松，更高效。

雖然，這兩種算法都存在一些問題。 如果我們有一個包含數千個節點（商店）的較大地圖，則這些算法無法高效地找到目標節點。 看一下DFS映射，如果我們將車間L作為目標節點，則DFS的性能不會比BFS好得多。 盡管BFS存在搜索所有節點的問題，但DFS可能會浪費時間在錯誤的方向上進行搜索。

為了解決這些問題，我們有更好的算法，例如AI系統中實際使用的啟發式算法。 但這是另一天的博客。