“回溯算法”框架及练习题
大模型开发/技术交流
- LLM
11月19日204看过
一、回溯算法是什么？
结论：==回溯 = 穷举== 解决一个回溯问题，实际上就是一个决策树的遍历过程
-
路径：就是已经做出的选择
-
选择列表：就是你当前可以做出的选择
-
结束条件：就是base case条件，也就是临界条件
二、框架如下：
==框架如下：==
result = []def backtrack(路径，选择列表) {if 满足结束条件 :result.add(路径)returnfor 选择 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 caseif (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]
————————————————
版权声明：本文为稀土掘金博主「刘大猫26」的原创文章
原文链接：https://juejin.cn/post/7432098784928661542
如有侵权，请联系千帆社区进行删除
评论
