网站栏目页面,公司做一个网站如何定位,企业微信怎么下载,品牌网站建设维护大约在公元9世纪上半叶#xff0c;来自中亚古国花剌子模的波斯数学家花剌子米(al-Khwarizmi)先后出版了两本对数学界有深远影响的书籍《印度数字算术》与《代数学》#xff0c;前者在12世纪被翻译为拉丁文传入欧洲#xff0c;十进制也因此传入欧洲#xff0c;最终所形成的… 大约在公元9世纪上半叶来自中亚古国花剌子模的波斯数学家花剌子米(al-Khwarizmi)先后出版了两本对数学界有深远影响的书籍《印度数字算术》与《代数学》前者在12世纪被翻译为拉丁文传入欧洲十进制也因此传入欧洲最终所形成的英文中的“算法”一词实际上是花剌子米的名字的拉丁文转译后传入法国大概在14世纪末传入英国直至19世纪固定后形成了今天的“算法”一词。这个例子告诉我们很多时候人类的知识就像是通过一张“以讹传讹”的网络得以扩散和传播的。 算法的由来 所有的图算法在本质上都是对更为基础的图上的计算、分析与查询操作的高度概括与集成。那么什么是基础的图上的计算、分析与查询操作呢可以简单概括为以下两类操作。
❑ 面向元数据的低维、离散的操作。典型的例如面向顶点或边的聚合、排序等操作。
❑ 面向高维数据的操作。典型的例如路径、子图、网络查询以及图算法等操作。从图计算的视角面向元数据的操作与之前所有SQL或NoSQL数据库没有本质区别因此并不是本书的重点。
❑ 面向高维数据的操作指的是从关联数据的角度查询数据之间的关联关系、关联路径和影响力范围例如我们常说的根因分析(Root-cause Analysis)、贡献度分析(ContributionAnalysis)、归因分析(Attribution Analysis)、影响力分析(Impact Analysis)、溯源分析(Backtracing)等。通过构建图数据模型然后进行图上的查询与分析通常会获得更高效、更灵活、更白盒化且更具可解释性的效果。
高维数据的查询有3个子类。
❑邻居查询如最典型的k邻查询。
❑路径查询如最短路径、环路、权重路径等。
❑展开、组网等其他较复杂查询如从某顶点展开、多顶点组网等。
当然所有的高维查询都可以通过拆解或分而治之的方式降维为低维查询因为它们都是从某个或某类元数据如顶点、边或其属性字段开始操作的而这些高维查询再进行组合、聚合、变形 就形成了我们所谓的图算法。例如度算法中的全图入度查询本质上就是计算所有顶点的入度。显然在一张大图上这个看似简单的算法的计算复杂度可能会非常高如何进行加速就变成了重要的议题我们会在第3章中进行详细分析。再比如全图k邻查询k-Hop Neighborsk跳邻居在连通度较高的图中即便是查询1个顶点的3跳、5跳邻居都可能会非常耗时假如1个顶点的1跳邻居有20个2跳邻居有400个3跳邻居有8000个而5跳邻居已经在3200000个的量级如果有10000000个顶点那么运行完这个算法的耗时和复杂度将是天文量级的。不经优化的图算法很多都是不具备实用性的而优化可以获得指数级的性能提升与耗时降低—可能原来需要运行1个月的算法如果在不增加硬件投入的前提下能提速1000倍降低至0.7h约40min内完成其意义是不言而喻的这也是为什么图算法的性能优化如此重要。
在剖析图算法的具体分类之前我们先了解一个设计良好的图算法应该具备的特征。通过梳理过去一个半世纪以来多位数学家和计算机学家对于算法特征的共性探讨我们总结了如下5点
1)无歧义即确定的操作逻辑。
2)清晰、明确的操作步骤。
3)具备良好的可行性如时间、空间、复杂度与效率。
4)定义了明确的输入、输出规则以及可验证正确性。
5)在有限步骤内可以完成。
关于图算法的分类业界并没有严格意义上的共识。有的侧重于学术研究的图计算框架甚至会把广度优先搜索(BFS)或深度优先搜索(DFS)作为算法单列尽管它们更适合作为一种图遍历模式存在。还有的如最短路径算法在20世纪计算机发展的前30年间20世纪40年代至70年代最短路径算法不断推陈出新对于计算机体系架构的发展有相当大的推动作用。图2-2示意了一种典型的在图上寻路所对应的算法分类情况。如图2-2所示DFS算法实现的是一种随机游走式的寻路且不关心路径是否最短。BFS算法实现的是无权重最短寻路而Dijkstra算法则实现的是有权重最短寻路。 我们在研究图算法的分类时一般都把图算法归类为组合数学算法的一部分因为组合数学涉及的领域相当广泛而图论是其中相当重要且有代表性的一部分。在组合数学中几乎所有的著名问题如旅行商问题、地图着色、任务分配、线性规划过河问题等都与图论或离散数学相关。按照在组合数学中的图论类算法可以简单地把算法作如下分类。 ❑图路由类算法最小生成树类算法、最短路径问题、最长路径问题、旅行商问题等。 ❑网络分析与网络流算法链接分析、网页排序算法、网络最大流问题等。 ❑图搜索类算法A*、B*、暴力搜索、回溯问题、双向搜索算法等。 ❑子图类算法强链接子图、团(Clique)、同态子图等。 ❑图可视化类算法力导向图、频谱布局、分层渲染、弧式图等。 ❑其他图算法染色类算法、拓扑排序算法、图匹配算法、最大势问题等。 我们还可以按照如下五大维度分别对图算法进行分类每个分类下又有一些典型子类算法。 1)按设计模式分类可分为以下6类 ❑遍历式列举式。在图算法以及图查询模式中遍历式是最为常见的。像广度优先算法与深度优先算法是最常用的图遍历模式很多现实世界的问题就是通过这些遍历模式解决的如象棋、围棋对弈问题。下面的回溯式算法也可以看作遍历式的一种特例。 ❑穷举式暴力计算。在海量数据集上穷举式计算并不一定是可行的但很多情况下带有过滤图上剪枝规则的穷举式计算又是必要的。例如在工商数据集中搜索一个自然人与一个发行人上市公司之间的全部最短关联路径是完全可行的即便两者之间存在成千上万条路径。❑分而治之。分而治之是算法设计中最经典的思路把大的问题缩小把大的数据集缩小通过递归、并发、分布式等方法来分块处理最后再汇总来解决全量的问题。二进制搜索、全图k邻算法等都是典型的采用分而治之的模式来解决问题的算法。 ❑回溯式、回溯式算法通常用于解决约束满足问题如各种迷宫或字谜类的益智游戏如经典的国际象棋八皇后问题、数独问题、背包问题等、地图着色问题、最大割问题等。因为有约束条件限定算法在进行某种随机遍历的过程中可能会通过回退即回溯或剪枝来优化遍历以找到正确的结果。 ❑随机化。通过随机操作的方式来求解的算法在学术界与工业界都很常见例如蒙特卡罗类算法在连通图中计算最小割问题的Karger算法就是通过随机删除图中的边并合并删前相连顶点的方式来实现以多项式时间复杂度参见下文中的按复杂度分类求解问题。
❑归约式。归约式算法通过把一个问题转换如映射成另一个问题进而寻求一种更简约的解决问题的方式。例如广度优先搜索求某个群顶点的k跳邻居中年龄最大者或最小或任意可度量维度或属性的过程中需要对结果集进行排序转换然后选取最大结果值返回这就是一种典型的先转换再求解的归约式算法。 2)按优化问题模式分类可分为以下3类 ❑线性规划(LP)。在最优化问题求解的过程中经常会遇到线性规划问题如商业管理中的降本增效问题、交通能源与通信领域的最大网络流问题等。 ❑动态规划(DP)。在经济学与航空工程学领域经常会遇到动态规划问题。简而言之动态规划问题一般通过把复杂的问题以递归的方式分解为更小的问题并找到最优解来说明该问题具备最优子结构(Optimal Substructure)。例如只要能证明贪心算法中的每一步都是最优的就可以用它来解决具有最优子结构的问题。贪心算法通常可以被看作动态规划类算法的一个特例最小生成树(MST)类算法就是典型的通过分解子结构来实现的贪心算法。 ❑启发式算法。启发式算法是在常规方式无法找到最优解的情况下太慢或效果太差通过在精度、准确性、完整性、最优性等维度之间进行协调取舍进而实现一种近似最优解的算法方案。3)按复杂度分类。可分为以下5类 ❑恒定时间。复杂度O(1)就是典型的恒定时间。比如无论数据集大小通过数组或向量数据结构访问任一顶点所需的时间恒定为O(1)。
连载文章未完待续
