路径搜索算法（Pathfinding and Search Algorithms）探索一个图，用于一般发现或显式搜索。这些算法通过从图中找到很多路径，但并不期望这些路径是计算最优的（例如最短的，或者拥有最小的权重和）。图搜索算法包括广度优先搜索和深度优先搜索，它们是遍历图的基础，并且通常是许多其他类型分析的第一步。
路径搜索（Pathfinding）算法建立在图搜索算法的基础上，并探索节点之间的路径。这些路径从一个节点开始，遍历关系，直到到达目的地。路径搜索算法识别最优路径，用于物流规划，最低成本呼叫或者叫IP路由问题，以及游戏模拟等。
**
DFS & BFS
图算法中最基础的两个遍历算法：广度优先搜索（Breadth First Search，简称 BFS）和深度优先搜索（Depth First Search，简称 DFS）。BFS 从选定的节点出发，优先访问所有一度关系的节点之后再继续访问二度关系节点，以此类推。DFS 从选定的节点出发，选择任一邻居之后，尽可能的沿着边遍历下去，直到不能前进之后再回溯。
下面是两张同样的图，分别采用 BFS 和 DFS 进行图的遍历，图上节点的数字标识这遍历顺序。
BFS
DFS
对于数据科学的角色来说，我们很少真正需要使用 BFS 和 DFS。这两个图搜索算法更多地作为底层算法支持其他图算法。例如，最短路径问题和 Closeness Centrality （在后文会有介绍）都使用了 BFS 算法；而 DFS 可以用于模拟场景中的可能路径，因为按照 DFS 访问节点的顺序，我们总能在两个节点之间找到相应的路径。
最短路径
最短路径（Shortest Paths）算法计算给定的两个节点之间最短（最小权重和）的路径。算法能够实时地交互和给出结果，可以给出关系传播的度数（degree），可以快速给出两点之间的最短距离，可以计算两点之间成本最低的路线等等。例如：
- 导航：谷歌、百度、高德地图均提供了导航功能，它们就使用了最短路径算法（或者非常接近的变种）；
- 社交网络关系：当我们在 LinkedIn、人人（暴露年龄了）等社交平台上查看某人的简介时，平台会展示你们之间有多少共同好友，并列出你们之间的关系。
最常见的最短路径算法来自于 1956 年的 Edsger Dijkstra。Dijkstra 的算法首先选择与起点相连的最小权重的节点，也就是 “最临近的” 节点，然后比较起点到第二临近的节点的权重与最临近节点的下一个最临近节点的累计权重和，从而决定下一步该如何行走。可以想象，算法记录的累计权重和如同地理的 “等高线” 一样，在图上以 “波” 的形式传播，直到到达目的地节点。
最短路径算法有两个常用的变种：A （可以念作 A Star）algorithm 和 Yen’s K-Shortest Paths。A algorithm 通过提供的额外信息，优化算法下一步探索的方向。Yen’s K-Shortest Paths 不但给出最短路径结果，同时给出了最好的 K 条路径。
所有节点对最短路径（All Pairs Shortest Path）也是一个常用的最短路径算法，计算所有节点对的最短路径。相比较一个一个调用单个的最短路径算法，All Pairs Shortest Path 算法会更快。算法并行计算多个节点的信息，并且这些信息在计算中可以被重用。
下图是从 A 节点开始的计算过程。
All Pairs Shortest Path 算法通常用于，当最短路径受限或者变成了非最优时，如何寻找替代线路。其实算法非常常用：
- 优化城市设施的位置和货物的分配：例如确定运输网格中不同路段上预期的交通负荷，例如快递线路设计，从而保证运输对突发事件的应对；
- 作为数据中心设计算法的一部分：查找具有最大带宽和最小延迟的网络。
最小生成树**
最小生成树（Minimum Spanning Tree）算法从一个给定的节点开始，查找其所有可到达的节点，以及将节点与最小可能权重连接在一起，行成的一组关系。它以最小的权重从访问过的节点遍历到下一个未访问的节点，避免了循环。
最常用的最小生成树算法来自于 1957 年的 Prim 算法。Prim 算法与Dijkstra 的最短路径类似，所不同的是， Prim 算法每次寻找最小权重访问到下一个节点，而不是累计权重和。并且，Prim 算法允许边的权重为负。
上图是最小生成树算法的步骤分解，算法最终用最小的权重将图进行了遍历，并且在遍历的过程中，不产生环。
算法可以用于优化连接系统（如水管和电路设计）的路径。它还用于近似一些计算时间未知的问题，如旅行商问题。虽然该算法不一定总能找到绝对最优解，但它使得复杂度极高和计算密集度极大的分析变得更加可能。例如：
- 旅行计划：尽可能降低探索一个国家的旅行成本；
- 追踪流感传播的历史：有人使用最小生成树模型对丙型肝炎病毒感染的医院暴发进行分子流行病学调查。
随机游走
随机游走（Random Walk）算法从图上获得一条随机的路径。随机游走算法从一个节点开始，随机沿着一条边正向或者反向寻找到它的邻居，以此类推，直到达到设置的路径长度。这个过程有点像是一个醉汉在城市闲逛，他可能知道自己大致要去哪儿，但是路径可能极其“迂回”，毕竟，他也无法控制自己~
随机游走算法一般用于随机生成一组相关的节点数据，作为后续数据处理或者其他算法使用。例如：
- 作为 node2vec 和 graph2vec 算法的一部分，这些算法可以用于节点向量的生成，从而作为后续深度学习模型的输入；这一点对于了解 NLP （自然语言处理）的朋友来说并不难理解，词是句子的一部分，我们可以通过词的组合（语料）来训练词向量。那么，我们同样可以通过节点的组合（Random Walk）来训练节点向量。这些向量可以表征词或者节点的含义，并且能够做数值计算；
- 作为 Walktrap 和 Infomap 算法的一部分，用于社群发现：如果随机游走总是返回同一组节点，表明这些节点可能在同一个社群；
- 其他机器学习模型的一部分，用于随机产生相关联的节点数据。
若有收获，就点个赞吧
0 人点赞
