Estom的博客

Bellman-Ford 单源最短路径算法 Bellman-Ford 算法是一种用于计算带权有向图中单源最短路径（SSSP：Single-SourceShortest Path）的算法。该算法由 Richard Bellman 和 Lester Ford 分别发表于 1958年和 1956 年，而实际上 Edward F. Moore 也在 1957年发布了相同的算法，因此，此算法也常被称为 Bellman-Ford-Moore 算法。 Bellman-Ford 算法和 Dijkstra算法同为解决单源最短路径的算法。对于带权有向图G = (V, E)，Dijkstra 算法要求图 G 中边的权值均为非负，而 Bellman-Ford算法能适应一般的情况（即存在负权边的情况）。一个实现的很好的Dijkstra 算法比 Bellman-Ford 算法的运行时间要低。 Bellman-Ford 算法采用动态规划（Dynamic Programming）进行设计，实现的时间复杂度为O(V*E)，其中 V 为顶点数量，E 为边的数量。Dijkstra 算法采用贪心算法（Gree...

Floyd-Warshall 全源最短路径算法 Floyd-Warshall 算法采用动态规划方案来解决在一个有向图 G = (V, E)上每对顶点间的最短路径问题，即全源最短路径问题（All-Pairs Shortest PathsProblem），其中图 G 允许存在权值为负的边，但不存在权值为负的回路。Floyd-Warshall算法的运行时间为 Θ(V3)。 Floyd-Warshall 算法由 Robert Floyd 于 1962 年提出，但其实质上与 Bernad Roy 于1959 年和 Stephen Warshall 于 1962 年提出的算法相同。 解决单源最短路径问题的方案有 Dijkstra算法和Bellman-Ford算法，对于全源最短路径问题可以认为是单源最短路径问题（SingleSource Shortest PathsProblem）的推广，即分别以每个顶点作为源顶点并求其至其它顶点的最短距离。更通用的全源最短路径算法包括： 针对稠密图的 Floyd-Warshall 算法：时间复杂度为 O(V3)； 针对稀疏图的 Johnson ...

Kruskal 最小生成树算法 对于一个给定的连通的无向图 G = (V, E)，希望找到一个无回路的子集 T，T 是 E的子集，它连接了所有的顶点，且其权值之和为最小。 因为 T 无回路且连接所有的顶点，所以它必然是一棵树，称为生成树（SpanningTree），因为它生成了图 G。显然，由于树 T 连接了所有的顶点，所以树 T 有 V - 1条边。一张图 G 可以有很多棵生成树，而把确定权值最小的树 T的问题称为最小生成树问题（Minimum Spanning Tree）。术语 “最小生成树”实际上是 “最小权值生成树” 的缩写。 Kruskal 算法提供一种在 O(ElogV) 运行时间确定最小生成树的方案。Kruskal算法基于贪心算法（GreedyAlgorithm）的思想进行设计，其选择的贪心策略就是，每次都选择权重最小的但未形成环路的边加入到生成树中。其算法结构如下： 将所有的边按照权重非递减排序； 选择最小权重的边，判断是否其在当前的生成树中形成了一个环路。如果环路没有形成，则将该边加入树中，否则放弃。 重复步骤 2，直到有 V - 1 条边在生...

Dijkstra 单源最短路径算法 Dijkstra 算法是一种用于计算带权有向图中单源最短路径（SSSP：Single-SourceShortest Path）的算法，由计算机科学家 Edsger Dijkstra 于 1956 年构思并于 1959年发表。其解决的问题是：给定图 G 和源顶点 v，找到从 v 至图中所有顶点的最短路径。 Dijkstra 算法采用贪心算法（GreedyAlgorithm）范式进行设计。在最短路径问题中，对于带权有向图 G = (V, E)，Dijkstra算法的初始实现版本未使用最小优先队列实现，其时间复杂度为 O(V2)，基于 Fibonacciheap的最小优先队列实现版本，其时间复杂度为 O(E + VlogV)。 Bellman-Ford算法和Dijkstra算法同为解决单源最短路径的算法。对于带权有向图G = (V, E)，Dijkstra 算法要求图 G 中边的权值均为非负，而 Bellman-Ford算法能适应一般的情况（即存在负权边的情况）。一个实现的很好的 Dijkstra 算法比Bellman-For...

时间复杂度 时间复杂度并不是表示一个程序解决问题需要花多少时间，而是当问题规模扩大后，程序需要的时间长度增长得有多快。也就是说，对于高速处理数据的计算机来说，处理某一个特定数据的效率不能衡量一个程序的好坏，而应该看当这个数据的规模变大到数百倍后，程序运行时间是否还是一样，或者也跟着慢了数百倍，或者变慢了数万倍。不管数据有多大，程序处理花的时间始终是那么多的，我们就说这个程序很好，具有O(1)的时间复杂度，也称常数级复杂度；数据规模变得有多大，花的时间也跟着变得有多长，这个程序的时间复杂度就是O(n)，比如找n个数中的最大值；而像冒泡排序、插入排序等，数据扩大2倍，时间变慢4倍的，属于O(n^2)的复杂度。还有一些穷举类的算法，所需时间长度成几何阶数上涨，这就是O(a^n)的指数级复杂度，甚至O(n!)的阶乘级复杂度。不会存在O(2*n^2)的复杂度，因为前面的那个“2”是系数，根本不会影响到整个程序的时间增长。同样地，O(n^3+n^2)的复杂度也就是O(n^3)的复杂度。因此，我们会说，一个O(0.01*n^3)的程序的效率比O(100*n^2)的效率低，尽管在n很小的时候，前...

Prim 最小生成树算法 Prim 算法是一种解决**最小生成树问题（Minimum Spanning Tree）**的算法。和Kruskal算法类似，Prim算法的设计也是基于贪心算法（Greedy algorithm）。 Prim算法的思想很简单，一棵生成树必须连接所有的顶点，而要保持最小权重则每次选择邻接的边时要选择较小权重的边。Prim算法看起来非常类似于单源最短路径 Dijkstra算法，从源点出发，寻找当前的最短路径，每次比较当前可达邻接顶点中最小的一个边加入到生成树中。 例如，下面这张连通的无向图 G，包含 9 个顶点和 14条边，所以期待的最小生成树应包含 (9 - 1) = 8 条边。 创建 mstSet 包含到所有顶点的距离，初始为 INF，源点 0 的距离为 0，{0, INF, INF,INF, INF, INF, INF, INF, INF}。 选择当前最短距离的顶点，即还是顶点 0，将 0 加入 MST，此时邻接顶点为 1 和 7。 选择当前最小距离的顶点 1，将 1 加入 MST，此时邻接顶点为 2。 选择 2 和 7 中最小距离的顶...

问题分析 有若干个城市，任何两个城市之间的距离都是确定的，现要求一旅行商从某城市出发必须经过每一个城市且只在一个城市逗留一次，最后回到出发的城市，问如何事先确定一条最短的线路已保证其旅行的费用最少？ 贪心算法 动态规划算法 分支限界算法 遗传算法

遗传算法定义 遗传算法（Genetic Algorithm,GA）起源于对生物系统所进行的计算机模拟研究。它是模仿自然界生物进化机制发展起来的随机全局搜索和优化方法，借鉴了达尔文的进化论和孟德尔的遗传学说。其本质是一种高效、并行、全局搜索的方法，能在搜索过程中自动获取和积累有关搜索空间的知识，并自适应地控制搜索过程以求得最佳解。 袋鼠跳问题（纯粹是觉得有意思） “袋鼠跳”问题 既然我们把函数曲线理解成一个一个山峰和山谷组成的山脉。那么我们可以设想所得到的每一个解就是一只袋鼠，我们希望它们不断的向着更高处跳去，直到跳到最高的山峰（尽管袋鼠本身不见得愿意那么做）。所以求最大值的过程就转化成一个“袋鼠跳”的过程。 作为对比下面简单介绍“袋鼠跳”的几种方式。 1. 爬山法（最速上升爬山法）： 从搜索空间中随机产生邻近的点，从中选择对应解最优的个体，替换原来的个体，不断重复上述过程。因为爬山法只对“邻近”的点作比较，所以目光比较“短浅”，常常只能收敛到离开初始位置比较近的局部最优解上面。对于存在很多局部最优点的问题，通过一个简单的迭代找出全局最优解的机会非常渺茫。（在爬山法中，袋鼠最有希望...

Creational Patterns（创建型模式）1 概述目标创建型模式（Creational Patterns）抽象了对象实例化过程。 用于 创建、组合和表示 一个系统的所有对象。 一个类创建型模式使用继承改变被实例化的类。 一个对象创建型模式将实例化委托给另一个对象。 随着系统演化得越来越依赖于对象复合而不是类的继承，创建型模式变得更为重要。 在这些模式中，有两个不断出现的主旋律： 它们都将关于该系统使用那些具体的类的信息封装起来。 它们隐藏了这些类的实例是如何被创建和放在一起的。 因此，创建型模式在什么被创建，谁创建它，它是怎样被创建的，以及何时创建这些方面给予你很大的灵活性。 Consequently, the creational patterns give you a lot of flexibility in what gets created, who creates it, how it gets created, and when. 2 具体方法Factory Method （工厂方法） Define an interface for creat...

Structural Patterns（结构型模式）1 概述目标结构型模式涉及到如何组合类和对象以获得更大的结构。 结构型类模式采用继承机制来组合接口实现。 结构型对象模式不是对接口和实现进行组合，而是描述了如何对一些对象进行组合，从而实现新功能的一些方法。 因为可以在运行时改变对象组合关系，所以对象组合方式具有更大的灵活性，而这种机制用静态组合是不可能实现的。 Adapter（适配器） 将一个类的接口转换成客户希望的另外一个接口。 Adapter 模式使得原本由于接口不兼容而不能一起工作的那些类可以一起工作。 Bridge（桥接） 将抽象部分与它的实现部分分离，使它们都可以独立地变化。 Composite（组合） 将对象组合成树形结构以表示 “部分-整体” 的层次结构。 Composite 使得用户对于单个对象和组合对象的使用具有一致性。 Decorator（装饰） 动态地给一个对象添加一些额外的职责。 就增加功能来说，Decorator 模式相比生成子类更为灵活。 Facade（外观） 为子系统中的一组接口提供一个一致的界面。 Facade 模式定义了一个高...