备案网站注意事项,灵感网站,百度风云榜明星,合肥网络公司 网站建设目录 知识框架No.1 贪婪技术一、问题引入二、基本思想三、问题实例#xff1a;连续背包问题 No.2 最小生成树问题一、基本思想二、Prim算法1、主要思想和步骤2、算法效率 三、Kruskal算法1、主要思想和步骤 No.3 Dijkstra算法一、主要思想二、问题实例#xff1a; No.4 哈夫曼… 目录 知识框架No.1 贪婪技术一、问题引入二、基本思想三、问题实例连续背包问题 No.2 最小生成树问题一、基本思想二、Prim算法1、主要思想和步骤2、算法效率 三、Kruskal算法1、主要思想和步骤 No.3 Dijkstra算法一、主要思想二、问题实例 No.4 哈夫曼问题一、哈夫曼树 知识框架
No.1 贪婪技术
一、问题引入
题目找零问题
题意用指定面额为d1d2…dm的最少数量的硬币找出金额为n的零钱
(就是说从给定的面额的硬币 使用 最少数量的硬币 凑出 金额 n)
d15角d22角d31角 d45分d52分d61分
当n0.48的时候请确定一种最佳选择序列的逻辑策略
( 贪心的思想也就是 直接从最大的往下减)
二、基本思想
贪婪法通过一系列步骤来构造问题的解每一步对目前构造的部分解做一个扩展直到获得问题的完整解为止。
可行的必须满足问题的约束局部最优是当前步骤中所有可行选择中最佳的局部选择不可取消选择一旦做出在算法的后面步骤中就无法改变
在每一步中它要求“贪婪”地选择最佳操作并希望通过一系列局部的最优选择能够产生一个整个问题全局的最优解
贪婪技术是否有效
的确存在某类问题一系列局部最优选择对于它们的每一个实例都能够产生一个最优解或者我们关心的是近似解或者只能满足于近似解
三、问题实例连续背包问题
问题描述
已知有n种物品和一个可容纳W重量的背包每种物品I的重量为wi假定将物品I的某一部分xi放入背包就会得到pi*xi的效益(0≤xi≤1, pi0) 采用怎样的装包方法才会使装入背包物品的总效益为最大呢
下面的方案体现从不同角度进行的贪心在局部最优解的情况下有时候可能得到全局最优解的
方案1按物品价值降序装包贪心思想方案2按物品重量升序装包贪心思想方案3按物品价值与重量比值的降序装包贪心思想
No.2 最小生成树问题
一、基本思想
给定n个点把它们按照一种成本最低的方式连接起来使得每一对点之间都有一条路径。这个问题可以表示成最小生成树问题。
就是说有n个点然后让你连接 n-1 条边使得这些点与点之间互通到达使得连通成本最低
连通图的一棵生成树是包含图的所有顶点的连通无环子图也就是一棵树加权连通图的一棵最小生成树是图的权重最小的生成树最小生成树问题就是求给定的加权连通图的最小生成树问题
用穷举法来解决不现实
随着图的规模增长生成树的数量呈指数增加生成一个给定图的所有生成树并非易事
二、Prim算法
1、主要思想和步骤
主要思想Prim算法通过一系列不断扩张的子树来构造一棵最小生成树。
方法步骤
从图的顶点集合V中任选一个单顶点作为序列中的初始子树。每一次迭代时以一种贪婪的方式来扩张当前的生成树即简单地把不在树中的最近顶点添加到树中以一条权重最小的边和树中的顶点相连树的形状是无所谓的当图的所有顶点都包含在所构造的树中以后算法停止每次只对树扩展一个顶点
方法要求
对于每个不在当前树中的顶点必须知道它连接树中顶点的最短边的信息每一个顶点附加两个标记树中最近顶点的名称、相应边的权重这两个标记在代码中是遍历来找最近顶点的
Prim算法是否能产生一个最优解
答案是肯定的
2、算法效率
Prim算法的实际运用算法效率 还是主要靠你使用的数据结构决定的
表示图本身的数据结构表示集合V-VT的优先队列的数据结构
如果图是由邻接链表表示的并且优先队列是由最小堆实现的那么该算法的运行时间属于O(|E|log|V|)
因为该算法进行了|V|-1次删除最小元素的操作并且进行了|E|次验证每一种操作都是O(log|V|)
如果使用更先进的可能算法效率会更好
三、Kruskal算法
1、主要思想和步骤
Kruskal算法把一个加权连通图GV,E的最小生成树看作是一个具有|V|-1条边的无环子图并且边的权重和是最小的。该算法通过对子图的一系列扩展来构造一棵最小生成树这些子图总是无环的但在算法的中间阶段并不一定是连通的。贪心到极致。
方法步骤
首先按照权重的非递减顺序对图中的边进行排序然后从一个空子图开始扫描有序列表试图把列表中的下一条边加到当前的子图中。必须保证该添加不会导致一个回路必须要不成环才能加入
算法详解
对包含给定图的所有顶点和某些边的一系列森林所做的连续动作 初始森林是由|V|棵只有根结点的树构成的最终的森林是由一棵树构成的它就是该图的最小生成树每次迭代的时候从图的边的有序列表中取出下一条边(u,v)并找到包含顶点u和v的树如果他们不是同一棵树通过加入边(u,v)把这两棵树连成一棵更大的树
No.3 Dijkstra算法
一、主要思想
单起点最短路径问题对于加权连通图的一个称为起点的给定顶点求出它到所有其他顶点之间的一系列最短路径。
也就是说给了一个起源点就能够通过这个算法求得起源点到其它各个顶点的最短路径是属于一步到位的
方法步骤
Dijkstra算法按照从给定起点到图中顶点的距离顺序求出最短的路径。
首先它求出从起点到最接近起点的顶点之间的最短路径然后求出第二近的依此类推
二、问题实例
主要针对的是边上权值非负情形的单源最短路径问题。
问题的提法
给定一个带权有向图D与源点 v求从 v 到D中其他顶点的最短路径。限定各边上的权值大于或等于0。
问题的解决步骤每次看的都是到源点v的距离比较
为求得这些最短路径, Dijkstra提出按路径长度的递增次序, 逐步产生最短路径的算法。首先求出长度最短的一条最短路径再参照它求出长度次短的一条最短路径依次类推直到从顶点v到其它各顶点的最短路径全部求出为止。
引入辅助数组dist。它的每一个分量dist[i]表示当前找到的从源点 v0到终点 vi 的最短路径的长度。初始状态 若从源点v0到顶点 vi 有边, 则dist[i]为该边上的权值若从源点v0到顶点 vi 无边, 则dist[i]为∞。 假设 S 是已求得的最短路径的终点的集合则可证明下一条最短路径必然是从v0 出发中间只经过 S 中的顶点便可到达的那些顶点vx (vx∈V-S )的路径中的一条。每次求得一条最短路径后, 其终点vk 加入集合S然后对所有的vi∈V-S修改其 dist[i]值。
代码
void dij(int index){//初始化visdis以及main上面的变量memset(vis,0,sizeof(vis));memset(dis,inf,sizeof(dis));for(int i0;in;i)dis[i]mp[index][i];dis[index]0;way[index]index;//初始化的人员初始化的道路选择num[index]people[index];cnt[index]1;//找n个最短点一个for找到一个点vis【点】1//显然第一个点是自己本身dis【index】0//第一部分找最短的for(int i0;in;i){int u-1,minninf;for(int j0;jn;j){if(vis[j]0dis[j]minn){uj;minndis[j];}}if(u-1)break;vis[u]1;//第二部分更新距离for(int j0;jn;j){if(vis[j]0dis[j]dis[u]mp[u][j]){dis[j]dis[u]mp[u][j];num[j]num[u]people[j];way[j]u;cnt[j]cnt[u];//c出现下面这个条件啊就会再出来一个最优判断。}else if(vis[j]0dis[j]dis[u]mp[u][j]){cnt[j]cnt[u]cnt[j];if(num[j]num[u]people[j]){way[j]u;num[j]num[u]people[j];}}}}
}Dijkstra算法的步骤详细解释 在第i次迭代开始以前该算法已经确定了i-1条连接起点和离起点最近顶点之间的最短路径。他们构成了一棵子树Ti 和Ti的顶点相邻的顶点集合成为“边缘顶点”以它们为候选对象选出下一个最接近起点的顶点。对于每一个边缘顶点u该算法求出它到最近的树中顶点v的距离给每个顶点附加两个标记 数字标记d指出目前为止该算法求出的从起点到该顶点间最短路径的长度另一个指出在这条路径上倒数第二个顶点的名字。 在确定了加入树中的顶点u*以后还需要做两个操作 把u*从边缘集合中移到顶点集合对于余下的每个边缘顶点u如果通过权重为w(u*,u)的边和u相连当duw(u*,u)du时把u的标记分别更新为u和duw(u*,u) 虽然从算法的标记和结构Dijkstra算法和Prim算法的用法十分相似且他们都会从余下顶点的优先队列中选择下一个顶点但他们解决的是不同的问题。
No.4 哈夫曼问题
一、哈夫曼树
