java回溯_java实现回溯算法
最近有在leetcode上⾯做算法题，已经遇到了两道回溯算法的题⽬，感觉⼀点思路都没有，现决定将java如何实现回溯算法做⼀次总结。
⼀、什么叫做回溯算法
(摘抄于百度百科)
回溯算法实际上⼀个类似枚举的搜索尝试过程，主要是在搜索尝试过程中寻问题的解，当发现已不满⾜求解条件时，就“回溯”返回，尝试别的路径。回溯法是⼀种选优搜索法，按选优条件向前搜索，以达到⽬标。但当探索到某⼀步时，发现原先选择并不优或达不到⽬标，就退回⼀步重新选择，这种⾛不通就退回再⾛的技术为回溯法，⽽满⾜回溯条件的某个状态的点称为“回溯点”。许多复杂的，规模较⼤的问题都可以使⽤回溯法，有“通⽤解题⽅法”的美称。
(摘抄于他⼈博客)
在包含问题的所有解的解空间树中，按照深度优先搜索的策略，从根结点出发深度探索解空间树。当探索到某⼀结点时，要先判断该结点是否包含问题的解，如果包含，就从该结点出发继续探索下去，如果该结点不包含问题的解，则逐层向其祖先结点回溯。(其实回溯法就是对隐式图的深度优先搜索算法)。
若⽤回溯法求问题的所有解时，要回溯到根，且根结点的所有可⾏的⼦树都要已被搜索遍才结束。 ⽽若使⽤回溯法求任⼀个解时，只要搜索到问题的⼀个解就可以结束。
⼆、如何使⽤回溯算法
回溯我认为也就是⼀种递归，有以下四个参数，当然不⼀定是我所举例的类型，要看题⽬⽽定
⼀个全局变量集合保存所有满⾜条件的答案，举例：List> list
⼀个集合保存⼀个满⾜条件的答案，举例：List tempList
算法问题给所给的输⼊条件，这个可能是⼀个字符串，也可能是⼀个数组
附加参数(可有可⽆，视题⽬⽽定)
下⾯具体以leetcode上的⼀道题⽬为例，这样能更好的理解
importjava.util.ArrayList;importjava.util.List;public classPermutations {//题⽬描述：Given a collection of distinct integers, return all possible permutations.(给定⼀组不同的整数，返回其所有的可能组合)
public List> permute(int[] nums) {//⼀个全局变量，⽤于保存所有集合
List> list = new ArrayList<>();//传⼊三个参数，没有附加参数
backtrack(list, new ArrayList<>(), nums);returnlist;
}private void backtrack(List> list, List tempList, int[] nums){//⼀个终结条件，也就是满⾜条件的时候
if(tempList.size() ==nums.length){//全局变量添加⼀个满⾜条件的集合
list.add(new ArrayList<>(tempList));
}else{for(int i = 0; i < nums.length; i++){ains(nums[i])) continue;//如果tempList没有包含nums[i]才添加
tempList.add(nums[i]);//递归调⽤，此时的tempList⼀直在变化，直到满⾜终结条件才结束
backtrack(list, tempList, nums);
System.out.println("tempList的内容:"+tempList+"-------"+"i的值:"+i);//它移除tempList最后⼀个元素的作⽤就是返回上⼀次调⽤时的数据，也就是希望返回之前的节点再去重新搜索满⾜条件。这样才能实现回溯
java技术介绍百度百科
}
}
}public static voidmain(String[] args){int[] nums={1,2,3};
(newPermutations()).permute(nums);
}
}
main⽅法测试，输出语句的结果显⽰如下，可以观察出回溯的过程
tempList的内容:[1, 2, 3]-------i的值:2
tempList的内容:[1, 2]-------i的值:1
tempList的内容:[1, 3, 2]-------i的值:1
tempList的内容:[1, 3]-------i的值:2
tempList的内容:[1]-------i的值:0
tempList的内容:[2, 1, 3]-------i的值:2
tempList的内容:[2, 1]-------i的值:0
tempList的内容:[2, 3, 1]-------i的值:0
tempList的内容:[2, 3]-------i的值:2
tempList的内容:[2]-------i的值:1
tempList的内容:[3, 1, 2]-------i的值:1
tempList的内容:[3, 1]-------i的值:0
tempList的内容:[3, 2, 1]-------i的值:0
tempList的内容:[3, 2]-------i的值:1
tempList的内容:[3]-------i的值:2
我对这道题⽬的理解是从这个for循环的i=0开始就不断递归，然后在不断消除集合最末尾元素进⾏回溯，直到回溯完成。这样就产⽣了⾸位元素是1的各种情况。以此类推，之后再开始for循环i=1，产⽣⾸位元素是2的各种情况。
形象点就是⼀个根结点有1，2，3三个元素，第⼀次从1出发，寻最低端满⾜条件的结点，然后再返回上⼀个结点寻满⾜条件的结点，直到返回1，返回1之后再从2开始，以此类推。

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。