算法总结---最常用的五大算法（算法题思路）
一、总结一句话总结：【明确所求：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】【分别从初始序列“61279345108”两端开始“探测”。先从右往左找一个小于6的数，再从左往右找一个大于6的数，然后交换他们】【交换哨兵ij对应的值】【哨兵ij相遇，交换相遇的位置和基准数】【哨兵i走过的位置所有的都比基准数小，j走过的都大】【设置的基准数是最左边的数，所以需要让哨兵j先出动：因为j会先发现比基准小的数，然后ij再相遇，然后在交换基准数和ij相遇的这个数】归并排序：【递归实现】【一直拆分到一个数】【排序完再合并】【利用完全二叉树特性的排序】【操作数组下标实现二叉树】【合并的过程和链表合并有点相似】
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方格的棋盘上，从任意指定方格出发，为马寻找一条走遍棋盘每一格并且只经过一次的一条最短路径。
二、分治算法
思想：
分治法应用场景：
运用分治策略解决的问题一般来说具有以下特点：1、原问题可以分解为多个子问题这些子问题与原问题相比，只是问题的规模有所降低，其结构和求解方法与原问题相同或相似。2、原问题在分解过程中，递归地求解子问题由于递归都必须有一个终止条件，因此，当分解后的子问题规模足够小时，应能够直接求解。3、在求解并得到各个子问题的解后应能够采用某种方式、方法合并或构造出原问题的解。不难发现，在分治策略中，由于子问题与原问题在结构和解法上的相似性，用分治方法解决的问题，大都采用了递归的形式。在各种排序方法中，如归并排序、堆排序、快速排序等，都存在有分治的思想。
分治法解题的一般步骤：
（1）分解，将要解决的问题划分成若干规模较小的同类问题；（2）求解，当子问题划分得足够小时，用较简单的方法解决；（3）合并，按原问题的要求，将子问题的解逐层合并构成原问题的解。
三、动态规划
基本思想：
与分治法最大的差别是：适合于用动态规划法求解的问题，经分解后得到的子问题往往不是互相独立的（即下一个子阶段的求解是建立在上一个子阶段的解的基础上，进行进一步的求解）
应用场景：
适用动态规划的问题必须满足最优化原理、无后效性和重叠性。1.最优化原理（最优子结构性质）最优化原理可这样阐述：一个最优化策略具有这样的性质，不论过去状态和决策如何，对前面的决策所形成的状态而言，余下的诸决策必须构成最优策略。简而言之，一个最优化策略的子策略总是最优的。一个问题满足最优化原理又称其具有最优子结构性质。
2.无后效性将各阶段按照一定的次序排列好之后，对于某个给定的阶段状态，它以前各阶段的状态无法直接影响它未来的决策，而只能通过当前的这个状态。换句话说，每个状态都是过去历史的一个完整总结。这就是无后向性，又称为无后效性。
求全路径最短路径的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(总重量)时背包中所放物品的最大价值。
四、回溯法
回溯法在问题的解空间树中，按深度优先策略，从根结点出发搜索解空间树。算法搜索至解空间树的任意一点时，先判断该结点是否包含问题的解。如果肯定不包含（剪枝过程），则跳过对该结点为根的子树的搜索，逐层向其祖先结点回溯；否则，进入该子树，继续按深度优先策略搜索。
回溯法就是对隐式图的深度优先搜索算法
回溯法：为了避免生成那些不可能产生最佳解的问题状态，要不断地利用限界函数(boundingfunction)来处死(剪枝)那些实际上不可能产生所需解的活结点，以减少问题的计算量。具有限界函数的深度优先生成法称为回溯法。（回溯法=穷举+剪枝）
一般步骤：
(1)针对所给问题，定义问题的解空间；(2)确定易于搜索的解空间结构；(3)以深度优先方式搜索解空间，并在搜索过程中用剪枝函数避免无效搜索。
两个常用的剪枝函数：
(1)约束函数：在扩展结点处减去不满足约束的子数(2)限界函数：减去得不到最优解的子树
用回溯法解题的一个显著特征是在搜索过程中动态产生问题的解空间。在任何时刻，算法只保存从根结点到当前扩展结点的路径。如果解空间树中从根结点到叶结点的最长路径的长度为h(n)，则回溯法所需的计算空间通常为O(h(n))。而显式地存储整个解空间则需要O(2^h(n))或O(h(n)!)内存空间。
五、分支限界法
分支限界法与回溯法的区别：
1、问题描述在下图所给的有向图G中，每一边都有一个非负边权。要求图G的从源顶点s到目标顶点t之间的最短路径。
下图是用优先队列式分支限界法解有向图G的单源最短路径问题产生的解空间树。其中，每一个结点旁边的数字表示该结点所对应的当前路长。
找到一条路径：
目前的最短路径是8，一旦发现某个结点的下界不小于这个最短路进，则剪枝：
同一个结点选择最短的到达路径：
2.剪枝策略在算法扩展结点的过程中，一旦发现一个结点的下界不小于当前找到的最短路长，则算法剪去以该结点为根的子树。在算法中，利用结点间的控制关系进行剪枝。从源顶点s出发，2条不同路径到达图G的同一顶点。由于两条路径的路长不同，因此可以将路长长的路径所对应的树中的结点为根的子树剪去。3.算法思想解单源最短路径问题的优先队列式分支限界法用一极小堆来存储活结点表。其优先级是结点所对应的当前路长。算法从图G的源顶点s和空优先队列开始。结点s被扩展后，它的儿子结点被依次插入堆中。此后，算法从堆中取出具有最小当前路长的结点作为当前扩展结点，并依次检查与当前扩展结点相邻的所有顶点。如果从当前扩展结点i到顶点j有边可达，且从源出发，途经顶点i再到顶点j的所相应的路径的长度小于当前最优路径长度，则将该顶点作为活结点插入到活结点优先队列中。这个结点的扩展过程一直继续到活结点优先队列为空时为止。