首页 > 编程语言 >”回溯算法“框架及练习题

”回溯算法“框架及练习题

时间:2024-11-01 14:41:48浏览次数:3  
标签:练习题 LinkedList nums track backtrack 选择 算法 回溯

@

目录

一、回溯算法是什么?

结论:回溯 = 穷举
解决一个回溯问题,实际上就是一个决策树的遍历过程

  1. 路径:就是已经做出的选择
  2. 选择列表:就是你当前可以做出的选择
  3. 结束条件:就是base case条件,也就是临界条件

二、框架如下:

框架如下:

result = []
def backtrack(路径,选择列表) {
	if 满足结束条件 : 
		result.add(路径)
		return
	for 选择 in 选择列表
		做选择
		backtrack(路径,选择列表)
		撤销选择	
}

举例:经典回溯算法问题:全排列问题

public class TestNode {
	private static List<List<Integer>> res = new LinkedList<>();

	public static void main(String[] args){
			//问题2.1:全排列问题
	        permute(new int[]{1,2,3});
	        res.stream().forEach(item -> System.out.print(item + " "));
	}	
	/**
     * 问题2.1:全排列问题,输入一个数组,输出所有全排列顺序
     *      框架:路径:记录在track中
     *           选择列表:nums中不存在于track的那些元素
     *           结束条件:nums中元素全部在track中出现
     * @param nums 数组
     * @return list
     */
    public static List<List<Integer>> permute(int[] nums) {
        //记录“路径”
        LinkedList<Integer> track = new LinkedList<>();
        backtrack(nums, track);
        return res;
    }
    public static void backtrack(int[] nums, LinkedList<Integer> track) {
        //base case
        if (track.size() == nums.length) {
            res.add(new LinkedList<>(track));
            return;
        }
        for (int i = 0; i < nums.length; i++) {
            //排除不合法的选择
            if (track.contains(nums[i])) continue;
            //做选择
            track.add(nums[i]);
            //进入下一层决策树
            backtrack(nums, track);
            //取消选择
            track.removeLast();
        }
    }

输出结果

[1, 2, 3] [1, 3, 2] [2, 1, 3] [2, 3, 1] [3, 1, 2] [3, 2, 1] 

本人其他文章链接

1.单链表题+数组题(快慢指针和左右指针)

2.BFS(Breath First Search 广度优先搜索)

3.”回溯算法“框架及练习题

4.JAVA 二叉树面试题

标签:练习题,LinkedList,nums,track,backtrack,选择,算法,回溯
From: https://www.cnblogs.com/bigcat26/p/18520211

相关文章

  • 算法设计与分析中的几个核心算法策略:动态规划、贪心算法、回溯算法和分治算法
    这些题目主要考察的是算法设计与分析中的几个核心算法策略:动态规划、贪心算法、回溯算法和分治算法。下面我将分别介绍这些知识点,并解析题目的详细解答过程。1.动态规划(DynamicProgramming,DP)知识点介绍:动态规划是一种通过把原问题分解为相对简单的子问题的方式来求解复杂问......
  • 书籍-《基于启发式卡尔曼算法解决优化问题》
    书籍:SolvingOptimizationProblemswiththeHeuristicKalmanAlgorithm:NewStochasticMethods作者:RosarioToscano出版:Springer编辑:陈萍萍的公主@一点人工一点智能01书籍介绍本书专注于简单且易用的设计策略,以解决在多个工程设计领域中出现的复杂工程问题,特别是非凸优化问题......
  • GBDT 算法的原理推导
    GBDT的全称为梯度提升决策树(gradientboostingdecisiontree),其基模型(弱分类器)为CART决策树,针对分类问题的基模型为二叉分类树,对应梯度提升模型就叫GBDT;针对回归问题的基模型为二叉回归树,对应的梯度提升模型叫做GBRT(gradientboostingregressiontree)。我们先来用一个通俗......
  • 聚类算法——Kernel K-Means (核K-均值聚类)聚类算法详解
    KernelK-Means聚类算法详解目录引言聚类算法概述K-Means算法回顾KernelK-Means算法概述KernelK-Means的工作原理核心思想与标准K-Means的区别KernelK-Means的算法步骤初始化计算核矩阵簇分配质心更新迭代与收敛数学基础目标函数核技巧(KernelTrick)特征映......
  • 聚类算法——Spherical K-Means聚类算法详解
    SphericalK-Means聚类算法详解聚类分析是数据挖掘和机器学习中的重要任务之一,其目的是将数据集中的对象分组,使得同一组内的对象相似度高,而不同组之间的对象相似度低。K-Means聚类算法是最经典和最广泛使用的聚类算法之一。然而,K-Means算法在处理高维稀疏数据或基于余弦相......
  • 【粒子群优化算法】基于Schwefel‘s P2.21函数的PSO算法变体性能分析(附完整算法Python
    基于Schwefel'sP2.21函数的PSO算法变体性能分析(附完整算法Python代码)摘要1.引言1.1研究目的2.算法与测试函数2.1Schwefel'sP2.21函数2.2PSO算法变体2.2.1标准PSO(SPSO)2.2.2自适应PSO(APSO)2.2.3改进的带变异PSO(IPSOM)2.2.4混合PSO(HPSO)3.实验设计3.......
  • 【Matlab算法】基于MATLAB实现时间序列预测(附MATLAB完整代码)
    基于MATLAB实现时间序列预测前言正文代码实现结果图结果说明总结前言时间序列预测是许多实际应用中的重要任务,涉及领域包括经济、金融、气象等。其中,自回归集成移动平均(ARIMA)模型是一种广泛使用的时间序列预测方法,因其简单有效而备受青睐。在本文中,......
  • 数据结构与算法(二叉树)
    鲸饮未吞海,剑气已横秋。 前言  这是我学习数据结构的第五份笔记,有关二叉树的知识。后期我会继续将数据结构知识的笔记补全。 上一期笔记有栈与列队,没看过的同学可以去看看:有关栈与列队的笔记https://blog.csdn.net/hsy1603914691/article/details/143064674?spm=10......
  • 02链表算法/代码随想录
    前几天忙比赛,算法停了三天,继续开刷,不能停!!二、链表2.1删除链表中的元素两种方案无哨头:要删除节点的前一个结点指向删除节点的指向节点。头节点需要单独定义有哨头:头节点不需要单独定义实战力扣203/***Definitionforsingly-linkedlist.*publicclassLis......
  • 【SSL-RL】自监督强化学习:Plan2Explore算法
            ......