一些算法的复习(最短路径、最小生成树、dp)
暑假过去两个月,再一次对一些算法的复习:
最短路径:
Floyd- Warshall算法:
这个算法就是让我们去寻找从点i到点j的距离,有以下两种情况:
(1). 两点直接到达的距离最短。
(2). 两点之间通过1个或者1个以上节点连接到达的距离最短。
其中主要代码只有五行,通过不同的点去中转看看中转之后的点到达的距离与直接到达是否小,如果小就更新距离。
for(k=1;k<=n;k++)
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
if(e[i][j]>e[i][k]+e[k][j])
e[i][j]=e[i][k]+e[k][j]
Dijkstra算法:
这个算法就是找到一个顶点,然后看看这个顶点到其他点的最小距离。如果到下一个顶点的距离比当前顶点大,九成新更新距离。
具体步骤:
1、将所有顶点分为两部分:已知最短距离路程的顶点集合P和未知最短路径的顶点集合Q。最开始,已知最短路径的顶点集合P只有一个顶点。我们这里用一个book记录那些点已经在集合P中。
2、设置源点s到自己的距离为0,若有源点能直接到达顶点,则距离为e[s][i],若不能到达此时距离为无穷大,这个我们定义99999999为无穷大。
3、在集合Q的所有顶点中选择离源点s最近的顶点u加入集合P中,并考察以u为起点的边,对每一条边进行松弛。
4、重复第3步,直到集合Q为空。
for(i=1;i<=n-1;i++)
{
min=inf;
//找到离1号顶点最近的点
for(j=1;j<=n;j++)
{
if(book[j]==0&&dis[j]<min)
{
min=dis[j];
u=j;
}
}
book[u]=1;
for(v=1;v<=n;v++)
{
if(e[u][v]<inf)
{
if(dis[v]>dis[u]+e[u][v])
dis[v]=dis[u]+e[u][v];
}
}
}
最小生成树:
kruskal算法:
先构造一个只含 n 个顶点、而边集为空的子图,把子图中各个顶点看成各棵树上的根结点,之后,从网的边集 E 中选取一条权值最小的边,若该条边的两个顶点分属不同的树,则将其加入子图,即把两棵树合成一棵树,反之,若该条边的两个顶点已落在同一棵树上,则不可取,而应该取下一条权值最小的边再试之。依次类推,直到森林中只有一棵树,也即子图中含有 n-1 条边为止。
这个算法实现就是先利用快排把从小到大排序,贪心算法取最优边,然后利用并查集判断两边是否已经在一个集合中。
核心代码:
for(i=1;i<=m;i++)//开始从小到大枚举每一条边
{
if(merge(e[i].u,e[i].v))//利用并查集判断两个边是否已经在一个集合中
{
count++;
sum=sum+e[i].w;
}
if(count==n-1)//到n-1条边后退出循环
break;
}
prim算法:
算法流程:
1、从任意一个顶点构造生成树,然后用book[]数组记录标记的点。
2、用dis[]数组记录生成树到各个顶点的距离
3、从dis[]数组中选出离生成树最近的顶点加入生成树中,如果dis[k]>e[j][k],则重新更新dis[k]。
4、重复第三步,直到count==n.
核心代码:
book[1]=1;//将1号顶点加入生成树
count++;
while(count<n)
{
min=inf;
for(i=1;i<=n;i++)
{
if(book[i]==0&&dis[i]<min)
{
min=dis[i];
j=i;
}
}
book[j]=1;
count++;
sum+=dis[j];
for(k=1;k<=n;k++)//扫描当前j所在的顶点,再以j为中间点,更新生成树到每一个非树顶点的位置
{
if(book[k]==0&&dis[k]>e[j][k])
dis[k]=e[j][k];
}
}
dp:
对于用动态规划的问题,其大大的减少了计算量,丰富了计算,它包括:背包问题(详解参照https://blog.csdn.net/qq_44859533/article/details/98972091)、动态三角形、还有最长、最大连续子序列。
最长连续子序列例题:
A numeric sequence of ai is ordered if a1 < a2 < … < aN.Let the subsequence of the given numeric sequence ( a1, a2, …, aN) be any sequence ( ai1, ai2, …, aiK), where 1 <= i1 < i2 < … < iK <= N. For example, sequence (1, 7, 3, 5, 9, 4, 8) has ordered subsequences, e. g., (1, 7), (3, 4, 8) and many others. All longest ordered subsequences are of length 4, e. g., (1, 3, 5, 8).
Your program, when given the numeric sequence, must find the length of its longest ordered subsequence.
Input
The first line of input file contains the length of sequence N. The second line contains the elements of sequence - N integers in the range from 0 to 10000 each, separated by spaces. 1 <= N <= 1000
Output
Output file must contain a single integer - the length of the longest ordered subsequence of the given sequence.
Sample Input
7
1 7 3 5 9 4 8
Sample Output
4
解题思路:给定一个序列找出连续的递增子序列;
程序代码:
#include<stdio.h>
int main()
{
int i,j,k,n,t;
int a[2000];
int len[2000];
int max;
scanf("%d",&n);
for(i=1;i<=n;i++)
scanf("%d",&a[i]);
len[1]=1;
for(i=2;i<=n;i++)
{
t=0;
for(k=1;k<i;k++)
{
if(a[k]<a[i]&&t<len[k])
t=len[k];
}
len[i]=t+1;
}
max=-1;
for(i=1;i<=n;i++)
{
if(max<len[i])
max=len[i];
}
printf("%d\n",max);
return 0;
}
相关文章
- 训练-我的基础算法刷题之路(四)
- 复旦大学961-数据结构-第五章-图(三)最小生成树基本概念,Prim算法,Kruskal算法
- 复旦大学961-数据结构-第三章-查找(5)优先队列与堆,堆的定义,堆的生成,调整算法;范围查询
- RBF神经网络学习算法及与多层感知器的比较
- 图算法(七):带一般过滤条件最短路径(Filtered Shortest Path)【适用场景:用于路径设计、网络规划等,通过对点边条件的过滤,控制最短路径的生成】【寻找两点间满足过滤条件的最短路径】
- 【风光场景生成】基于改进ISODATA的负荷曲线聚类算法(Matlab代码实现)
- 关于最大流的EdmondsKarp算法详解
- Prim算法求最小生成树
- 排列组合生成算法
- java算法实现树型目录反向生成(在指定的盘符或位置生成相应的文件结构)
- 设置TOMCAT SESSIONID 字符长度和生成算法
- 机器学习算法-kmeans 聚类算法一
- 22二叉树非递归遍历算法
- 2.特定领域知识图谱融合方案:文本匹配算法(Simnet、Simcse、Diffcse)【二】
- B.图算法:图游走模型/图学习之图游走类metapath2vec模型[系列五]
- 机器学习笔记之python实现朴素贝叶斯算法样例
- opencv之haar特征+AdaBoos分类器算法流程(三)
- SnowFlake --- 分布式id生成算法
- 生成主键ID,唯一键id,分布式ID生成器雪花算法代码实现
- 【人工智能】深度学习算法的底层理论与具体应用场景 || 神经网络、卷积神经网络、循环神经网络、图神经网络、长短期记忆神经网络、自编码器、生成对抗网络
- 一款基于SVM算法的分布式法律助手
- 前端 算法的时间复杂度和空间复杂度
- 一步一步写算法(之字符串查找 中篇)
- 一步一步写算法(之洗牌算法)
- Java实现Prim最小生成树算法
- 【Java】Java复习笔记-三大排序算法,堆栈队列,生成无重复的随机数列
- 数据结构和算法 (三)数据结构基础之树、二叉树
- paxos算法
- AcWing 859. Kruskal算法求最小生成树
- 感知哈希算法——找出相似的图片XsdGen:通过自定义Attribute与反射自动生成XSD
- 最小生成树------Prim算法
- 【算法010】反转链表(206)