AI和图形搜索

赞
使用AI进行图表搜索
通常，当我查看一些与AI相关的主题，教程或文章时，我发现图形搜索问题是作为AI如何工作的示例蜂拥呈现的。那么，为什么呢？一些经典的图搜索问题和AI之间有什么关系？

什么是人工智能？


人工智能似乎没有非常明确单一的定义。让我们看一下经典的路径寻找问题。我们有一个包含许多节点的图表，你尝试在两个节点之间找到具有最小成本的路径。你不明确地知道路径是什么，AI通过感知环境，在我们的例子中，图表将找到那条路径。
但我们知道有许多算法能够解决图搜索问题。只需看看DFS，BFS，Dijkstra或A *。我们中的一些人从高中就知道这个算法。那么这里有什么新东西？这是AI的作用吗？是的，但它不仅仅能做这些。人工智能不仅是一种编程范式，如图搜索算法，但正如我之前所说，这是一项研究环境并试图选择具有最佳结果方法。
AI是一个广义的术语。它们涉及机器学习，神经网络，深度学习等等，它们被用于金融，医疗机构，安全等，因此图搜索只是AI的一个小子类型。
经典图搜索算法和能够找到两个节点之间最短路径的AI之间的区别只是术语的差异。

经典老派算法


有许多方法可以实现图搜索。有像BFS和DFS这样的经典算法能够在不计算最佳路径的情况下找到目标节点，并且有一些算法，如Unifrom Cost搜索，Dijkstra或A *，它们能够计算从源到a的最短路径。目标。所有这些算法都是基于树的算法，唯一的问题是与树不同，图可能包含周期。
所有这些算法的要点是，在我们访问节点之后，我们必须选择下一个未访问的节点并“访问”它以查看我们是否达到了目标。

关于BFS


就像我之前说过的，广度优先搜索是一种基于树的算法。它的名字来源于图遍历是分层的。从源节点开始，我们首先探索邻居，然后再向下移动。
我们来看下面的图片：

从节点A开始，我们看到这个图形如何变成树。
A是停留在第0层的起始节点，然后B和C在第1层上，然后D和E在第2层上。这是BFS将遍历此图的顺序。
如果我们使用BFS遍历此图，则顺序为：A - > B - > C - > D - > E.
仔细观察树，我们将看到B和C以及E和D之间存在一些联系。这是因为我们的图包含循环。但是如果我们想要以最佳方式遍历它，我们就不应该再次访问已经访问过的节点。因此，选择要访问的节点的一个条件是不可访问的。

算法如何工作


考虑到这一点，在我们访问起始节点后，我们将继续访问其所有邻居，然后我们将进入下一个“层”并需要一个队列。当我们访问节点时，我们检查它的邻居，如果没有访问邻居，我们将它们添加到队列中。然后，我们实际上只是从队列中选择要访问的下一个节点。我们需要做的另一件事是将访问过的节点标记为不再访问它们。这样，我们将只访问所有图形节点一次。
我们来看看伪代码：
 1BFS(G, s, goal)
 2  Let Q be queue
 3  Q.enqueue(s)
 4  Mark s as visited
 5  while (Q is not empty)
 6    //Removing that vertex from queue
 7    v = Q.dequeue()
 8    If v is goal 
 9      return “found the goal”
10    //processing all the neighbours of v  
11    for all neighbours w of v in Graph G
12      if w is not visited 
13        //Stores w in Q to further visit its neighbour
14        Q.enqueue(w)                                     
15        mark w as visited

因此，使用此算法，如果起始节点和目标之间至少存在路径，我们就能够找到任何节点。

寻找最短路径


让我们通过在顶点上添加一些成本来更改我们的图形。

现在我们想要在成本最低的路径上从A到D。我们看到从A到D有多种方式。我们可以走这条路，A - > B - > D，成本为20，或者我们可以选择A - > C - > B - > D，成本更低16但是还有另一条成本最低的路径3，A - > C - > E - > D.那么，我们应该怎样做才能找到这条路？我们需要改变获取下一个节点的方式。在经典的BFS算法中，我们使用FIFO队列顺序选择下一个要访问的节点（先进先出，然后进入）。我们最终会找到目标而不是最便宜的路径。为了在成本最低的路径上实现目标，我们需要对从队列中访问下一个节点的方式进行更改。
我将向您呈现的算法称为统一成本搜索，它是Dijkstra的略微修改版本，我们在找到目的地时停止。经典的Dijkstra算法继续访问所有节点，直到队列为空，找到从起始节点到图中每个其他节点的最低成本。与BFS的不同之处在于，我们必须存储一个新值，表示从开始到当前访问节点的总成本。
FIFO规则不会对队列进行排序，相反，我们将根据当前成本到目前为止的值对队列进行排序，优先考虑到目前为止成本最低的未访问节点。
我们来看看代码：
 1UniformCostSrearch(G, s)
 2  s.costSoFar = 0;
 3  for all nodes w in G except s
 4    w.costSoFar = Int.maxInt
 5  Let Q be a priority queue ordered by cost_so_far
 6  Q.enqueue(s)
 7  while (Q is not empty)
 8    //Removing that vertex from queue
 9    v = Q.dequeue()
10    If v is goal
11      return “found the goal” 
12    //processing all the neighbours of v  
13    for all neighbours w of v in Graph G
14      currentCost = dist[v,w]
15      newCost = v.costSoFar + currentCost;
16      If (newCost < w.costSoFar)
17        w.costSoFar = newCost ;
18        Q.enqueue(w)

这样，我们将根据每个节点到目前为止的最低成本选择要访问的下一个节点。
但到目前为止，最低成本需要更新，因为通过探索图表，我们总能找到更好的方式来到达节点。为此，当我们访问一个节点时，我们看看它的所有邻居，然后我们将它们当前的成本与新成本进行比较，这是迄今为止访问节点的成本与该节点与其之间的距离之间的总和。邻居：
1currentCost = dist[v,w]
2newCost = v.costSoFar + currentCost;
3If (newCost  < w.costSoFar) {
4  w.costSoFar = newCost ;
5  Q.enqueue(w);
6}

如果新成本较低，这意味着我们找到了更好的方式来到达该节点，并且我们到目前为止更新了该成本。在这里，您可以看到有关此算法的更多详细信息，以及如何通过使用某种估算来改进它，从而将其转换为A *。

图搜索和人工智能之间的关系


我们用图搜索算法得到了什么？我们得到一个函数，一个程序，给定一个图形，一个环境和一个起始节点，通过考虑过去和当前的感知，计算一系列用于找到目标节点的动作。
考虑到AI概念，让我们编写一个AI代理来分析环境并计算一系列可以帮助我们实现目标的操作（我们基本上会构建一个图搜索算法但使用AI术语）。
以下是罗马尼亚的地图：

我们在阿拉德，我们想以最短的路径前往布加勒斯特。我们可以看到我们可以采取多种途径。我们可以从Arad到Timisoara，然后是Lugoj，等等，或者我们可以选择Sibiu然后Fagaras直接去布加勒斯特。但我们不知道哪条路的成本最低。

什么是问题的定义？

可以分解问题：
  • 初始状态：在阿拉德；
  • 当我们处于某个州时，它会返回一组可能的操作。例如：在阿拉德，我们可以去Zerind，Sibiu或Timisoara；
  • 函数结果（s，a） - > s'，在州，如果我们采取行动a，我们将去s'；
  • 目标测试功能goaltest（s） - > t / f，它告诉我们是否达到了目标；
  • step_cost（s，a，s'） - >行动成本，它告诉我们使用动作a从s到s'的步骤成本；
  • 成本（S1 - > S2 - > ...... - > Sn） - > n（路径成本），总路径成本；
现在让我们看看这是如何映射我们的目标寻找问题的。最初的状态是在阿拉德，如果我们到达布加勒斯特，目标测试功能将返回。所有可能的状态称为状态空间。从Arad开始并应用函数动作（“Arad”），我们将得到三个可能的动作。去Zering，Timisoara或Sibiu。现在，考虑到这一点，我们可以将状态空间分为三个部分：
  • 探索的州的一部分（例如现在只是阿拉德）
  • 有边疆。我们称之为已经探索过的最远的州（蒂米什瓦拉，泽林德和锡比乌）
  • 未开发的州：所有其他城市
因此，在状态的探索部分，我们需要从边界选择一个新状态，应用一个动作，然后移动到该状态，从而扩展边界。
 1TreeSearch(G, s)
 2  s.costSoFar = 0;
 3  for all nodes w in G except s
 4    w.costSoFar = Int.maxInt
 5  Let frontier be a priority queue ordered by  the cost_so_far
 6  frontier.enqueue(s)
 7  while (frontier is not empty)
 8    //Removing that vertex from frontier,whose neighbour will be visited now
 9    v = frontier.dequeue()
10    If v is goal
11      return “found the goal” 
12    //processing all the neighbours of v  
13    for all neighbours w of v in Graph G
14      currentCost = dist[v,w]
15      newCost = v.costSoFar + currentCost;
16      If (newCost  < w.costSoFar) {
17        w.costSoFar = newCost ;
18        frontier.enqueue(w)

因此，我们有一个边界，首先，它只包含在起始节点中。然后，在每次迭代中，我们从边界获得一个元素，我们移动到下一个状态，如果我们到达目标，我们退出“找到目标”的消息。或者，我们也可以打印路径。否则，我们将新状态添加到边界。
现在，根据您从边界获取新状态的方式，您可以实现经典的BFS，统一的成本搜索或A *算法。在这里，您可以更清楚地看到这些算法与检测从Arad到布加勒斯特的最短路径的最佳算法之间的差异。

总结


我们有用于人脸识别的AI算法，有机器学习，神经网络和基于统计的算法，其中唯一的限制是数学。但这并不一定要害怕，因为基本概念并不难理解。

长按订阅更多精彩▼

如有收获，点个在看，诚挚感谢