一：简介
（1）回溯法 又称试探法
回溯法的基本做法是深度优先搜索，是一种组织得井井有条的、能避免不必要重复搜索的穷举式搜索算法；基本思想是：从一条路往前走，能进则进，不能进则退回来，换一条路再试。适用场景：当遇到某一类问题时，它的问题可以分解，但是又不能得出明确的动态规划或是递归解法，此时可以考虑用回溯法解决此类问题。回溯法的优点在于其程序结构明确，可读性强，易于理解，而且通过对问题的分析可以大大提高运行效率。但是，对于可以得出明显的递推公式迭代求解的问题，还是不要用回溯法，因为它花费的时间比较长（不到万不得已，不要用回溯法，费时） —— 有时，感觉回溯法，非常类似于上一篇博客DFS+剪枝
（2）贪心算法 又称贪婪算法
在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，他所做出的仅是在某种意义上的局部最优解。贪心算法不是对所有问题都能得到整体最优解，关键是贪心策略的选择，选择的贪心策略必须具备无后效性，即某个状态以前的过程不会影响以后的状态，只与当前状态有关。它与动态规划相对的，动态规划，是寻找子问题，子问题与原问题有极大的相似性，求解是全局最优
（3）递归和回溯
递归是一种算法结构，回溯是一种算法思想；一个递归就是在函数中调用函数本身来解决问题；回溯就是通过不同的尝试来生成问题的解，有点类似于穷举，但是和穷举不同的是回溯会“剪枝”，意思就是对已经知道错误的结果没必要再枚举接下来的答案了，比如一个有序数列1,2,3,4,5，我要找和为5的所有集合，从前往后搜索我选了1，然后2，然后选3 的时候发现和已经大于预期，，那么4,5肯定也不行，这就是一种对搜索过程的优化。
二：案例详解
（1）回溯法详解
首先要将问题转化，得出状态空间树。这棵树的每条完整路径都代表了一种解的可能。通过深度优先搜索这棵树，枚举每种可能的解的情况；从而得出结果。但是，回溯法中通过构造约束函数，可以大大提升程序效率，因为在深度优先搜索的过程中，不断的将每个解（并不一定是完整的，事实上这也就是构造约束函数的意义所在）与约束函数进行对照从而删除一些不可能的解，这样就不必继续把解的剩余部分列出从而节省部分时间。回溯法中三个概念：（一）约束函数：约束函数是根据题意定出的。通过描述合法解的一般特征用于去除不合法的解，从而避免继续搜索出这个不合法解的剩余部分。因此，约束函数是对于任何状态空间树上的节点都有效、等价的。（二）状态空间树：刚刚已经提到，状态空间树是一个对所有解的图形描述。树上的每个子节点的解都只有一个部分与父节点不同。（三）扩展节点、活结点、死结点：所谓扩展节点，就是当前正在求出它的子节点的节点，在深度优先搜索中，只允许有一个扩展节点。活结点就是通过与约束函数的对照，节点本身和其父节点均满足约束函数要求的节点；死结点反之。由此很容易知道死结点是不必求出其子节点的（没有意义）。利用回溯法解题的具体步骤
（2）回溯法的实现步骤
通过读题完成下面三个步骤：1)描述解的形式，定义一个解空间，它包含问题的所有解。2)构造状态空间树。3)构造约束函数（用于杀死节点）。然后就要通过深度优先搜索思想完成回溯，完整过程如下：1)设置初始化的方案（给变量赋初值，读入已知数据等）。2)变换方式去试探，若全部试完则转(7)。3)判断此法是否成功（通过约束函数），不成功则转(2)。4)试探成功则前进一步再试探。5)正确方案还未找到则转(2)。6)已找到一种方案则记录并打印。7)退回一步（回溯），若未退到头则转(2)。8)已退到头则结束或打印无解
（3）回溯法示例（连同图格数）
#include<iostream>#include<cstring>using namespace std;#define isBound(a,b) (a<0 || a>=b)const int maxN = 21;char map[maxN][maxN];bool visit[maxN][maxN];int w,h,ans;void dfs(int row,int col){if(isBound(row,h)||isBound(col,w)||map[row][col]=='#'||visit[row][col])return;visit[row][col] = true;ans ++;dfs(row,col-1);dfs(row-1,col);dfs(row,col+1);dfs(row+1,col);}int main(){int i,j,row,col;char flg = '@';while(cin>>w>>h&&(w||h)){ans = 0;memset(visit,false,sizeof(visit));for(i=0;i<h;++i){for(j=0;j<w;++j){cin >> map[i][j];if(flg == map[i][j]){row = i;col = j;}}}dfs(row,col);cout << ans << endl;}return 0;}//POJ 1979 Red and Black(利用回溯法来扫图可以记忆搜索了，设置一个avilable数组记录是否可以到达。
如果一个位置avilable为真，证明已经搜索过这个点了，不再重复搜索。通过这个点可以到达的位置必然已经标记为avilable了。
（4）回溯法示例二（全排列）
# include <stdio.h>void swap2 (char *x, char *y){char temp;temp = *x;*x = *y;*y = temp;}/* 打印字符串的全排列*/void permute(char *str, int i, int n){ int j; if (i == n)printf("%s\n", str); else {for (j = i; j <= n; j++){swap((str+i), (str+j));permute(str, i+1, n);swap((str+i), (str+j)); //回溯} }}/* 测试 */int main(){ char str[] = "ABCD"; int len = sizeof(str)/sizeof(char) – 2; permute(str, 0, len); getchar(); return 0;}
（4）贪心算法
（1）贪心算法的基本思路： 1.建立数学模型来描述问题。 2.把求解的问题分成若干个子问题。 3.对每一子问题求解，得到子问题的局部最优解。 4.把子问题的解局部最优解合成原来解问题的一个解。
（2）贪心算法适用的问题
人若软弱就是自己最大的敌人
