首页 > 编程语言 >回溯算法模板

回溯算法模板

时间:2024-02-15 11:45:18浏览次数:29  
标签:backtrack res 选择 算法 回溯 path 模板

回溯算法的模板通常包含递归函数和回溯过程。以下是一个通用的回溯算法模板:

def backtrack(start, path, other_parameters):
    # 满足结束条件时,将当前路径加入结果
    if satisfies_end_condition:
        result.append(path[:])
        return

    # 从start开始遍历可能的选择
    for i in range(start, len(choices)):
        # 做出选择
        path.append(choices[i])

        # 递归调用,处理下一层决策树
        backtrack(i, path, other_parameters)

        # 撤销选择,进行回溯
        path.pop()

# 主函数
def main_function(other_parameters):
    result = []
    choices = [1, 2, 3]  # 替换成实际问题的选择集合
    backtrack(0, [], other_parameters)
    return result

在这个模板中,backtrack函数是回溯的核心部分,负责递归地处理决策树。start表示当前考虑的位置,path表示当前的路径,other_parameters表示可能的其他参数。结束条件通常是根据问题的要求定义的。
这个模板可以根据具体问题进行调整和扩展,主要思想是通过递归不断尝试不同的选择,并在满足结束条件时记录结果,然后通过回溯的方式撤销选择,进行下一轮的尝试。

简化模板
1:

res = []

def backtrack(remaining_area, res, path):
    if remaining_area meets end condition:
        res.add(path.copy()) # 深度拷贝
        return
    for choice in current_possible_choices of remaining_area:
        if choice meets requirement:
            path.add(choice)
            backtrack(new_remaining_area, res, path)
            path.pop()

backtrack 的含义是:在未探索区域中寻找所有到达结束条件的可能路径,其中 path 变量保存的是当前路径,res 变量保存的是所有搜索到的路径。因此,当「未探索区域满足结束条件」时,需要将 path 放入结果 res 中。
path.pop() 表示在编程实现中的一个必要步骤,因为我们始终只使用一个变量 path。因此,在添加一个选择并回溯之后,需要清除当前的选择,以防影响其他路径的搜索。

对于本题,要求将字符串分割成一系列回文子串,按照模板思路应该如下:
未探索区域:剩余未搜索的字符串 s;
结束条件:s 为空;
未探索区域当前可能的选择:每次可以选择 s 的 1 到 length 个字符,即 cur=s[0...i];
当前选择符合要求:cur 是回文字符串 isPalindrome(cur);
新的未探索区域:将剩余字符串 s[i+1...N] 作为新的未搜索区域。

2:

def backtrack(新区域, res, path):
    if 结束:# 一般是最小值最大值
        res.add(path) # 
        return
    for 选择 in 新区域:
        if 符合要求:
            path.add(当前选择)
            backtrack(新区域, res, path)
            path.pop()

例子:leetcode 131题 https://leetcode.cn/problems/palindrome-partitioning/description/

标签:backtrack,res,选择,算法,回溯,path,模板
From: https://www.cnblogs.com/taixian/p/18016096

相关文章

  • 字符串KMP算法详解
    引入字符串kmp算法用于解决字符串匹配的问题:给出两个字符串\(s_1\)和\(s_2\),若\(s_1\)的区间\([l,r]\)子串与\(s_2\)完全相同,则称\(s_2\)在\(s_1\)中出现了,其出现位置为\(l\)。现在请你求出\(s_2\)在\(s_1\)中所有出现的位置。很显然,我们能够想到暴力求......
  • poj 2676 Sudoku(DFS+回溯+剪枝)
    2676--Sudoku(poj.org)#include<iostream>#include<cstring>usingnamespacestd;intt,row[10][10],col[10][10],grid[10][10],map[10][10];boolDFS(intr,intc){if(r==10)returntrue;boolflag=false;if(map[r][c]){if(c=......
  • Tarjan 算法
    part1:离线求\(lca\)将走过的点且未回溯的标记为\(1\),已回溯的标记为\(2\),未访问标记为\(0\)把对于一点\(x\)的询问\(y\)存进相应的\(vector\),当回溯时判断如果询问的点标记为\(2\),则\(lca\)为询问的点\(y\)到根的路径上最早标记为\(1\)的点但直接找复杂度不对......
  • 使用lanczos算法进行的预处理共轭梯度算法(Preconditioned Conjugate Gradients Metho
    构造预处理矩阵M(对称正定)下图来自:预处理共轭梯度法(1)......
  • 模板
    01.模版的概念(了解)1.函数或类是通用,但是里面的数据类型的多种状态2.模版有:函数和类02.函数模版(重点)1.什么是函数模版函数模板,实际上是建立一个通用函数,其函数类型和形参类型不具体制定,用一个虚拟的类型来代表。这个通用函数就成为函数模板2.怎么编写函数模版//T代表泛型的......
  • 代码随想录算法训练营第十七天| 110.平衡二叉树 257. 二叉树的所有路径 404.左叶
    110.平衡二叉树 题目链接:110.平衡二叉树-力扣(LeetCode)思路:判断平衡二叉树,就是判断两个子树的高度差,继而问题转化为了如何求子树的高度——后序遍历(主要卡在了这里)。递归函数返回的是树的高度,同时用-1来表示退出递归(一开始想着用bool型作为返回值,发现函数不好设计)。同时要关......
  • URL编码算法:解决特殊字符在URL中的烦恼
    引言:URL编码算法是一种将URL中的特殊字符转换为特定格式的编码方式。它在网络传输中起到了保护数据安全与完整性的重要作用。本文将深入探讨URL编码算法的优点与缺点,并介绍它在Web开发、网络安全等方面的应用。URL编码解码|一个覆盖广泛主题工具的高效在线平台(amd794.com)h......
  • 【算法】【动态规划】钢条切割
    1 题目来自算法导论的一道经典题目:2 解答动态规划原理虽然已经用动态规划方法解决了上面问题,但是大家可能还跟我一样并不知道什么时候要用到动态规划。总结一下上面的斐波拉契数列和钢条切割问题,发现两个问题都涉及到了重叠子问题,和最优子结构。①最优子结构用动态规......
  • 预处理共轭梯度算法(Preconditioned Conjugate Gradients Method)
    预处理共轭梯度算法(PreconditionedConjugateGradientsMethod)给出百度百科上的解释:预处理共轭梯度法预处理共轭梯度法是。不必预先估计参数等特点。共轭梯度法近年来在求解大型稀疏方程组中取得了较好的成效。理论上普通的共扼梯度法对于对称超正定方程,只要迭代步数达到......
  • leetcode——数组算法——前缀和构建和应用
    leetcode——数组算法——前缀和构建和应用前缀和技巧适用于快速、频繁地计算一个索引区间内的元素之和303.区域和检索-数组不可变比如leetcode303.区域和(检索-数组不可变)题目介绍:给定一个整数数组nums,处理以下类型的多个查询:计算索引left和right(包含left......