人工智能中的图搜索

引言

图搜索是人工智能中的一种重要方法，它通过结构化的、由相互关联的数据元素（称为节点）和边组成的数据结构来帮助移动。这些结构，称为图，被应用于不同领域，以模拟社交网络、配送系统、网站导航、视频游戏等中的关系。图搜索算法可以被描述为允许人工智能系统与这些结构交互并找到解决方案的方法。因此，这些算法在解决问题和一般决策制定中至关重要。

在人工智能中，在关系至关重要的环境中会使用图，例如导航系统中的路径查找或社交网络系统中的聚类。对这些性能的验证和确认有助于检查人工智能系统是否会依赖于图搜索算法的选择，这些算法以结构化的方式规划搜索路径，以期得出最佳解决方案。

图搜索算法普遍应用于任何人工智能应用中，例如机器人路径规划、复杂网络分析、自然语言处理，甚至游戏内人工智能。由于在各种管理情况下的灵活性，它们在解决涉及关系和连通性问题方面非常有用。高效图搜索算法的进步将继续推动人工智能的边界，特别是在环境日益复杂的情况下。

图搜索中的关键概念

节点和边

• 节点（顶点）：图中的节点，对应对象、状态或任何数据。
• 边：节点之间的链接，边可以表示节点之间的关系，或者从一个节点到另一个节点的移动，可以是直接的或双向的。

图的表示

• 邻接表：一种对图进行建模的技术，其中每个节点都包含一个邻接节点列表。
• 邻接矩阵：一个二维数组，行和列是节点，它们相互关联，单元格的值表示连接。
• 边列表：图中所有已定义边的列表，形式为第一个连接节点和第二个连接节点。

路径查找

• 路径：通过边连接的节点向量；图中的路径。
• 最短路径：连接两个节点的最短路径，边权重之和最小。Dijkstra 和 Bellman-Ford 是用于路径查找的其他类型的算法，很可能给出最短路径。
• 路径成本：遍历权重或成本的总和，这是优化特定路径的关键。

启发式算法

• 启发式函数：一种估计技术，用于计算从任何当前节点到最后一个或目标节点的成本，这有助于像 A* 这样的聚焦搜索。
• 可接受的启发式：该启发式不会给出比实际成本更远的解决方案，如果必须达到目标。

图搜索属性

• 完备性：指示搜索算法在存在解决方案的情况下是否始终能找到解决方案。
• 最优性：指所发现的解决方案是最优的。
• 时间复杂度：评估时间复杂度，通常以扩展的节点数表示。
• 空间复杂度：因此，它衡量算法在搜索过程中存储的节点相对于内存的使用情况。

遍历技术

• 图遍历：系统地遍历图中所表示的每个实体。
• 前序、中序和后序：能够从树结构中的一点移动的技术，主要源于图论中的二叉树。

连接性

• 连通图：图中任意两个节点都可以找到直接连接的图。
• 不连通图：图的连通分量彼此不关联。
• 强连通：在有向图中，所有节点都连接到所有其他节点。
• 弱连通：在有向图中，节点在不考虑方向的情况下是可达的。

加权图和无权图

• 加权图：边被权重或成本标记的图，用于涉及成本优化的计算。
• 无权图：图中所有边的值都相同，大多数情况下，相关的是步数。

广度优先搜索

广度优先搜索 (BFS) 是一种在图中系统地、逐层地搜索节点的算法。它从一个起始节点开始，然后评估所有相邻节点，然后遍历这些邻居的邻居，依此类推，直到到达终止节点或所需节点。BFS 通常用于需要识别起始节点邻居的情况。

BFS 如何工作？

BFS 使用队列数据结构来维护要访问的节点。

• 初始化：将起始节点插入队列，并将其状态标记为已访问。
• 处理节点：从队列中移除第一个元素，或弹出队列的第一个元素。我们需要对节点执行某些操作，例如打印它或检查它是否等于目标。
• 入队邻居：将所有尚未访问过的邻居入队，并将它们标记为已访问。
• 重复：持续调用出队节点并入队邻居节点，直到队列为空或找到感兴趣的节点。

这确保了 BFS 可以在访问距离起始节点更远的节点之前，检查所有离起始节点最近的节点。

BFS 用于什么？

• 无权图中的最短路径：再次强调，当边的权重相同时，BFS 是确定两个节点之间最短路径的首选方法。
• 连通性检查：BFS 的一个应用是确定图中的所有节点是否都可以从特定节点访问。
• 层序遍历：BFS 是一种遍历树的层的方法，在处理层次数据时可能很有用。
• 网络分析：它在社交网络分析中起着重要作用，以了解网络是否连通，或者我们与网络中的某人相距多少步。
• 迷宫或网格搜索：它用于逃离迷宫和在以网格布局的地图上找到出路。

深度优先搜索

深度优先搜索 (DFS) 遍历图，其中整个树被尽可能深地遍历，然后再回溯到其他分支。它具有回溯的性质，可以解决所有节点或证明图是否包含目标。它与深度优先搜索结合使用，用于搜索问题的更深阶段或可能隐藏在搜索图深处的解决方案。

DFS 如何工作？

DFS 使用堆栈数据结构来存储节点，无论是直接使用栈顶空间还是间接使用递归。

• 初始化：选择一个任意节点，将其标记为已访问，并将其添加到堆栈（或作为参数传递）。
• 探索节点：我们从堆栈中移除的第一个节点将被考虑，然后我们继续下一步。如果当前节点是目标节点，则停止。
• 入栈邻居：从堆栈中弹出一个节点；如果未访问，则将其标记为已访问，然后将其所有未访问的邻居压入堆栈。
• 回溯：如果没有这样的节点，则通过存储在堆栈中的节点进行回溯，并将它们视为前一个级别。
• 重复：重复此过程，直到堆栈耗尽或找到目标解决方案。

这样 DFS 就可以深入一个路径，然后再扩展到其他路径。

DFS 用于什么？

• 迷宫或谜题中的路径查找：DFS 广泛用于涉及深入路径的问题，例如迷宫、谜题等。
• 图中的环检测：在 DFS 中，如果一个有向或无向图节点被访问，它可以找到环。
• 拓扑排序：在依赖项解析 DAG 中，DFS 用于任务排序，因为该算法是拓扑的。
• 连通分量识别：DFS 查找连通图中的不同连通分量。

启发式搜索算法

启发式搜索算法是人工智能搜索技术的一类。搜索空间必须通过对问题解决区域的额外知识来增强，以便更快、更有效地搜索目标。这种知识通常表示为启发式函数，该函数定义了到目标的成本估计或距离，以便这些算法可以集中于此工作。

搜索引擎如何运作？

启发式搜索中的基于优先级的内存选择算法提供了一个标准来确定下一个要探索的节点。

• 初始化：从给定的状态开始，将此状态传递给启发式函数，并将其与目标状态进行比较。此状态应放置在优先级队列（也称为开放列表）中，并按启发式值排序。
• 节点选择：从开放列表中选择要用于探索的节点的过程称为反向传播，这意味着选择具有最高优先级（启发式函数值最小）的节点。
• 扩展：生成可能从当前节点产生的子节点，以到达下一个节点。计算每个后继节点的启发式值，并将其放入优先级队列。
• 目标测试：应检查当前节点是否为目标状态。如果是，则停止并返回到目标的路径或进行讨论。

重复此过程，直到可能达到目标状态或所有节点都被探索到最后一个级别。

启发式搜索算法是什么？

• 路径查找：像 A* 这样的算法被认为是导航系统、机器人和游戏人工智能路径查找的最佳选择。
• 优化问题：这些算法用于物流、资源分配和时间安排问题。
• 复杂游戏求解：这些算法有助于像国际象棋这样的游戏，提供获胜方向。
• 路线规划：示例包括创建旅行路线图或分发货物/服务。

A* 搜索算法

A* 搜索算法是人工智能中更著名的启发式搜索技术之一，用于在图中搜索最短路径。它是Dijkstra 算法最短路径和贪婪最佳优先搜索速度的结合，通过使用启发式。

A* 搜索如何工作？

初始化：从基本状态（起始顶点）开始。第一个数据结构，优先级队列，更常称为开放列表，被创建并包含起始节点。此队列基于节点估计的总成本进行排序。

成本计算：A* 使用两个基本函数

• g(n)：从网络起点到达节点 n 的成本。
• h(n)：评估从 n 到目标状态的成本的启发式函数。
• A* 将它们结合成一个总成本函数。
• 因此，新的方程是 f(n) = g(n) + h(n)，它表示到达目标节点 n 的估计总成本（g(n)）以及从 n 到目标的估计成本（h(n)）。

节点扩展：迷宫选择开放列表中 f(n) 值最低的节点进行扩展。这是通过将该特定节点设为当前节点来完成的。

后继节点生成：生成当前节点的后继节点。对于每个后继节点

确定其 g(n) 和 h(n)。

然后应将新列表和总 f(n) 分数添加到开放列表中。

节点在被发现时需要被标记，这只能通过使用所谓的闭集来实现。

目标测试：如果任何生成的节点满足目标，则过程终止，并回溯到目标的路径。

重复：在循环中继续此过程，直到满足以下两个条件之一：找到了目标节点，或者开放列表中的所有节点都已用尽。

A* 用于什么？

• 导航和路径查找：在地图系统、机器人或视频游戏中用于确定两个点之间的最优路径。
• 谜题求解：在 8-puzzle 或 15-puzzle 等问题中，用于确定到目标的最佳路径长度。
• 网络路由：在路由协议中用于查找网络中的最佳路径。

图搜索在 AI 中的应用

机器人路径查找

路径搜索算法在机器人领域是必不可少的一个关键领域，因为它们涉及导航和运动计算。对于导航，机器人采用 A* 或 Dijkstra 等路径或技术来避免与障碍物碰撞，并以最快、最安全的方式从一个点移动到另一个点。这些算法将地图或网格视为图，节点是位置，边代表可能的移动，从而使机器人能够自主移动。

自然语言处理

图搜索在自然语言处理中用于语法解析、机器翻译和信息提取。例如，在依存关系解析中，句子的词被视为节点，它们之间的语法关系被视为边。算法主动搜索这些图以检测句子结构、上下文或翻译的最优路径，从而增强对语言的理解和处理。

社交网络分析

从社交网络角度来看，社交网络点被建模为图，其中最终用户是节点，链接（可能是朋友或互动）是边。图搜索算法有助于分析这些网络，以识别有影响力的用户和社区，或推荐合适的连接。这种分析有助于区分共同兴趣的领域，并随后进行营销，在社交研究中进行人际互动，并在欺诈检测案例中进行应用。

游戏 AI

一些活动涉及游戏内决策制定和策略制定，这些都应用了图搜索算法。对于棋盘游戏，游戏的当前状态可以被图化；在每一步游戏中，玩家进行一次移动，并最终到达另一个节点的状态。诸如 Minimax 等策略，有时与图搜索结合使用，可以考虑潜在的未来移动以选择最佳路径，从而提高 AI 的游戏理解能力。

知识表示和推理

人工智能系统中使用的图搜索（例如语义网络）可以帮助搜索信息、关系和解决方案，通常用于回答问题。推荐系统、问答系统和本体管理等人工智能应用程序利用这些算法来搜索并找到其在大规模复杂数据网络中的路径。这使得人工智能系统能够模仿对大数据集的推理。

计算机视觉

在计算机视觉中，图搜索技术已被用于识别对象、分割图像和理解场景。图像中的连接点可以被视为节点，图割等算法对于识别对象或它们之间的边界非常有用。它们有助于找到常用于人脸检测和医学成像的焦点区域，并指导自动驾驶汽车进行导航。

高级图搜索技术

双向搜索

双向搜索是对传统搜索过程的优化。它不以经典搜索模式从给定的初始位置（起始节点）朝向期望状态（目标）进行操作，而是同时进行两个并行搜索：一个朝向目标，另一个朝向起始节点。当两个搜索相遇时，就得到了最短路径。这种方法比花费的时间节省了更多的步骤，使其适用于大型网络或地图中的路径查找。例如，这可以用于导航系统和计算机网络中的流量引导。

迭代加深搜索 (IDS)

迭代加深搜索是一种搜索算法，它同时具备 DFS 的空间效率和 BFS 的完备性。IDS 通过多次调用 DFS 并增加深度来运行，直到找到解决方案。这种方法在解决方案深度不确定的情况下最有价值。因此，该算法在搜索最优解决方案的过程中不会陷入无限分支，同时仍会抛弃不理想的路径。这经常用于 GAI 和必须充分优化每一字节内存的情况。

启发式搜索

启发式搜索通过利用问题区域中已有的信息来评估节点到目标的接近程度来寻找解决方案。因此，与最佳优先搜索类似，它在节点上提供了一个启发式函数，该函数应该能够引导到目标，从而最大限度地减少需要搜索的节点数量。这使其比 BFS 等盲目搜索算法更快。A* (A-star) 等方法是启发式搜索的例子，常用于路线规划、机器人和解谜，因为它们能快速找到最短路径。

结论

总而言之，图搜索是人工智能领域的一个分支，它是一种模式问题解决方法，用于在大型问题域中进行决策。图搜索技术为解决人工智能问题提供了多种可能性，从最简单的技术，如 BFS 和 DFS，到更复杂的技术，如 A* 和 MCTS。这些算法被广泛应用于路径查找、游戏人工智能、网络优化和战略规划等领域。因此，图搜索方法远未被新的人工智能技术取代，并且在各个领域处理更复杂的问题方面仍然至关重要。