回溯算法 和 贪心算法（全排列）

一：简介

（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了。

（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）贪心算法适用的问题

      贪心策略适用的前提是：局部最优策略能导致产生全局最优解。
    实际上，贪心算法适用的情况很少。一般，对一个问题分析是否适用于贪心算法，可以先选择该问题下的几个实际数据进行分析，就可做出判断。

（3）贪心算法的实现框架
    从问题的某一初始解出发；
    while （能朝给定总目标前进一步）
    { 
          利用可行的决策，求出可行解的一个解元素；
    }
    由所有解元素组合成问题的一个可行解；
  
（4）贪心策略的选择
     因为用贪心算法只能通过解局部最优解的策略来达到全局最优解，因此，一定要注意判断问题是否适合采用贪心算法策略，找到的解是否一定是问题的最优解。