无规则采集器列表算法(：如何在日常任务到创建世界一流的人工智能？)

　　无规则采集器列表算法(：如何在日常任务到创建世界一流的人工智能？)

　　描述

　　您所做的一切都始于搜索！人工智能可以解决这些日常问题。让我们了解 BFS、DFS 等...

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

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

　　不要让这个解释变得简单。我们将以现实生活（LoL）为例来了解搜索本身的发展。行（？）

　　所以很明显我有一个女朋友丽莎（至少在我的想象中）。她对她使用的一切都很聪明，而且非常挑剔。几天前，她的口红在某处丢失了。这是她最喜欢的阴影。就像我说的她很挑剔，她不会适应其他色调或任何其他品牌。但问题是口红非常稀有，让人害怕。现在她打算买新的。我们附近的商店非常宽敞；如果他们没有，他们会引导她去其他商店。她可以通过多种方式开始搜索，让我们一一了解。

　　广度优先搜索 (BFS)

　　> 图 1. BFS 中的第 1 步

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

　　> 图 2. BFS 中的第 2 步

　　接下来，她会去A店老板推荐的D店，如果他们不去，他们也会建议她去其他店。她把这些店铺都加到了名单上，继续一个一个的逛店铺，直到找到那只该死的口红。她成功了。她是在G店老板推荐的一家店里找到的。那就是J店。让我们画一张她去过的所有这些商店的地图。两个商店之间的连接表明该特定商店是由另一家商店推荐的。在正式的术语中，我们称这张地图为“图形”，在本例中为“树”。

　　> fig 3. BFS MAP（线条上的数字代表她访问这些商店的顺序。）

　　这不是一件容易的事，但她得到了她最喜欢的口红。可以观察到，Lisa 依次去了同一个店主推荐的店铺。我们称这种方法为广度优先搜索 (BFS) 算法，因为我们首先搜索所有以前已知的可用选项并添加新选项以供将来使用。但是这种方法的问题在于它会产生冗余。观察K店的情况，可以同时从F店和G店到达该店。还有那次她两次光顾这家店（请认为她很笨）。BFS 有这个规则，以一种访问方式访问所有节点。您是否访问过它们并不重要。

　　深度优先搜索 (DFS)

　　在我们之前的方法中，Lisa 必须步行到 10 家商店才能拿到口红。让我们看看我们是否可以让 Lisa 的搜索更有效率。让我们尝试另一种方法。这一次，Lisa 将以不同的方式列出建议的商店。这一次，当她从商店收到建议时，她会将其添加到列表的顶部。初始列表将有 3 个商店，与 BFS 相同。访问A店后，她的名单如下所示。

　　> 图 4. DFS 中的第 1 步

　　她会标记她去过的商店。她将遵循相同的自上而下的方法。因此，她的下一站将是D店。她将在顶部添加 D 商店和 E 商店。D店的老板让她去我的店。她去了那里，但找不到口红，我老板的店也没有告诉她其他店的情况。丽莎走遍了E店楼上的所有店铺。现在她的名单是这样的。

　　> 图 5. DFS 中的第 2 步

　　推荐的返回 A 店的过程正式称为回溯。E 店的老板会告诉她去 J 店（添加在列表顶部）和宾果游戏！她找到了她最喜欢的口红。

　　让我们再次放置图形。

　　> fig 6. DFS MAP（线条上的数字代表她访问这些商店的顺序。）

　　丽莎深入搜索树，而不是去同一层的商店。我们称这种方法为深度优先搜索算法。从图中可以看出，Lisa 只需要访问 5 个商店，这比我们的 BFS 方法要少得多。因此，可以说我们的 DFS 方法优于 BFS。另外，如果她要通过商店F访问商店K，她不会通过商店G访问它。因为她已经标记了它。因此，通过这种方法，她不会多次光顾同一家商店。

　　堆栈和队列

　　让我们来看看丽莎的清单。通过改变她输入新条目的方式，她极大地扩大了她的搜索范围。我们称这个列表为数据结构。数据结构是一种将数据存储在计算机内存中的方法。在丽莎的情况下，她把它存储在纸上。但是，对于 BFS 和 DFS，这种数据存储方式是不同的。

　　在 BFS 中，她将新元素添加到列表的末尾，并以自上而下的方式跟随列表。在前一个列表之后（即先进先出（FIFO）），将访问她列表中新添加的商店。我们称这种数据结构为队列。它的工作原理与我们在机场的队列相同。第一个客户是最先服务的。在队列中，新元素从后面添加，旧元素从前面删除，这正是Lisa在BFS中所做的。

　　在 DFS 中，Lisa 在列表顶部添加了一个新元素。她没有改变从上到下的顺序。在此方法中，较新的元素首先访问较旧的元素，即后进先出 (LIFO)。我们称这种数据结构为堆栈。在堆栈中，从一端添加元素，然后从同一端删除元素。在 Lisa 的案例中，这是她列表的顶部，她在其中添加了新商店并按顺序访问了它们。

　　综上所述

　　出于两个原因，DFS 是比 BFS 更好的算法。

　　· 它不会在数据结构中创建冗余，因此不会访问已经访问过的相同节点。

　　· 比BFS计算更简单，效率更高。

　　虽然，这两种算法都有一些问题。如果我们有一个收录

数千个节点（商店）的大地图，这些算法无法有效地找到目标节点。从DFS映射来看，如果我们以车间L为目标节点，DFS的性能不会比BFS好多少。虽然 BFS 存在搜索所有节点的问题，但 DFS 可能会浪费时间在错误的方向搜索。

　　为了解决这些问题，我们有更好的算法，比如 AI 系统中实际使用的启发式算法。但这是另一天的博客。