蛮力贪婪法数据结构与算法pptx

DataStructuresandAlgorithms主讲教师:黄襄念西华大学数学与计算机学院图像处理与模式识别实验室课程QQ群：101600501数据结构与算法本章授课内容蛮力法：算法设计思想蛮力法：选择排序蛮力法：穷举查找蛮力法：0-1背包问题贪婪法：算法设计思想贪婪法：Prim算法贪婪法：Kruskal算法贪婪法：Dijkstra算法贪婪法：连续背包问题本章授课学时：3学时07:122／28问题求解框架实际问题数学模型求解算法数据组织程序实现程序测试数学描述算法设计程序设计数据结构设计07:123／28蛮力法〔BruteForceAlgorithm〕蛮力法：直接基于问题本身描述的算法设计方法解决问题没有或不用技巧〔简单、直接〕简例a和非负整数n，计算an的蛮力算法：

典型算法：各种穷举法优缺点优点：算法设计简单，易于设计缺点：算法的时间效率一般不高蛮力法：算法设计思想07:124／28蛮力法应用——一种重要的算法设计方法解决各种问题的一般方法常用于一些很根本又重要的算法——计算n个数的和——求数据集的最大元素，……可作为尺度，衡量同样问题的其他算法的效率对于规模不大的问题〔蛮力法的速度可以接受时〕蛮力法是一种很好的解决方案！设计高效算法的代价很可能是不值得的：①算法可读性变差，算法实现的复杂性增加软件工程：不利于软件的开发、测试、维护②时间效率得不到显著的表达蛮力法：应用07:125／28排序问题中的蛮力法冒泡排序、选择排序查找问题中的蛮力法顺序查找、字符串匹配〔朴素的〕组合问题中的蛮力法穷举查找：子集和问题、0-1背包问题图问题中的蛮力法穷举查找：哈密顿回路问题穷举查找：货郎担〔旅行商，TSP，邮递员〕问题计算几何问题中的蛮力法穷举查找：最近对问题、凸包问题蛮力法：应用例07:126／28排序算法设计举例：对线性表(89,45,68,90,29,34,17)排为升序思考：什么是排序问题？最直接的排序方法？蛮力法：按从小到大顺序挑出各个元素排列好蛮力法：选择排序07:127／28组合问题的查找前述查找：给定集合中查找满足条件的一个元素(key)组合问题的查找：给定集合中查找满足条件的子集例：子集和问题在给定的整数集合中，查找满足如下条件的子集：元素和=某个给定的整数〔约束条件〕应用例：食堂就餐〔50元钱能买多少食品，不找零〕穷举查找设计生成算法，生成全部子集〔个数：〕对所有子集一一判定是否满足约束条件：满足的子集：解〔可行解〕不满足的子集：不可行解蛮力法：穷举查找2n幂集07:128／28背包问题〔KnapsackProblem〕：n个物品，重量(w1,...,wn),价值(v1,...,vn),一个承重量为W的背包求解：能够放入背包(可行)、最有价值的子集(最优)连续背包物品可以按任意比例切分，比例系数(0.0~1.0)离散背包〔0-1背包〕物品不能切分。0：不放入，1：放入0-1背包的蛮力法(穷举查找)生成n个物品集合的全部子集〔所有组合〕计算每个子集的重量(≤W)，计算可行解的价值最优解：可行解中价值最大者蛮力法：0-1背包问题07:129／28贪婪法／贪心法〔GreedyAlgorithm〕常用于解决最优化问题贪婪法：算法设计思想全局最优解由一系列的局部最优解构成下山：一步一步走迭代法，非直接法最速下山法从始点出发，根据当前局部最优决策，使目标函数f(X)→min最快f(x1,x2)变化最快方向？——梯度方向(+,-)正梯度：函数值增大负梯度：函数值减小07:1210／28每一步的决策是可行解〔满足约束条件〕局部最优〔贪婪〕不可逆转〔后续步骤不能改变它〕优缺点优点：算法较简单，时空效率较高缺点：存在视界局限〔局部最优不一定是全局最优〕，对某些优化问题，不能获得最优解！贪婪法：贪婪策略与特点负梯度只是局部最好方向，相邻两次迭代的方向垂直，整个搜索轨迹呈现锯齿形！假设函数性态很坏，震荡现象严重，甚至计算不收敛。07:1211／28生成树(SpanningTree,ST)包含连通图全部顶点的一个连通无环子图(边数=n-1)最小生成树(MinimumSpanningTree,MST)带权连通图所有生成树中，权重之和最小的那一棵贪婪法：Prim算法1324132413241324ADCB1235ADCB123ADCB135ADCB125

w(T1)=6

w(T2)=9

w(T3)=807:1212／28普利姆(Prim)算法策略：初始子树开始，逐步扩展子树，直到生成MST算法：初始子树任选一个顶点v0子树扩展〔贪婪〕参加顶点：不在树中、到树的距离最近的一个顶点顶点到树的距离：到树中所有顶点的最短距离算法停止全部顶点都已参加树中〔形成一棵树〕说明：MST不唯一，但权之重和相同算法过程图：下页贪婪法：Prim最小生成树算法07:1213／28贪婪法：Prim算法过程图为何参加顶点时，只考虑边缘点？每个边缘点到子树的最短距离是？参加子树中的顶点是哪一个？子树边缘点边缘点边缘点边缘点？12457324507:1214／28MST应用例右图：6个社区A~F权值：已测绘的距离任务：修建道路连通6个社区要求：造价本钱最低问题分析：连通性与本钱最低要求①连通无环图(树)；②总里程最短(MST)问题求解：选用Prim算法顶点集分2个子集：树中顶点集、候选顶点集顶点增加2个属性：树中最近邻接点名称、边长(权)例如：子树顶点集{A,B},F(B,4),D(-,∞)贪婪法：Prim算法例BCFAED带权图G07:1215／28算法过程图例Prim算法例

树中顶点集候选顶点集BCFAED初始树BCFAED07:1216／28Prim算法例

树中顶点集候选顶点集BCFAEDBCFAEDBCFAEDMST不唯一时间效率O(n2),与边数无关适合于稠密图07:1217／28Kruskal算法(克鲁斯卡尔,避环法)策略：初始森林开始，逐步合并森林，直到生成MSTKruskal算法//网G=<V,E,W>{G的边集E排序：权值小→大初始森林：MST的边集ET=Φwhile(|ET|<=n-1)//MST有多少边？{从E取下一条边{u,v};E=E-{u,v};if({u,v}与ET中边不构成回路)ET=ET∪{u,v};//{u,v}参加MST}}贪婪法：Kruskal最小生成树算法如何判断参加边是否构成回路？BCFAED判断u,v是否属于同一棵树(极小连通子图)O(eloge),e边数07:1218／28贪婪法：Kruskal算法过程图BCFAED

树中边集ET

有序候选边集EBC,EF,AB,BF,CF1

2344AF,DF,AE,CD,DE55668ΦBCFAEDBC,

EF,AB,BF,CF

1

2344AF,DF,AE,CD,DE5566

8BCBCFAEDBC,EFBC,

EF,

AB,BF,CF

1

2

344AF,DF,AE,CD,DE5566

807:1219／28贪婪法：Kruskal算法过程图BCFAED

树中边集ET

有序候选边集EBC,EF,AB,

BF,CF

123

44AF,DF,AE,CD,DE55668BC,EF,ABBCFAEDBC,EF,AB,BF,CF

12344AF,DF,AE,CD,DE5566

8BCFAEDBC,EF,AB,BF,CF

12344AF,DF,AE,CD,DE5566

8BC,EF,AB,BFBC,EF,AB,BF,DF不唯一07:1220／28单源最短路径问题给定加权连通图，求一个源点到其余顶点的最短路径与MST区别——整棵树权值和最小〔不要求任意两顶点最近〕与完全最短路径问题区别〔Floyd算法〕——每个顶点到其余顶点的最短路径与货郎担〔旅行商〕问题区别——经过带权连通图全部顶点仅一次的最短回路贪婪法：Dijkstra算法ADCB1234ADCB123ADCB124带权图MST单源最短路径树07:1221／28解单源最短路径问题——Dijkstra算法贪婪法：Dijkstra算法子树边缘点边缘点非边缘点124584225Dijkstra与Prim很类似Dijkstra：到起点v0

距离最近Prim：到子树距离最近07:1222／28背包问题的数学模型〔优化模型〕贪婪法：连续背包问题目标函数约束条件n

个物品：重量:

(w1,...,wn)

价值:(v1,...,vn)背包承重量:W物品k

放入背包的比例系数:xk0-1背包连续背包三种贪婪策略价值贪婪重量贪婪价值／重量贪婪能找到最优解吗？07:1223／28贪婪法：连续背包问题解法//解向量(空背包)//背包的当前承重量//背包中物品总价值//排序(降序)：价值/重量//n个物品循环//未超重//整个装入背包：xi=1//背包当前承重量减小//物品价值记入总价值//物品超重：放入一局部07:1224／28设计蛮力算法：判断一个邻接矩阵表示的连通图是否具有欧拉回路。该算法的效率类型如何？完备子图问题：给定一个图G和正整数k，确定该图是否包含一个大小为k的完备子图即具有k个顶点的完全子图。请为该问题设计一个穷举查找算法。贪婪法求连续背包问题最优解：n=7,W=15,

(w1,w2,w3,w4,w5,w6,w7)=(2,3,5,7,1,4,1)(v1,v2,v3,v4,v5,v6,v7)=(10,5,15,7,6,18,3)应用Prim算法之前，是否需要检查图的连通性？该算法本身能完成这种检查？如何应用Prim算法求不带权的连通图的生成树？