算法总结---最常⽤的五⼤算法（算法题思路）算法总结---最常⽤的五⼤算法（算法题思路）
⼀、总结
⼀句话总结：
> 【明确所求：dijkstra是求点到点的距离，辅助数组就是源点到⽬标点的数组】
> 【最简实例分析：⽐如思考dijkstra：假设先只有三个点】
1、贪⼼算法是什么？
> 当前看来最好的选择
> 局部最优解
> 可能得到整体最优解或是最优解的近似解
贪⼼算法（⼜称贪婪算法）是指，在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，他所做出的仅是在某种意义上的局部最优解。贪⼼算法不是对所有问题都能得到整体最优解，但对范围相当⼴泛的许多问题他能产⽣整体最优解或者是整体最优解的近似解。
2、贪⼼算法实例？
> 求最⼩⽣成树的Prim算法：【边集中依次选取那些权值最⼩的边】
> 求最⼩⽣成树的Kruskal算法：【和求最短路径有点相似：不过这⾥是求两个集合之间的距离】：【⼀维中间数组记录到当前已经选择顶点的最短距离】：【⼆维表记录每个点到每个点的最短距离】
> 计算强连通⼦图的Dijkstra算法：【和最⼩⽣成树Kruskal类似】【⼆维表记录每个点到每个点的最短距离】【明确所求：dijkstra是求点到点的距离，辅助数组就是源点到⽬标点的数组】【每次从辅助数组中选择最⼩的，⽤选出的点来更新辅助数组】【最简实例分析：⽐如思考dijkstra：假设先只有三个点】
> 构造huffman树的算法：【每次都选取权值⼩的两个点合成⼆叉树】
Kruskal算法简述
在带权连通图中，不断地在边集合中到最⼩的边，如果该边满⾜得到最⼩⽣成树的条件，就将其构造，直到最后得到⼀颗最⼩⽣成树。
假设 WN=(V,{E}) 是⼀个含有 n 个顶点的连通⽹，则按照克鲁斯卡尔算法构造的过程为：先构造⼀个只含 n 个顶点，⽽边集为空的⼦图，若将该⼦图中各个顶点看成是各棵树上的根结点，则它是⼀个含有 n
棵树的⼀个森林。之后，从⽹的边集 E 中选取⼀条权值最⼩的边，若该条边的两个顶点分属不同的树，则将其加⼊⼦图，也就是说，将这两个顶点分别所在的两棵树合成⼀棵树；反之，若该条边的两个顶点已落在同⼀棵树上，则不可取，⽽应该取下⼀条权值最⼩的边再试之。依次类推，直⾄森林中只有⼀棵树，也即⼦图中含有 n-1条边为⽌。
普利姆算法的核⼼步骤是：
在带权连通图中，从图中某⼀顶点v开始，此时集合U={v}，重复执⾏下述操作：在所有u∈U,w∈V-U的边(u,w)∈E中到⼀条权值最⼩的边，将(u,w)这条边加⼊到已到边的集合，并且将点w加⼊到集合U中，当U=V时，就到了这颗最⼩⽣成树。
3、分治法的思想？
> 规模为N的问题分解为K个规模较⼩的⼦问题
> 这些⼦问题相互独⽴且与原问题性质相同
> 解题思路：分解->求解->合并
分治算法的基本思想是将⼀个规模为N的问题分解为K个规模较⼩的⼦问题，这些⼦问题相互独⽴且与原问题性质相同。求出⼦问题的解，
就可得到原问题的解。
4、分治法实例？
> ⼆分法：猜数字游戏，【你给数字我来猜】
> 快排：【选取基准数（⽐如第⼀个），⽐我⼩的往前挪，⽐我⼤的往后挪】【辅助变量：指向第⼀个数据的哨兵i，指向最后⼀个数据的哨兵j】【分别从初始序列“6  1  2 7  9  3  4  5 10  8”两端开始“探测”。先从右往左⼀个⼩于6的数，再从左往右⼀个⼤于6的数，然后交换他们】【交换哨兵ij对应的值】【哨兵ij相遇，交换相遇的位置和基准数】【哨兵i⾛过的位置所有的都⽐基准数⼩，j⾛过的都⼤】【设置的基准数是最左边的数，所以需要让哨兵j先出动：因为j会先发现⽐基准⼩的数，然后ij再相遇，然后在交换基准数和ij相遇的这个数】
> 归并排序：【递归实现】【⼀直拆分到⼀个数】【排序完再合并】【利⽤完全⼆叉树特性的排序】【操作数组下标实现⼆叉树】【合并的过程和链表合并有点相似】
5、动态规划基本思想？
> 空间换时间：如果我们能够保存已解决的⼦问题的答案，⽽在需要时再出已求得的答案，这样就可以避免⼤量的重复计算，节省时间。
> 和分治法的区别：与分治法不同的是，适合于⽤动态规划求解的问题，【经分解得到⼦问题往往不是互相独⽴的】。若⽤分治法来解这类问题，则【分解得到的⼦问题数⽬太多】，有些【⼦问题被重复计算了很多次】。
> 状态转移⽅程如何书写：【看如何将问题分解为⼦问题：分解的过程就是状态转移⽅程】【确定状态，就是所求：dijkstra是求点到点的距离，辅助数组就是源点到⽬标点的数组】【最简实例分析：⽐如思考dijkstra：假设先只有三个点】
6、动态规划实例？
> 求全路径最短路径的Floyd算法：【从i号顶点到j号顶点只经过前k号点的最短路程】
> 背包问题：【从背包中取哪⼏个有最优价值】
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];
7、回溯法基本思想？
> 深度优先算法
> 搜索某⼀步时，⾛不通，就退回
> 剪枝：回溯法优化
回溯法（探索与回溯法）是⼀种选优搜索法，按选优条件向前搜索，以达到⽬标。但当探索到某⼀步时，发现原先选择并不优或达不到⽬标，就退回⼀步重新选择，这种⾛不通就退回再⾛的技术为回溯法，⽽满⾜回溯条件的某个状态的点称为“回溯点”。
8、回溯法经典实例？
> ⼋皇后：
9、分⽀限界法的基本思想？
> ⼴度优先搜索：节点出队，节点的孩⼦全⼊队操作
> 常见两种：队列式和优先队列式
分⽀限界法常以⼴度优先或以最⼩耗费（最⼤效益）优先的⽅式搜索问题的解空间树。
在分⽀限界法中，每⼀个活结点只有⼀次机会成为扩展结点。活结点⼀旦成为扩展结点，就⼀次性产⽣其所有⼉⼦结点。在这些⼉⼦结点中，导致不可⾏解或导致⾮最优解的⼉⼦结点被舍弃，其余⼉⼦结点被加⼊活结点表中。
此后，从活结点表中取下⼀结点成为当前扩展结点，并重复上述结点扩展过程。这个过程⼀直持续到到所需的解或活结点表为空时为⽌。常见的两种分⽀限界法：
（1）队列式(FIFO)分⽀限界法
按照队列先进先出（FIFO）原则选取下⼀个节点为扩展节点。
（2）优先队列式分⽀限界法
按照优先队列中规定的优先级选取优先级最⾼的节点成为当前扩展节点。
10、分⽀限界法与回溯法的区别？
> 求解⽬标：回溯-所有解，分⽀限界法-⼀个解
> 搜索⽅式：回溯-深搜，分⽀限界法-⼴搜
（1）求解⽬标：回溯法的求解⽬标是出解空间树中满⾜约束条件的所有解，⽽分⽀限界法的求解⽬标则是出满⾜约束条件的⼀个解，或是在满⾜约束条件的解中出在某种意义下的最优解。
（2）搜索⽅式的不同：回溯法以深度优先的⽅式搜索解空间树，⽽分⽀限界法则以⼴度优先或以最⼩耗费优先的⽅式搜索解空间树。
⼆、最常⽤的五⼤算法（转）
⼀、贪⼼算法
贪⼼算法（⼜称贪婪算法）是指，在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，他所做出的仅是在某种意义上的局部最优解。贪⼼算法不是对所有问题都能得到整体最优解，但对范围相当⼴泛的许多问题他能产⽣整体最优解或者是整体最优解的近似解。
⽤贪⼼法设计算法的特点是⼀步⼀步地进⾏，常以当前情况为基础根据某个优化测度作最优选择，⽽不考虑各种可能的整体情况，它省去了为最优解要穷尽所有可能⽽必须耗费的⼤量时间，它采⽤⾃顶向
下，以迭代的⽅法做出相继的贪⼼选择，每做⼀次贪⼼选择就将所求问题简化为⼀个规模更⼩的⼦问题，通过每⼀步贪⼼选择，可得到问题的⼀个最优解，虽然每⼀步上都要保证能获得局部最优解，但由此产⽣的全局解有时不⼀定是最优的，所以贪⼼法不需要回溯。
注意：对于⼀个给定的问题，往往可能有好⼏种量度标准。初看起来，这些量度标准似乎都是可取的，但实际上，⽤其中的⼤多数量度标准作贪婪处理所得到该量度意义下的最优解并不是问题的最优解，⽽是次优解。因此，选择能产⽣问题最优解的最优量度标准是使⽤贪婪算法的核⼼。
经典的求最⼩⽣成树的Prim算法和Kruskal算法、计算强连通⼦图的Dijkstra算法、构造huffman树的算法都是漂亮的贪⼼算法
基本思路：
⒈建⽴数学模型来描述问题。
⒉把求解的问题分成若⼲个⼦问题。
⒊对每⼀⼦问题求解，得到⼦问题的局部最优解。
⒋把⼦问题的解局部最优解合成原来解问题的⼀个解。
实现该算法的过程：
从问题的某⼀初始解出发；
while 能朝给定总⽬标前进⼀步 do
求出可⾏解的⼀个解元素；
由所有解元素组合成问题的⼀个可⾏解。
例⼦：
马踏棋盘的贪⼼算法
【问题描述】
马的遍历问题。在8×8⽅格的棋盘上，从任意指定⽅格出发，为马寻⼀条⾛遍棋盘每⼀格并且只经过⼀次的⼀条最短路径。
【贪⼼算法】
其实马踏棋盘的问题很早就有⼈提出，且早在1823年，J.C.Warnsdorff就提出了⼀个有名的算法。在每个结点对其⼦结点进⾏选取时，优先选择‘出⼝’最⼩的进⾏搜索，‘出⼝’的意思是在这些⼦结点中它们的可⾏⼦结点的个数，也就是‘孙⼦’结点越少的越优先跳，为什么要这样选取，这是⼀种局部调整最优的做法，如果优先选择出⼝多的⼦结点，那出⼝少的⼦结点就会越来越多，很可能出现‘死’结点（顾名思义就是没有出⼝⼜没有跳过的结点），这样对下⾯的搜索纯粹是徒劳，这样会浪费很多⽆⽤的时间，反过来如果每次都优先选择出⼝少的结点跳，那出⼝少的结点就会越来越少，这样跳成功的机会就更⼤⼀些。
⼆、分治算法
思想：
分治算法的基本思想是将⼀个规模为N的问题分解为K个规模较⼩的⼦问题，这些⼦问题相互独⽴且与原问题性质相同。求出⼦问题的解，就可得到原问题的解。
分治法应⽤场景：
运⽤分治策略解决的问题⼀般来说具有以下特点：
1、原问题可以分解为多个⼦问题
这些⼦问题与原问题相⽐，只是问题的规模有所降低，其结构和求解⽅法与原问题相同或相似。
2、原问题在分解过程中，递归地求解⼦问题
由于递归都必须有⼀个终⽌条件，因此，当分解后的⼦问题规模⾜够⼩时，应能够直接求解。
3、在求解并得到各个⼦问题的解后
应能够采⽤某种⽅式、⽅法合并或构造出原问题的解。
不难发现，在分治策略中，由于⼦问题与原问题在结构和解法上的相似性，⽤分治⽅法解决的问题，⼤都采⽤了递归的形式。在各种排序⽅法中，如归并排序、堆排序、快速排序等，都存在有分治的思想。
分治法解题的⼀般步骤：
（1）分解，将要解决的问题划分成若⼲规模较⼩的同类问题；
（2）求解，当⼦问题划分得⾜够⼩时，⽤较简单的⽅法解决；
（3）合并，按原问题的要求，将⼦问题的解逐层合并构成原问题的解。
三、动态规划
基本思想：
动态规划算法通常⽤于求解具有某种最优性质的问题。在这类问题中，可能会有许多可⾏解。每⼀个解都对应于⼀个值，我们希望到具有最优值的解。动态规划算法与分治法类似，其基本思想也是将待求解问题分解成若⼲个⼦问题，先求解⼦问题，然后从这些⼦问题的解得到原问题的解。与分治法不同的是，适合于⽤动态规划求解的问题，经分解得到⼦问题往往不是互相独⽴的。若⽤分治法来解这类问题，则分解得到的⼦问题数⽬太多，有些⼦问题被重复计算了很多次。如果我们能够保存已解决的⼦问题的答案，⽽在需要时再出已求得的答案，这样就可以避免⼤量的重复计算，节省时间。我们可以⽤⼀个表来记录所有已解的⼦问题的答案。不管该⼦问题以后是否被⽤到，只要它被计算过，就将其结果填⼊表中。这就是动态规划法的基本思路。具体的动态规划算法多种多样，但它们具有相同的填表格式。
与分治法最⼤的差别是：适合于⽤动态规划法求解的问题，经分解后得到的⼦问题往往不是互相独⽴的（即下⼀个⼦阶段的求解是建⽴在上⼀个⼦阶段的解的基础上，进⾏进⼀步的求解）
应⽤场景：
适⽤动态规划的问题必须满⾜最优化原理、⽆后效性和重叠性。
1.最优化原理（最优⼦结构性质）最优化原理可这样阐述：⼀个最优化策略具有这样的性质，不论过去状态和决策如何，对前⾯的决策所形成的状态⽽⾔，余下的诸决策必须构成最优策略。简⽽⾔之，⼀个
最优化策略的⼦策略总是最优的。⼀个问题满⾜最优化原理⼜称其具有最优⼦结构性质。
2.⽆后效性将各阶段按照⼀定的次序排列好之后，对于某个给定的阶段状态，它以前各阶段的状态⽆法直接影响它未来的决策，⽽只能通过当前的这个状态。换句话说，每个状态都是过去历史的⼀个完整总结。这就是⽆后向性，⼜称为⽆后效性。
3.⼦问题的重叠性动态规划将原来具有指数级时间复杂度的搜索算法改进成了具有多项式时间复杂度的算法。其中的关键在于解决冗余，这是动态规划算法的根本⽬的。动态规划实质上是⼀种以空间换时间的技术，它在实现的过程中，不得不存储产⽣过程中的各种状态，所以它的空间复杂度要⼤于其它的算法。
求全路径最短路径的Floyd算法就是漂亮地运⽤了动态规划思想。
下⾯是我到的⼀个关于0-1背包问题的动态规划思想PPT截图：
问题描述：
给定n种物品和⼀背包。物品i的重量是wi，其价值为vi，背包的容量为C。问应如何选择装⼊背包的物品，使得装⼊背包中物品的总价值最⼤?
对于⼀种物品，要么装⼊背包，要么不装。所以对于⼀种物品的装⼊状态可以取0和1.我们设物品i的装⼊状态为xi,xi∈ (0,1)，此问题称为0-11背包问题。
数据：物品个数n=5，物品重量w[n]={0，2，2，6，5，4}，物品价值V[n]={0，6，3，5，4，6},
（第0位，置为0，不参与计算，只是便于与后⾯的下标进⾏统⼀，⽆特别⽤处，也可不这么处理。）总重量c=10。背包的最⼤容量为10，那么在设置数组m⼤⼩时，可以设⾏列值为6和11，那么，对于m(i,j)就表⽰可选物品为i…n背包容量为j(总重量)时背包中所放物品的最⼤价值。
四、回溯法
回溯法（探索与回溯法）是⼀种选优搜索法，按选优条件向前搜索，以达到⽬标。但当探索到某⼀步时，发现原先选择并不优或达不到⽬标，就退回⼀步重新选择，这种⾛不通就退回再⾛的技术为回溯法，⽽满⾜回溯条件的某个状态的点称为“回溯点”。
基本思想：
回溯法在问题的解空间树中，按深度优先策略，从根结点出发搜索解空间树。算法搜索⾄解空间树的任意⼀点时，先判断该结点是否包含问题的解。如果肯定不包含（剪枝过程），则跳过对该结点为根的⼦树的搜索，逐层向其祖先结点回溯；否则，进⼊该⼦树，继续按深度优先策略搜索。
回溯法就是对隐式图的深度优先搜索算法
回溯法：为了避免⽣成那些不可能产⽣最佳解的问题状态，要不断地利⽤限界函数(bounding function)来处死(剪枝)那些实际上不可能产⽣所需解的活结点，以减少问题的计算量。具有限界函数的深度优先⽣成法称为回溯法。（回溯法 = 穷举 +　剪枝）
⼀般步骤：
(1)针对所给问题，定义问题的解空间；
(2)确定易于搜索的解空间结构；
完全二叉树算法(3)以深度优先⽅式搜索解空间，并在搜索过程中⽤剪枝函数避免⽆效搜索。
两个常⽤的剪枝函数：
(1)约束函数：在扩展结点处减去不满⾜约束的⼦数
(2)限界函数：减去得不到最优解的⼦树
  ⽤回溯法解题的⼀个显著特征是在搜索过程中动态产⽣问题的解空间。在任何时刻，算法只保存从根
结点到当前扩展结点的路径。如果解空间树中从根结点到叶结点的最长路径的长度为h(n)，则回溯法所需的计算空间通常为O(h(n))。⽽显式地存储整个解空间则需要O(2^h(n))或O(h(n)!)内存空间。
五、分⽀限界法

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。