回溯算法 和 贪心算法(全排列)

一:简介

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

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

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

郑重声明:本站内容如果来自互联网及其他传播媒体,其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享,并不代表本站赞同其观点和对其真实性负责,也不构成任何其他建议。