人工智能的兩種最基本搜索算法

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

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

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

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

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

廣度優(yōu)先搜索（BFS）

> fig 1. Step 1 in BFS

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

> fig 2. Step 2 in BFS

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

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

這不是一件容易的事，但她得到了她最喜歡的口紅。 您可以觀察到，Lisa按順序依次去了同一位店主建議的商店。 我們將這種方法稱為廣度優(yōu)先搜索（BFS）算法，因?yàn)槲覀兪紫人阉飨惹耙阎乃锌捎眠x項(xiàng)，并添加新選項(xiàng)以供日后使用。 但是這種方法的問題在于它會(huì)產(chǎn)生冗余。 觀察商店K的情況，可以同時(shí)從商店F和商店G到達(dá)商店。而且她兩次拜訪商店的時(shí)間（請考慮自己是啞巴）。 BFS具有此規(guī)則以訪問方式訪問所有節(jié)點(diǎn)。 是否已經(jīng)訪問過它們都沒關(guān)系。

深度優(yōu)先搜索（DFS）

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

> fig 4. step 1 in DFS

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

> fig 5. Step 2 in DFS

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

讓我們再次放置該圖。

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

麗莎走進(jìn)了搜索樹的深處，而不是去同一層的商店。 我們稱這種方法為深度優(yōu)先搜索算法。 從圖中可以看出，Lisa只需要拜訪5家商店，比我們的BFS方法要少得多。 因此，可以說我們的DFS方法比BFS更好。 另外，如果她本來要通過商店F訪問商店K，那么她就不會(huì)通過商店G訪問它。因?yàn)樗呀?jīng)標(biāo)記了它。 因此，通過這種方法，她在那里不會(huì)多次訪問同一家商店。

Stack和Queue

讓我們關(guān)注麗莎的清單。 僅通過更改輸入新條目的方式，她就大大改善了搜索范圍。 我們將此列表稱為數(shù)據(jù)結(jié)構(gòu)。 數(shù)據(jù)結(jié)構(gòu)是一種將數(shù)據(jù)存儲(chǔ)在計(jì)算機(jī)內(nèi)存中某處的方法。 就麗莎而言，她將其存儲(chǔ)在紙上。 但是，對于BFS和DFS，這種數(shù)據(jù)存儲(chǔ)方式是不同的。

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

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

結(jié)論

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

· 它不會(huì)在數(shù)據(jù)結(jié)構(gòu)中創(chuàng)建冗余，因此不會(huì)訪問已經(jīng)訪問過的同一節(jié)點(diǎn)。

· 它在計(jì)算上比BFS更輕松，更高效。

雖然，這兩種算法都存在一些問題。 如果我們有一個(gè)包含數(shù)千個(gè)節(jié)點(diǎn)（商店）的較大地圖，則這些算法無法高效地找到目標(biāo)節(jié)點(diǎn)。 看一下DFS映射，如果我們將車間L作為目標(biāo)節(jié)點(diǎn)，則DFS的性能不會(huì)比BFS好得多。 盡管BFS存在搜索所有節(jié)點(diǎn)的問題，但DFS可能會(huì)浪費(fèi)時(shí)間在錯(cuò)誤的方向上進(jìn)行搜索。

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