【算法复习二】传统基本算法(贪心、动态规划、回溯和分支限界)

2024-04-05 01:58

本文主要是介绍【算法复习二】传统基本算法(贪心、动态规划、回溯和分支限界),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

 一,贪心算法的设计思想

        • 从问题的某一个初始解出发逐步逼近给定的目标,每一步都作一个不可回溯的决策,尽可能地求得最好的解。当达到某算法中的某一步不需要再继续前进时,算法停止。


二,贪心算法的基本性质

       1)贪心选择性质

             所谓贪心选择性质是指所求问题的整体最优解可以通过一系列局部最优的选择,即贪心选择来达到。这是贪心算法可行的第一个基本要素,也是贪心法与动态规划法的主要区别。

       2) 最优子结构性质

           该问题解的整体最优性依赖于其局部子问题解的最优性。这种性质是可以采用贪心算法解决问题的关键特征。例如,活动安排问题,在选择了一项活动后,它必须是最优的,否则不能得到全局的最优。


三,贪心算法的适用性

        • 贪心算法对问题只需考虑当前局部信息就要做出决策,也就是说使用贪心算法的前提是局部最优策略能导致产生全局最优解

        该算法的适用范围较小若应用不当不能保证求得问题的最佳解。更准确的方法是通过数学方法证明问题对贪心策略的选用性。


四,绝对贪心问题

        例一:Dijkstra单源最短路径问题(有向图)  

      (Dijkstra)算法思想
  按路径长度递增次序产生最短路径算法:
  把V分成两组:
  (1)S:已求出最短路径的顶点的集合
  (2)V-S=T:尚未确定最短路径的顶点集合
   将T中顶点按最短路径递增的次序加入到S中
   保证:1)从源点V0到S中各顶点的最短路径长度都不大于  从V0到T中任何顶点的最短路径长度
             2)每个顶点对应一个距离值
  S中顶点:从V0到此顶点的最短路径长度
     T中顶点:从V0到此顶点的只包括S中顶点作中间  顶点的最短路径长度
  依据:可以证明V0到T中顶点Vk的最短路径,或是从V0到Vk的  直接路径的权值;或是从V0经S中顶点到Vk的路径权值之和
 
  求最短路径步骤
  算法步骤如下:
  1. 初使时令 S={V0},T={其余顶点},T中顶点对应的距离值
  若存在<V0,Vi>,d(V0,Vi)为<V0,Vi>弧上的权值
  若不存在<V0,Vi>,d(V0,Vi)为∝
  2. 从T中选取一个其距离值为最小的顶点W且不在S中,加入S
  3. 对T中顶点的距离值进行修改:若加进W作中间顶点,从V0到Vi的  距离值比不加W的路径要短,则修改此距离值
  重复上述步骤2、3,直到S中包含所有顶点,即S=T为止


        辅助数组:dist[ ] 存放V0到T中点距离  

                          path[ ]存放已经加入S中点到V0最短路径


        例二:Kruskal最小生成树问题(每次选权值最小边,直到生成一个最小生成树)

                  算法的运行时间为 O(nlog n)

         源码:

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define MAX_NAME 5
#define MAX_VERTEX_NUM 20 
typedef char Vertex[MAX_NAME];/*顶点名字串*/
typedef int AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];/*邻接距阵*/
struct MGraph/*定义图*/
{Vertex vexs[MAX_VERTEX_NUM]; AdjMatrix arcs; int vexnum,arcnum; 
};typedef struct
{ Vertex adjvex; /*当前点*/int lowcost;    /*代价*/
}minside[MAX_VERTEX_NUM];int LocateVex(MGraph G,Vertex u)//定位
{ int i;for(i=0;i<G.vexnum;++i)if(strcmp(u,G.vexs[i])==0)return i;return -1;
}void CreateGraph(MGraph &G)
{int i,j,k,w;Vertex va,vb;printf("请输入无向网G的顶点数和边数(以空格为分隔)\n");scanf("%d %d",&G.vexnum,&G.arcnum);printf("请输入%d个顶点的值(<%d个字符):\n",G.vexnum,MAX_NAME);for(i=0;i<G.vexnum;++i) /* 构造顶点集*/scanf("%s",G.vexs[i]);for(i=0;i<G.vexnum;++i) /*初始化邻接矩阵*/for(j=0;j<G.vexnum;++j)G.arcs[i][j]=0x7fffffff; printf("请输入%d条边的顶点1 顶点2 权值(以空格作为间隔): \n",G.arcnum);for(k=0;k<G.arcnum;++k){scanf("%s%s%d%*c",va,vb,&w); i=LocateVex(G,va);j=LocateVex(G,vb);G.arcs[i][j]=G.arcs[j][i]=w; /*对称*/}
}void kruskal(MGraph G){int set[MAX_VERTEX_NUM],i,j;int k=0,a=0,b=0,min=G.arcs[a][b];for(i=0;i<G.vexnum;i++)set[i]=i;printf("最小代价生成树的各条边为:\n");while(k<G.vexnum-1) { for(i=0;i<G.vexnum;++i)for(j=i+1;j<G.vexnum;++j)if(G.arcs[i][j]<min){min=G.arcs[i][j]; a=i; b=j; }min=G.arcs[a][b]=0x7fffffff; if(set[a]!=set[b]){printf("%s-%s\n",G.vexs[a],G.vexs[b]); k++; for(i=0;i<G.vexnum;i++)if(set[i]==set[b]) set[i]=set[a];}}}int main(){MGraph g;CreateGraph(g); kruskal(g); system("PAUSE");return 0;}
/*结果如下
请输入无向网G的顶点数和边数(以空格为分隔)
6 10
请输入6个顶点的值(<5个字符):
v1
v2
v3
v4
v5
v6
请输入10条边的顶点1 顶点2 权值(以空格作为间隔):
v1 v2 6
v1 v3 1
v1 v4 5
v2 v3 5
v2 v5 3
v4 v3 5
v4 v6 2
v3 v5 6
v3 v6 4
v5 v6 6
最小代价生成树的各条边为:
v1-v3
v4-v6
v2-v5
v3-v6
v2-v3
请按任意键继续. . .
*/
  

五,相对贪心问题

       例一,取数游戏。

        •问题描述

                2个人轮流取2n个数中的n个数,取数之和大者为胜。设计算法,让先取数者获胜,模拟取数过程。

        •问题分析

                这个游戏一般假设取数者只能看到2n个数中两边的数(第一次取时,能看到6,5则取6),用贪心算法的情况:

        •例如

               若一组数据为:6,16,27,6,12,9,2,11,6,5

               用贪心策略每次两人都取两边的数中较大的一个数,先取者胜.以A先取为例:

               取数结果为:

                      A  6,27,12,5,11=61  胜

                      B  16,6,9,6,2=39

              •但若选另一组数据:16,27,7,12,9,2,11,6

               仍都用贪心算法,先取者A败。

               取数结果为:

                        A  16,7,9,11=43

                        B  27,12,6,2=47 胜

           其实,若我们只能看到两边的数据,则此题无论先取还是后取都无必胜的策略。这时一般的策略是用近似贪心算法

           但若取数者能看到全部2n个数,则此问题可有一些简单的方法,有的虽不能保证所取数的和是最大,但确是一个先取者必胜的策略。


六,动态规划(各个问题包含公共子问题)

       1)最优决策原理:要求问题具有最优子结构(即最优解包含子问题的最优解),是一种自底向上的求解思路,与递归正好相反,每次求解到一个阶段时,该阶段求解所依赖的子问题已经完全求解完毕,因此每一步的求解都是在直到全部所需信息的情况下进行的,因此可以得到全局最优解。

       2)动态规划的决策过程:最优决策是在最后阶段形成的,然后向前倒推,直到初始阶段;而决策的具体结果及所产生的状态转移,却是由初始阶段开始进行计算的,然后向后递归或迭代,直到最终结果。

       3)适用条件

         任何思想方法都有一定的局限性,超出了特定条件,它就失去了作用。同样,动态规划也并不是万能的。适用动态规划的问题必须满足最优化原理和无后效性。
         1.最优化原理(最优子结构性质) 最优化原理可这样阐述:一个最优化策略具有这样的性质,不论过去状态和决策如何,对前面的决策所形成的状态而言,余下的诸决策必须构成最优策略。简而言之,一个最优化策略的子策略总是最优的。一个问题满足最优化原理又称其具有最优子结构性质。
         2.无后效性:将各阶段按照一定的次序排列好之后,对于某个给定的阶段状态,它以前各阶段的状态无法直接影响它未来的决策,而只能通过当前的这个状态。换句话说,每个状态都是过去历史的一个完整总结。这就是无后向性,又称为无后效性。

         3.子问题的重叠性:动态规划将原来具有指数级复杂度的搜索算法改进成了具有多项式时间的算法。其中的关键在于解决冗余,这是动态规划算法的根本目的。 动态规划实质上是一种以空间换时间的技术,它在实现的过程中,不得不存储产生过程中的各种状态,所以它的空间复杂度要大于其它的算法

 

     例题:著名的货郎担(旅行售货商)问题

                 详细解答参见博文------货郎担(旅行售货商)

 

 

七,回溯

        1)设计思想

              回溯与分支限界技术实际上都是基于穷举方法的,即按照一定规律,把问题所有可能的解组织成某种树结构,形成可能的解空间树或状态空间树。然后按照具体问题的约束条件,通过各种搜索策略,遍历可能的解空间树。从而得到满足问题条件的解或最优解。两种算法设计思路相近、本质一致。

        2)回溯与分支限界法解决实际问题,大致可分为四个环节:

             (1)确定问题的可能解空间,相当于找出进行穷举的搜索范围。

             (2)以一种便于搜索的方式组织所有的可能解,一般是生成可能解空间树

             (3)以某种方式搜索可能的解空间树,有两种基本搜索方式。即:深度优先搜索方式和,这就是回溯技术;广度优先搜索,就是分支限界技术。

             (4)在搜索过程中利用判定函数,也称为限界函数,通过“剪枝”来加速搜索过程

       3)回溯法的设计原理

             按照深度优先搜索的方式,从根结点出发搜索状态空间树。

             •   每搜索到达状态空间树的一个扩展结点,总是先判断以该结点为根的子树是否包含问题的解。如果肯定不包含,则跳过对该结点为根的子树的进一步搜索,该结点成为一个死结点,同时应向上层回溯至最近的一个活动结点。再以该活动结点作为当前新的扩展结点。以这种方式递归地在解空间中搜索,直至找到问题的解,或者解空间中已无活动结点为止,即此问题无解。

             •   在回溯法中,为了避免生成那些不可能产生最佳解的问题状态,要不断地利用限界函数来处死那些实际上不可能产生所需解的活动结点,以减少问题的计算量。所以,回溯法应是具有限界函数的深度优先搜索法。

             用回溯法解题时,常遇到两类典型的解空间树,子集树与排列树。

  

         例题:著名的八皇后问题

                    详细解答参见博文------八皇后问题

 

八,分支限界(求问题在某种意义下的最优解

       1)分支限界法的设计原理

             分支限界法类似于回溯法,也是一种在问题的状态空间树上搜索解的算法。但是,分支限界法与回溯法有不同的求解目标。回溯法的求解目标是找出状态空间树中的所有回答结点或任一回答结点,分支限界法的求解目标则是找出使得某一目标函数达到极小或极大的一个问题结点

       2)分支限界法与回溯法有两点不同:

           1)求解目标不同。回溯法的求解目标是找出解空间树中满足约束条件的所有解,而分支限界法的求解目标则是找出满足约束条件的一个解或最优解

           (2)搜索方式不同。回溯法以深度优先的方式搜索解空间树,而分支限界法则以广度优先或以最小耗费优先的方式搜索解空间树。

      3)常见的两种分支限界法

          (1)队列式(FIFO)分支限界法
                  按照队列先进先出(FIFO)原则选取下一个结点为扩展结点。
          (2)优先队列式分支限界法
                  按照优先队列中规定的优先级选取优先级最高的结点成为当前扩展结点。
     4)常见问题

            装箱问题、布线问题、单源最短路径问题、最大团问题、0-1背包问题、旅行售货问题

 

这篇关于【算法复习二】传统基本算法(贪心、动态规划、回溯和分支限界)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/877381

相关文章

SpringBoot实现MD5加盐算法的示例代码

《SpringBoot实现MD5加盐算法的示例代码》加盐算法是一种用于增强密码安全性的技术,本文主要介绍了SpringBoot实现MD5加盐算法的示例代码,文中通过示例代码介绍的非常详细,对大家的学习... 目录一、什么是加盐算法二、如何实现加盐算法2.1 加盐算法代码实现2.2 注册页面中进行密码加盐2.

Java时间轮调度算法的代码实现

《Java时间轮调度算法的代码实现》时间轮是一种高效的定时调度算法,主要用于管理延时任务或周期性任务,它通过一个环形数组(时间轮)和指针来实现,将大量定时任务分摊到固定的时间槽中,极大地降低了时间复杂... 目录1、简述2、时间轮的原理3. 时间轮的实现步骤3.1 定义时间槽3.2 定义时间轮3.3 使用时

SpringBoot整合MybatisPlus的基本应用指南

《SpringBoot整合MybatisPlus的基本应用指南》MyBatis-Plus,简称MP,是一个MyBatis的增强工具,在MyBatis的基础上只做增强不做改变,下面小编就来和大家介绍一下... 目录一、MyBATisPlus简介二、SpringBoot整合MybatisPlus1、创建数据库和

mybatis-plus 实现查询表名动态修改的示例代码

《mybatis-plus实现查询表名动态修改的示例代码》通过MyBatis-Plus实现表名的动态替换,根据配置或入参选择不同的表,本文主要介绍了mybatis-plus实现查询表名动态修改的示... 目录实现数据库初始化依赖包配置读取类设置 myBATis-plus 插件测试通过 mybatis-plu

如何通过Golang的container/list实现LRU缓存算法

《如何通过Golang的container/list实现LRU缓存算法》文章介绍了Go语言中container/list包实现的双向链表,并探讨了如何使用链表实现LRU缓存,LRU缓存通过维护一个双向... 目录力扣:146. LRU 缓存主要结构 List 和 Element常用方法1. 初始化链表2.

基于Canvas的Html5多时区动态时钟实战代码

《基于Canvas的Html5多时区动态时钟实战代码》:本文主要介绍了如何使用Canvas在HTML5上实现一个多时区动态时钟的web展示,通过Canvas的API,可以绘制出6个不同城市的时钟,并且这些时钟可以动态转动,每个时钟上都会标注出对应的24小时制时间,详细内容请阅读本文,希望能对你有所帮助...

Vue中动态权限到按钮的完整实现方案详解

《Vue中动态权限到按钮的完整实现方案详解》这篇文章主要为大家详细介绍了Vue如何在现有方案的基础上加入对路由的增、删、改、查权限控制,感兴趣的小伙伴可以跟随小编一起学习一下... 目录一、数据库设计扩展1.1 修改路由表(routes)1.2 修改角色与路由权限表(role_routes)二、后端接口设计

前端 CSS 动态设置样式::class、:style 等技巧(推荐)

《前端CSS动态设置样式::class、:style等技巧(推荐)》:本文主要介绍了Vue.js中动态绑定类名和内联样式的两种方法:对象语法和数组语法,通过对象语法,可以根据条件动态切换类名或样式;通过数组语法,可以同时绑定多个类名或样式,此外,还可以结合计算属性来生成复杂的类名或样式对象,详细内容请阅读本文,希望能对你有所帮助...

Python中多线程和多进程的基本用法详解

《Python中多线程和多进程的基本用法详解》这篇文章介绍了Python中多线程和多进程的相关知识,包括并发编程的优势,多线程和多进程的概念、适用场景、示例代码,线程池和进程池的使用,以及如何选择合适... 目录引言一、并发编程的主要优势二、python的多线程(Threading)1. 什么是多线程?2.

golang字符串匹配算法解读

《golang字符串匹配算法解读》文章介绍了字符串匹配算法的原理,特别是Knuth-Morris-Pratt(KMP)算法,该算法通过构建模式串的前缀表来减少匹配时的不必要的字符比较,从而提高效率,在... 目录简介KMP实现代码总结简介字符串匹配算法主要用于在一个较长的文本串中查找一个较短的字符串(称为