文享日志

算法要点概述

算法

发表于2018年09月04日13:27:55

更新于2018年09月06日21:56:35

0条评论 152次阅读

概念:

      算法是一系列解决问题的明确指令,也就是说,对于一个符合一定规范的输入,能够在有限的时间内获得要求的输出。


效率分析:

算法效率有两种:时间复杂度与空间复杂度。

时间复杂度指出正在讨论的算法运行得有多快;空间复杂度关心算法需要的额外空间。


重要问题:

排序、查找、字符串处理、图问题、组合问题、几何问题、数组问题


具体问题:

最近对问题:在一个包含n个点的几何中,找出距离最近的两个点。(注意是在平面或者高维空间)

凸包问题:在平面或者高维空间的一个给定点几何中寻找凸包。(凸包就是图形是凸的,有顶点的所有顶点是凸的,没顶点的就所有边的凸的)

旅行商问题:要求找出一条n个给定的城市间的最短路径,使在回到出发城市之前,对每个城市都只访问一次。

背包问题:给定n个重量不同的,价值不同的物品和一个背包,求这些物品中一个最有价值的子集,并且要能够装到背包里。


算法设计策略:

一、蛮力法:

蛮力法是一种简单直接地解决问题的方法,常常直接基于问题的描述和所设计的概念定义。


特点:

  1. 解决各领域的问题,通用性强

  2. 对于一些重要问题,蛮力法可以产生一些合理的算法,他们多少具备一些实用价值,而且不必限制实例的规模。

  3. 如果要解决的问题的实例不多,若能以一种可以接受的速度对实例求解,可以使用蛮力法。

  4. 解决小规模问题实例

  5. 作为研究或教学目的服务



求解问题:

1、选择排序

    选择排序开始时,扫描整个列表,找到最小元素,然后和第一个元素交换,将最小的元素放到它有序表中的最终位置。然后从第二个元素扫描,找到第二小元素,跟第二个元素交换...如此下去,列表就排好了。


2、冒泡排序

    冒泡排序比较表中相邻元素,如果他们是逆序,就交换他们的位置。重复多次以后,最大的元素就到了列表最后一个位置。第二遍操作将第二大元素沉到倒数第二...如此下去,列表就排好了。


3、凸包问题

     计算任意两点的直线方程,判断其他点是否在该直线的同一侧,若在的话,则该线是是凸包边界。


还有顺序查找、蛮力字符串匹配、最近对问题等用蛮力法解决较为容易,故此处略过


二、减治法

将原问题划分成若干问题,并且原问题的解与子问题的解之间存在某种确定的关系。


求解问题:

1、插入排序

    将序列分为“已排序”和“未排序”两部分,依次将“未排序”中的每一个记录插入到一个已排好序的序列中,直到全部记录都排好序。


2、折半查找

    利用二分法进行查找。在有序数组中,比较查找键与中间位置元素的值来确定要查找元素的范围,递归比较则求得解


3、选择问题

     给定一个序列T和一个整数k,寻找T的第k小元素的问题

     求解要用到快速排序中的原理,所以放到分治法中讲。


三、分治法

将一个难以直接解决的大问题划分成一些规模较小的子问题,分别求解各个子问题,再合并子问题的解。


求解问题:

1、合并排序

对于需要排序的数组,将该数组一分为二,对每个子数组递归排序,然后把这两个子数组合并为一个有序数组。

图例:

归并排序


2、快速排序

排序需要经历三个步骤:划分、求解子问题与合并

划分:任意选定一个记录为轴值,以轴值为基准将整个序列划分为两个子序列,在划分过程中,使得前一个子序列中的记录均小于或等于轴值,后一个子序列中的记录均大于或等于轴值。

求解子问题:对划分后的每一个子序列递归处理,继续进行划分

合并:对划分后的序列直接进行合并


图例:

快速排序

上面的文字描述我自己看的也有点懵,所以以图例中的示例,讲一下大概怎么求解这种问题。

先随便选一个轴值(图中选的是23为轴),进行第一次划分。轴值右侧序列开始与轴值比较,移动j指针,选择比较值,值比轴值小的,则与轴值进行交换,交换完之后,轴值右侧的值都比轴值大,此时移动i指针到下一个要比较的元素,判断元素与轴值大小,若比轴值小,则移动i到下一个元素,比轴值大,则继续进行交换。交换完之后,轴值左侧都比轴值小,右侧j之后都比轴值大,i到j之间的元素还未比较。。所以继续递归比较判断即可,直到i与j重合,说明比较完了。进行第一次划分之后,分别对子序列递归划分,最后合并即可。


选择问题:

选择问题利用快速排序的原理,在对序列进行一次划分后,比较轴值位置与k值(要求的第k小元素),若轴值位置等于k,则直接返回轴值。否则对左部分或者右部分子序列继续进行划分即可。


四、动态规划

动态规划法将问题划分为一个一个相互重叠的子问题,每个问题对应决策过程中的每个阶段。


最优性原理:无论决策过程的初始状态和初始决策是什么,其余的决策都必须相对于初始决策所产生的当前状态,构成一个最优决策序列。


求解问题:

1、多段图的最短路径问题

如图所示为一个带权有向图,求解从原点到终点的最小代价路径

解:

首先证明该问题满足最优性原理,然后再用动态规划法求解


设Cij为顶点i到顶点j之间的代价,d(i,j)为顶点i到顶点j之间的最短路径。

则以图为例,d(0,1) = C01 , d(0,4) = min{ d(0,1) + C14 , d(0,2) + C24 }

求解初始子问题,得

d(0,1) = C01 = 4 ; d(0,2) = C02 = 2 ; d(0,3) = C03 = 3 ;

求解下一阶段子问题,得

d(0,4) = min{ d(0,1) + C14 , d(0,2) + C24 } = 8 ;

d(0,5) = min{ d(0,1) + C15 , d(0,2) + C25 , d(0,3) + C35 } = 7 ;

d(0,6) = min{ d(0,2) + C26 , d(0,3) + C36 } = 10 ;

再求解下一阶段的子问题,有

d(0,7) = 13 ; d(0,8) = 13 ;

最后阶段

d(0,9) = min{ d(0,7) + C79 , d(0,8)+C89 } = 16 ;


将状态回溯,得到最短路径0-3-5-8-9,最短路径长度为16


五、贪心法

将一个复杂问题分解为一系列较为简单的局部最优选择,每一步选择都是对当前解的一个扩展,直到获得问题的完整解。


求解问题:

1、TSP问题

从任意城市出发,每次在没有到过的城市中选择最近的一个,直到经过了所有的城市,最后回到出发城市


2、图着色问题

随机选择一种颜色,然后尽可能的填涂多的点,直到不能用该色继续填涂为止,然后换下一种颜色...


3、背包问题

将物品按照单位重量价值从大到小排列,然后按排列顺序将物品放入背包。


六、回溯法

在包含问题的所有解空间树中,从根节点出发,按照深度优先搜索的策略进行搜索,对于解空间树的某个节点,如果该节点满足问题的约束条件,则进入该子树继续进行搜索,否则将以该节点为根节点的子树进行剪枝。


特点:

常常可以避免搜索所有的可能解,适用于求解组合数较大的问题


求解问题:

1、图着色问题

首先构造解空间树,每个节点的每个分支代表一种颜色,有多少种颜色,该节点就有多少个分支。从根节点出发,进行深度优先搜索,搜索到不满足约束条件的(即当前节点的颜色与父节点颜色相同),进行回溯,搜索下一个分支。直到得到可行解。



七、分支限界法

按广度优先搜索策略搜索问题的解空间树,在搜索的过程中,对待处理的节点根据限界函数估算目标函数的可能取值,从中选取使目标函数取得极值的节点优先进行广度优先搜索,从而不断的调整搜索方向,尽快找到问题的解。


      分支限界法首先确定一个合理的限界函数,并根据限界函数确定目标函数的界[down,up]。然后按照广度优先策略搜索问题的解空间树,在分支节点上,依次扩展该节点的所有孩子节点,分别估算这些孩子节点的目标函数的可能取值,如果某孩子节点的目标函数可能取值超过目标函数的界,则将其丢弃;否则,将其加入待处理节点表。依次从待处理节点表中选取使目标函数取得极值的节点称为当前的扩展节点,重复上述过程,直到找到最优解。


特点:

限界函数常常基于问题的目标函数而确定,所以适用于求解最优化问题







👍 0  👎 0
共有0条评论

发表新评论

提交

广告展示

腾讯云推广 阿里云推广