你所做的一切都是从搜索开始的！人工智能可以解决这些日常问题。让我们了解一下BFS、DFS等…

杰克斯洛普在Unsplash上拍摄的照片

纵观历史，人类一直在寻找事物。搜索造就了今天的我们。在古代，觅食者经常寻找生活必需品。他们创造了一些工具来简化搜索过程。人脑也在这个过程中进化。现在，它可以创建该区域的思维地图，而觅食者可以将该区域映射到自己的思维中，更有效地进行搜索。即使在现代，我们也基本上使用和以前一样的策略。但是现在，我们有了更先进的工具，我们的思想也更发达了。我们使用地图来寻找方法，谷歌地图等工具是我们如何发展自己以更有效地搜索的最好例子。

我们在搜索方面取得的最显著的进步要归功于技术的变革。在计算机科学中，我们称这个术语为算法。随着脑力的增强，我们创造了更复杂、更高效的算法。我们开发了这些解决方案来解决更复杂的问题。算法可以让我们的生活更简单，让我们更高效。从日常任务到创造世界级的人工智能，搜索算法是人类所有工作的基础。在这篇博客中，我们将看到两种基本的搜索算法，这将为我们理解更复杂的算法奠定基础。

不要让这个解释变得平淡无奇。我们将以现实生活(LoL)为例，来了解搜索本身的发展。好吧(？)

所以，显然我有女朋友Lisa(至少在我的想象中)。她对她使用的所有东西都很聪明，而且她很挑剔。几天前，她把口红丢在了某个地方。这是她最喜欢的影子。就像我说的，她很挑剔。她不会适应其他的影子或者其他任何品牌。但问题是口红很稀有，很害怕。现在，她打算买新的。我们附近的商店非常宽敞；如果没有，他们会引导她去其他商店。她可以从几种方式开始搜索，我们一个一个来了解。

广度优先搜索（BFS）

图一。在BFS

丽莎是一个有条理的女孩。另外，我知道她家附近有一些美容店。她在纸上列出了他们的名字。假设有一些店铺A，B，c，她会在列表中输入店铺的名称，从A店开始从上到下的访问A！A店没有那种影子，但是他们建议她去别的店买。她把这些名字列为D店和ShopE。她会紧紧跟随。下一站，b店，他们又没有了，但是建议她去别的店。她还把它们分别列在F店和G店。然后，在C店。现在她去了C店。他们也不知道，但是他们不能给她推荐任何商店。最后，Lisa的列表如下所示。

图二。在BFS

接下来她会去逛a店老板建议的D店，如果他们不去，也会建议她去别的店。她把这些店加到列表里，继续按顺序一家一家的逛，直到找到那该死的口红。她成功了。她在g店店主推荐的一家店里找到的，那是J店。让我们画一张她去过的所有这些商店的地图。两个商店之间的联系表明特定商店是由另一个商店建议的。用正式的术语来说，我们称这个地图为“图”，在这里是“树”。

图三。BFS地图(线上的数字代表她去那些商店的顺序。)

这不是一个简单的任务，但她得到了她最喜欢的口红。你可以观察到丽莎依次去了同一个店主推荐的商店。我们称这种方法为广度优先搜索(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系统中实际使用的启发式算法。 但这是另一天的博客。

(本文翻译自Arshad Kazi的文章《Search Algorithms In Artificial Intelligence》，参考：https://towardsdatascience.com/search-algorithms-in-artificial-intelligence-5332fc560c74)