首页 > 编程语言 >回溯函数(算法)杂谈 -----可主动控制撤回逻辑处理的递归函数

回溯函数(算法)杂谈 -----可主动控制撤回逻辑处理的递归函数

时间:2024-08-10 11:58:53浏览次数:17  
标签:return 递归函数 int 杂谈 vector ----- result 回溯 path

概述

回溯,对接触了算法的人而言,并不陌生,其实严谨地说回溯函数就是递归函数,只不过在使用上,人们将它的一些细节抽离出来,进而演化出了所谓的回溯,在算法导论中,与其相关的被称为“回溯搜索算法”。

回溯本质是递归的副产物,只要有递归调用就会有回溯。

回溯法也经常和二叉树或N叉树遍历,深度优先搜索混在一起,因为这两种方式的简单实现都是用了递归(当然可以使用数据结构的栈模拟递归,来设计搜索遍历算法)。

接下来的杂谈中,大家也可以隐隐约约感觉,回溯就是在暴力搜索,只是它的优势在于,你可以在有限的函数操作里实现庞大搜索空间的操作,而不用设计冗余或重复的代码结构。

回溯和递归有个不同点就是回溯,它有一个显性逆回的步骤  (撤销本次处理的结果)

设计回溯函数的核心:1. 处理局部结果   2. 递归   3. 回溯 (撤回处理结果)

有几个要领  1. 在递归函数中对关键形参变量的调整 

                    2. 回溯对于待处理对象,大部分使用引用传参

N叉树情景

N叉树一般可以由很多问题抽象而来,比如,给定⼀个⽆重复元素的数组 candidates 和⼀个⽬标数 target ,找出 candidates 中所有可以使数字和为 target 的组合。

这里我介绍网上一个算法大咖的回溯模板, 利用循环进行递归调用很好地解决这类问题

回溯⼀般是在集合中递归搜索,集合的大小构成了树的宽度,递归的深度构成的树的深度

for循环可以理解是横向遍历,backtracking(递归)就是纵向遍历

根据不同的需求,可以纵横地扫描全局各结果的可能性

void backtracking(参数) {
    if (终⽌条件) {
        存放结果;
        return;    
    }
    
    //index用以控制横向的搜索空间
    for (index = 0; index < 总集合宽度 ; index++) {
        1. 处理节点; (处理外部需要收集结果的容器)
        
        2. backtracking(路径,index+1); // 递归
        

        3. 回溯
    }
}

在上面所提及的问题中,可以给出下面的解法

class Solution {
    private:
        vector<int> path;
        vector<vector<int>> result;

        void backingtrack(vector<int>& candidates, int sum, int target, int startindex){
            if(sum == target ){ 
                result.push_back(path);
                return;
            }

            if(target < sum)
                return;

            //定义startindex 可以根据 i 来 界定 回溯去重作用
            for(int i = startindex; i < candidates.size(); ++i){
                    sum += candidates[i];           //处理
                    path.push_back(candidates[i]);  //处理
                    backingtrack(candidates, sum, target, i);  //i != i+1 表示可以重复读取当前的数
                    path.pop_back();       //回溯
                    sum -= candidates[i];  //回溯
            }
        }
public:
    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        path.clear();
        result.clear();

        backingtrack(candidates, 0, target, 0);
        return result;
    }
};

二叉树情景

在LeetCode上 有这样一个问题,数字为0~9之间

求根节点到叶节点数字之和,如下为两个示例及一种回溯的解法

 

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */

class Solution {
    private:
        int countSum(vector<int>& ve){
            int len = ve.size();
            int res = 0;

            for(int i = 0; i <len; i++){
                res += ve[i];
                if(i == len -1)
                    break;
                res *= 10;
            }

            //cout << res << endl;
            return res;
        }

        void Proback(TreeNode* root, vector<int>& ve, int &sum){
            if(root == nullptr)
                return;    //终止条件

            ve.push_back(root->val);  //处理结果
            if(root->left == nullptr && root->right == nullptr){
                sum += countSum(ve);  //处理结果  (可以提前终止 直接return)
                //return ;
            }

            if(root->left){
                Proback(root->left, ve, sum); //递归
                ve.pop_back();    //回溯
            }
            
            if(root->right){
                Proback(root->right, ve, sum);  //递归
                ve.pop_back();     //回溯
            }
            
            return;
        }
public:
    int sumNumbers(TreeNode* root) {
        vector<int> v;
        int sum = 0;
        Proback(root, v, sum);

        return sum;
    }
};

当然也可以使用二维数组 收集路径的总集,一维数组收集路径

class Solution {
    private:
        vector<vector<int>> ve;
        vector<int> path;

        void preorder(TreeNode* root){
            if(root == nullptr)
                return;

            path.push_back(root->val);  //处理
            if(root->left == nullptr && root->right == nullptr)
                ve.push_back(path);     //处理

            if(root->left){
                preorder(root->left);
                path.pop_back();   //回溯
            }

            if(root->right){
                preorder(root->right);
                path.pop_back();   //回溯
            }
        }
public:
    int sumNumbers(TreeNode* root) {
        preorder(root);

        int res = 0;

        for(int i=0; i < ve.size(); i++){
            int len = ve[i].size();       //path数组的长度
            int sum = 0;

            //计数
            for(int j = 0; j < len; j++){
                int tmp = ve[i][j] * pow(10, len-j-1);
                sum += tmp;
            }

            res += sum;
        }

        return res;
    }
};

回溯的使用也存在一些技巧和花样,比如下面两种实现方式,本质都是一样的,一个是通过主动调用而进行回溯操作(显式),一个是通过调整形参进而进行自动回溯(隐式)。

显式回溯

递归函数里主动地回溯

class Solution {
    private:
        string s;
        vector<string> res;
        unordered_map<int, string> index2string = {
            {0, ""}, {1, ""}, {2, "abc"}, {3, "def"}, {4, "ghi"}, {5, "jkl"}, {6, "mno"},
            {7, "pqrs"}, {8, "tuv"}, {9, "wxyz"}
        }; 

        void backtracking(string digits, int index){
            if(index == digits.size()){
                res.push_back(s);
                return;
            }

            int digit = (int)(digits[index] - '0');    // - '0' ASCII 差值 获得数值
            string letters = index2string[digit];
            
            for(int i = 0; i < letters.size(); ++i){
                s.push_back(letters[i]);              //处理
                backtracking(digits, index+1);        //递归
                s.pop_back();                         //回溯
            }
        }
public:
    vector<string> letterCombinations(string digits) {
        res.clear();
        s.clear();

        if(digits.size() == 0)
            return res;

        backtracking(digits, 0);
        return res;
    }
};

隐式回溯

递归函数里被动地回溯

把回溯隐藏在递归参数里,把参数写进递归函数 == 自动回溯。下面举个抽象的例子

(开过车的都知道,手动挡的车,比起自动挡而言,在切换变速杆时,多了离合器的控制,而这些其实在自动挡车,有汽车控制器帮你完成了)

class Solution {
    private:
        string s;
        vector<string> res;
        unordered_map<int, string> index2string = {
            {0, ""}, {1, ""}, {2, "abc"}, {3, "def"}, {4, "ghi"}, {5, "jkl"}, {6, "mno"},
            {7, "pqrs"}, {8, "tuv"}, {9, "wxyz"}
        }; 

        void backtracking(string digits, int index, const string& s){
            if(index == digits.size()){
                res.push_back(s);
                return;
            }

            int digit = (int)(digits[index] - '0');    // - '0' ASCII 差值 获得数值
            string letters = index2string[digit];
            
            for(int i = 0; i < letters.size(); ++i){
                
                backtracking(digits, index+1, s+letters[i]);        //处理+递归+回溯
                
            }
        }
public:
    vector<string> letterCombinations(string digits) {
        res.clear();
        s.clear();

        if(digits.size() == 0)
            return res;

        backtracking(digits, 0, "");
        return res;
    }
};

应用场景

这里以算法题中几个经典问题来谈谈其巧妙的应用,尽量以显式回溯来阐述。

排列组合问题

这里比较取巧地使用了交换的思想来处理排列,排列是有序的,使用N叉树思想,在循环中嵌套递归,并且每层都是从0开始搜索而不是startIndex。

class Solution {
    private:
        vector<vector<int>> res;
        void backTrack(vector<vector<int>>& res, vector<int>& out, int cur, int len){
            if(cur == len){
                res.emplace_back(out);
                return;
            }

            for(int i = cur; i < out.size(); ++i){
                swap(out[cur], out[i]);            //处理
                backTrack(res, out, cur+1, len);   //递归
                swap(out[cur], out[i]);            //回溯
            }
        }
public:
    vector<vector<int>> permute(vector<int>& nums) {
        backTrack(res, nums, 0, nums.size()-1);

        return res;
    }
};

不同于排列问题,组合是无序的,仍然是利用N叉树思想,用for循环嵌套递归来控制搜索的数量,遍历所有结果。

class Solution {
    private:
        vector<int> path;
        vector<vector<int>> result;
        void Backtracking(int n, int k, int startindex){
            if(path.size() == k){
                result.push_back(path);
                return;     //终止条件
            }

            for(int i = startindex; i <= n; i++){   // 每次从startindex开始
                path.push_back(i);          //处理结果
                Backtracking(n, k, i+1);    //递归
                path.pop_back();            //回溯
            }
    }
    public:
        vector<vector<int>> combine(int n, int k) {

            /*第一层中 [1, n-k+1]   进入下一层;
             右边界扩充  [startindex, n-k+1 + path.size()]
            */

            path.clear();
            result.clear();

            Backtracking(n, k, 1);
            return result;
        }
};

切割子集问题

类似于排列组合问题,但是在处理结果上进行了一些调整,在处理中引入了逻辑判断条件,后续的数独问题也是引入了逻辑判断条件,但是更加复杂。

切割要点:1.模拟切割线  2.递归终止 3.在递归循环中截取子串   4.判断回文

class Solution {
    private:
        bool ispartition(const string& s, int start, int end){
            for(int i = start, j = end; i < j; i++, j--){
                if(s[i] != s[j])
                    return false;
            }

            return true;
        }

        vector<string> path;
        vector<vector<string>> result;

        /*
            startindex 是搜索的起始位置
            for 循环是重新一条N叉树的分支, 递归是深度搜索
        */ 
        void backtracing(string& s, int startindex){
            if(startindex >= s.size()){
                result.push_back(path);
                return;     //终止条件
            }

            for(int i = startindex; i < s.size(); ++i){
                if(ispartition(s, startindex, i)){             //处理
                    string str = s.substr(startindex, i-startindex+1);
                    path.push_back(str);
                }else{
                    continue;
                }

                backtracing(s, i+1);   //递归 ;index+1 表示不重复搜索
                path.pop_back();       //回溯

            }
        }

public:
    vector<vector<string>> partition(string s) {
        path.clear();
        result.clear();

        backtracing(s, 0);

        return result;
    }
};

子集的要点:

子集问题是在N叉树形结构中要收集所有节点的结果,而组合问题是收集叶子节点的结果

就是边递归边存值的问题,for循环表示横向,每一层都递增一个可能的结果。

class Solution {
    private:
        vector<int> path;
        vector<vector<int>> result;

        void backtracing(vector<int>& nums, int startindex){
            if(startindex > nums.size())
                return;   //终止条件

            for(int i = startindex; i < nums.size(); ++i){
                path.push_back(nums[i]);     //处理
                result.push_back(path);      //每次都要存结果,每一层的不同结果
                backtracing(nums, i+1);      //递归;index去重
                path.pop_back();             //回溯

            }

        }
public:
    vector<vector<int>> subsets(vector<int>& nums) {
        result.clear();
        path.clear();

        backtracing(nums, 0);
        result.push_back({});  //单独处理空集,题目有要求空集也算上
        return result;
    }
};

棋盘数独问题

这类问题,就是叠加了多层循环嵌套的递归了,可能嵌套在判断条件,可能嵌套在搜索条件,不再像前面两种应用问题里的,单独一个循环可以考虑充分。可以想象为,每个节点都是一个棋盘或一局数独矩阵,而在前面两类问题上,每一个节点,仅仅只是一个数组

棋盘,抽象成二维矩阵,矩阵中的长既是N叉树的树形结构中每一个节点的棋盘长度,又是N叉树的高度;矩阵中的宽就是N叉树的树形结构中每一个节点的棋盘宽度。

以N皇后为例,这是嵌套在判断条件里的。

棋盘的宽度就是for循环的长度,递归的深度就是棋盘的高度,只要搜索到了树的叶子节点,说明就找到了皇后们的位置了,然后收集合理的结果。

class Solution {
    private:
        vector<vector<string>> result; //3 dim
        vector<string> path;
        

        bool isvalid(int row, int col, vector<string>& path, int n){

            //col
            for(int i = 0; i < row; ++i){
                if(path[i][col] == 'Q') return false;
            }

            //45
            for(int i = row-1, j =col -1; i >=0 && j >= 0; i--, j--){
                if(path[i][j] == 'Q') return false;
            }

            //135
            for(int i = row -1, j = col + 1; i>= 0 && j < n; i--, j++){
                if(path[i][j] == 'Q') return false;
            }

            return true;

        }

        void backtracing(int n, int row){
            if(row == n){
                result.push_back(path);
                return;
            }

            // 取数 ; for 循环的 下一次循环
            for(int col = 0; col < n; col++){
                if(isvalid(row, col, path, n)){  //嵌套判断条件
                    path[row][col] = 'Q';     //处理
                    backtracing(n, row+1);    //递归
                    path[row][col] = '.';     //回溯
                }
            }
        }
        

public:
    vector<vector<string>> solveNQueens(int n) {
        result.clear();
        path = vector<string>(n , string(n, '.'));

        backtracing(n, 0);

        return result;
    }
};

数独,不同于N皇后,每一行每一列都只有一个有效位置的逻辑(局部有效进而全局有效),在递归过程(N皇后问题是因为每一行每一列只放一个皇后,只需要一层for循环遍历一行,递归来遍历列,把逻辑判断嵌套在判断条件里,然后一行一列确定皇后的唯一位置),数独中棋盘的每一个位置都要放一个数字(多重局部有效进而全局有效),并检查数字是否合法,解数独的树形结构要比N皇后更杂,更宽,更深,不再是简单的一行或列出现一个。

而且在棋盘的基础上,抽象了N叉树节点的棋盘大小就是9*9的,因此需要进一步拓展思维,用常量来设置嵌套在判断条件,并同时用常量设置嵌套在搜索条件,因为此刻棋盘固定,最终为三维递归

class Solution {
    private:
        
        bool isvalid(int row, int col, char val, vector<vector<char>>& result){

            //row
            for(int i =0; i < 9; ++i){
                if(result[row][i] == val)
                    return false;
            }

            //col
            for(int i = 0; i < 9; ++i){
                if(result[i][col] == val)
                    return false;
            }

            //3*3
            int startrow = (row / 3) * 3;
            int startcol = (col / 3) * 3;
            for(int i = startrow; i < startrow + 3; ++i){
                for(int j = startcol; j < startcol + 3; ++j){
                    if(result[i][j] == val)
                        return false;
                }
            }

            return true;
        }

        // 搜索单条路径
        // 两层for循环刻画棋盘
        bool backtracing(vector<vector<char>>& result){
            for(int i = 0; i < result.size(); ++i){
                for(int j = 0; j < result[0].size(); ++j){
                    if(result[i][j] == '.'){
                        // for as char
                        for(char k = '1'; k <= '9'; ++k){
                            if(isvalid(i, j, k, result)){              //嵌套判断条件
                                result[i][j] = k;                      //处理
                                if(backtracing(result)) return true;   //递归
                                result[i][j] = '.';                    //回溯
                            }
                        }

                        return false;
                    }
                }
            }

            return true;
        }
public:
    void solveSudoku(vector<vector<char>>& board) {

        backtracing(board);

    }
};

拓展应用

其实回溯的花样远不止本文所总结的这些,它可以和很多问题进行杂糅,并且在处理上有更灵活的做法,比如经典的迷宫游戏问题,本文杂谈就简单地归纳和个人理解的可能有误,如果大家发现问题还请指正下。

算法的种类和应用千千万,需要自行沉淀去悟出深意,感兴趣的读者可以去搜索了解哈。

完结撒花!!!!!!!!!

标签:return,递归函数,int,杂谈,vector,-----,result,回溯,path
From: https://blog.csdn.net/weixin_56228133/article/details/140994362

相关文章

  • C语言问答进阶--2、C语言简介及基本的输入输出函数
    C语言简介Q:您好,能大体介绍下C语言吗?A:当然可以。C语言是一种计算机语言,它主要被用在系统编程里,可以说,C语言的产生就和操作系统的编写密不可分。【C语言简要历史】1978年由美国电话电报公司(AT&T)的贝尔实验室正式发表了C语言。同时由B.W.Kernighan和D.M.Ritchie合著了著......
  • 2-SAT 学习笔记
    2-SAT用于求解布尔方程组,其中每个方程最多含有两个变量,方程的形式为\((a∨b)=1\),即式子\(a\)为真或式子\(b\)为真。求解的方法是根据逻辑关系式建图,然后求强联通子图,每一个强联通子图的答案都是一样的。建图:这里以模版题为例:题意:给定若干个需要满足的条件,其形式为\(a,1......
  • bat cmd javaw -jar
    rem使用者应根据自身平台编码自行转换防止乱码例如win使用gbk编码@echooffchcp65001remjar平级目录setAppName=medicare-down.jarsetpathx=%CD%setpathxx=%pathx%\Java\jdk1.8.0_101\::echo%pathxx%set"JAVA_HOME=%pathxx%::set"CLASSPATH=%JAVA_HOME%\lib\dt.jar;......
  • 学生Java学习路程-6
    ok,到了一周一次的总结时刻,我大致会有下面几个方面的论述:1.这周学习了Java的那些东西2.这周遇到了什么苦难3.未来是否需要改进方法等几个方面阐述我的学习路程。复习面向对象数组数组的三种初始化方法:默认,静态,动态引用类型Man放入数组中的测试代码数组的拷贝使用规范使......
  • AP2402 5-100V 1.5A 外围简单DC-DC降压恒流驱动IC 手电筒与汽车灯方案
    产品描述AP2402是一款PWM工作模式,高效率、外围简单、内置功率管,适用于5-100V输入的高精度降压LED恒流驱动芯片。输出最大功率可达15W,最大电流1.5A。AP2402可实现三段功能切换,通过MODE1/2/3切换三种功能模式:全亮,半亮,爆闪。AP2402工作频率固定在150KHZ左右,同时内置抖......
  • Linux服务管理-Nginx进阶
    通常会通过rewrite将用户的80请求转化为443请求,也就意味着Nginx需要去做虚拟主机,一个80端口的虚拟主机和一个443端口的虚拟主机,当访问80端口的虚拟主机时返回一个信息让用户去访问443端口的虚拟主机。......
  • RPC框架实现-1-总体把握
    文章目录如何去实现RPC框架,我的思路从RPC的角度来看从框架实现的角度来看总结如何去实现RPC框架,我的思路要实现RPC框架,作为一个没写过类似东西的小白。要考虑两点。什么是RPC,原理与实现怎么实现一个框架,如我们Java中的Spring,网络通信框架Netty等从这两个角度来考......
  • 塔子哥的美食节-阿里淘天2024笔试(codefun2000)
    题目链接塔子哥的美食节-阿里淘天2024笔试(codefun2000)题目内容塔子哥是一位美食评论家,他最近参加了一个美食节,品尝了n种不同的美食,每种美食都有一个特定的人气值。现在,塔子哥想写一篇关于这次美食节的文章,他打算挑选出k种美食,使得文章中能够突出一种特别受欢迎的......
  • Linguistics-English-高频词辩析 + 常用句式:keep me posted(有消息通知我 )
    高频词辨析someVSany:some:肯定句式,ihavesomepen.caniborrowsomepen?any:疑问/否定句式idon'thaveanypen.doyouhaveanypen?fewVSafew,littleVSalittlefew+可数名词复数:很少(几乎没有),表"否定".afew+可数名词复......
  • 08-08 题解
    08-08题解地址A-CF1420Eluogu翻译更正ifhegivesnomorethatkorders对于至多k次操作,题面没有翻译出来思路怎么算贡献?贡献(被保护)出现在「处在任意两个不同的0的连续段的守卫」之间,而处于同一连续段的守卫之间没有贡献设一共\(cnt\)个\(0\),每个连续......