-
viterbi 算法:利用动态规划寻找最短路径
动态规划原理
基本思想:问题的最优解如果可以由子问题的最优解推导得到,则可以先求解子问题的最优解,在构造原问题的最优解;若子问题有较多的重复出现,则可以自底向上从最终子问题向原问题逐步求解。
使用条件
可分为多个相关子问题,子问题的解被重复使用
Optimal substructure(优化子结构):
一个问题的优化解包含了子问题的优化解
缩小子问题集合,只需那些优化问题中包含的...
2020-01-23 02:09:32 |
Data-Struct
-
遗传算法详解
前言
说一说跨学库的东西。
生物学中的进化论可谓无人不知,无人不晓。
数学中的梯度下降和牛顿迭代,收敛的效果能否进一步优化呢?
这也使我想起来以前阅读的两本书《失控》和《超级智能》
什么是遗传算法?
遗传算法的科学定义
遗传算法(Genetic Algorithm, GA)是模拟达尔文生物进化论的自然选择和遗传学机理的生物进化过程的计算模型,是一种通过模拟自然进化过程搜索最优解...
2020-01-23 02:09:32 |
Data-Struct
-
图最短路径算法之弗洛伊德算法(Floyd)
Floyd算法
定义概览
Floyd-Warshall算法(Floyd-Warshall algorithm)是解决任意两点间的最短路径的一种算法,可以正确处理有向图或负权的最短路径问题,同时也被用于计算有向图的传递闭包。
Floyd-Warshall算法的时间复杂度为O(N^3),空间复杂度为O(N^2)。
算法描述
1) 算法思想原理:
Floyd算法是一个经典的动态规划算法...
2020-01-23 02:09:32 |
Data-Struct
-
图最短路径算法之迪杰斯特拉算法(Dijkstra)
问题定义
求解单元点的最短路径问题:给定带权有向图G和源点v,求v到G中其他顶点的最短路径
限制条件:图G中不存在负权值的边(这个可以通过弗洛伊德算法,后期将进行讲解)
核心思想
设G=(V,E)是一个带权有向图,把图中顶点集合V分成两组,第一组为已求出最短路径的顶点集合(用S表示,初始时S中只有一个源点,以后每求得一条最短路径 , 就将加入到集合S中,直到全部顶点都加入到S中,算法...
2020-01-23 02:09:32 |
Data-Struct
-
java 实现有向图(Direct Graph)
基本概念
图
图是数据结构中最为复杂的一种,我在上大学的时候,图的这一章会被老师划到考试范围之外,作为我们的课后兴趣部分。
但实际上,图在信息化社会中的应用非常广泛。图主要包括:
无向图,结点的简单连接
有向图,连接有方向性
加权图,连接带有权值
加权有向图,连接既有方向性,又带有权值
图是由一组顶...
2020-01-23 02:09:32 |
Data-Struct
-
DAG 有向无环图(Directed Acyclic Graph)
中文分词的算法
中文分词算法中,有一步就需要实现 DGA(有向无环图)。
所以来学习一下这种数据结构。
图
图是数据结构中最为复杂的一种,我在上大学的时候,图的这一章会被老师划到考试范围之外,作为我们的课后兴趣部分。
但实际上,图在信息化社会中的应用非常广泛。
图主要包括:
无向图,结点的简单连接
有向图,连接有方向性
加权图,连接带有权值
加权有向图,连接既有方向性,又...
2020-01-23 02:09:32 |
Data-Struct
-
DAG 拓扑序列 什么是拓扑排序 Topological Sorting
拓扑序列
拓扑序列是顶点活动网中将活动按发生的先后次序进行的一种排列。
拓扑排序,是对一个有向无环图(Directed Acyclic Graph简称DAG)G进行拓扑排序,是将G中所有顶点排成一个线性序列,使得图中任意一对顶点u和v,若边(u,v)∈E(G),则u在线性序列中出现在v之前。通常,这样的线性序列称为满足拓扑次序(Topological Order)的序列,简称拓扑序列。
...
2020-01-23 02:09:32 |
Data-Struct
-
利用有向无环图(DAG)进行任务调度
定时任务
定时任务是软件开发中经常遇到的问题。
简单的定时任务只需要在固定时间触发它的执行就可以了。
但是对于复杂的定时任务,可能是由多个任务组成一个任务组,它们之间存在依赖关系,一个任务执行的条件,必须是它的前置任务已经执行成功(或者没有前置任务),它才可以执行。
例如下面这幅图:
图中任务的依赖关系为:
任务1:依赖2,5
任务2:依赖3,4
任务3:无依赖
任务4...
2020-01-23 02:09:32 |
Data-Struct