回溯java算法_聊聊算法——回溯算法
“遞歸只應(yīng)天上有，迭代還須在人間”，從這句話我們可以看出遞歸的精妙，確實(shí)厲害，遞歸是將問(wèn)題規(guī)模逐漸減小，
然后再反推回去，但本質(zhì)上是從最小的規(guī)模開(kāi)始，直到目標(biāo)值，思想就是數(shù)學(xué)歸納法，舉個(gè)例子，求階乘 N!=(N-1)！*N ，
而迭代是數(shù)學(xué)中的極限思想，利用前次的結(jié)果，逐漸靠近目標(biāo)值，迭代的過(guò)程中規(guī)模不變，舉例如For循環(huán)，直到終止條件。
遞歸的思想不復(fù)雜，但代碼理解就麻煩了，要理解一個(gè)斐波那契數(shù)組遞歸也不難，比如下面的回溯算法遞歸，for 循環(huán)里面
帶遞歸，看代碼是不是暈了？好，下面我們專門(mén)來(lái)聊聊這個(gè)框架！
作者原創(chuàng)文章，謝絕一切形式轉(zhuǎn)載，違者必究！
準(zhǔn)備：
Idea2019.03/JDK11.0.4
難度： 新手--戰(zhàn)士--老兵--大師
目標(biāo)：
回溯算法分析與應(yīng)用
1 回溯算法
先給出個(gè)回溯算法框架：
backtrack(路徑，選擇列表){
//結(jié)束條件
將中間結(jié)果加入結(jié)果集
for 選擇 in 選擇列表:
//做選擇，并將該選擇從選擇列表中移除
路徑.add(選擇)
backtrack(路徑，選擇列表)
//撤銷(xiāo)選擇
路徑.remove(選擇)
}
為了理解上述算法，回想一下，我前篇文章中有說(shuō)到，多路樹(shù)的遍歷算法框架：
private static class Node {
public int value;
public Node[] children;
}
public static void dfs(Node root){
if (root == null){
return;
}
// 前序遍歷位置，對(duì)node做點(diǎn)事情
for (Node child:children
) {
dfs(child);
}
// 后序遍歷位置，對(duì)node做點(diǎn)事情
}
如果去掉路徑增加/撤銷(xiāo)的邏輯，是不是和多路樹(shù)的遍歷算法框架一樣了呢？其實(shí)就是一個(gè)多路樹(shù)DFS的變種算法！
另外，雖然遞歸代碼的理解難度大，運(yùn)行時(shí)是棧實(shí)現(xiàn)，但看官不要掉進(jìn)了遞歸棧，否則就出不來(lái)了，如果試著用打斷
點(diǎn)逐行跟進(jìn)的辦法非要死磕，那對(duì)不起，估計(jì)三頓飯功夫也可能出不來(lái)，甚至我懷疑起自己的智商來(lái)，所以，理解遞歸，
核心就是抓住函數(shù)體來(lái)看，抽象的理解，只看懂 N 和 N-1 的轉(zhuǎn)移邏輯即可！不懂的先套用再說(shuō)，也不定哪天就靈感來(lái)了，
一下頓悟！
那就先上菜了！先是經(jīng)典回溯算法，代號(hào)A，我們要做個(gè)數(shù)組全排列，我看別人說(shuō)回溯算法也都是拿這個(gè)例子說(shuō)事，
我就落個(gè)俗套：
class Permutation {
// 排列組合算法
private static List> output = new LinkedList();
static List> permute( List nums, // 待排列數(shù)組
int start //起始位置
){
if (start == nums.size()){
output.add(new ArrayList<>(nums));
}
for (int i = start; i < nums.size(); i++) {
// 做選擇，交換元素位置
Collections.swap(nums, start, i);
// 遞歸，縮小規(guī)模
permute( nums,start +1);
// 撤銷(xiāo)選擇，回溯，即恢復(fù)到原狀態(tài),
Collections.swap(nums, start, i);
}
return output;
}
// 測(cè)試
public static void main(String[] args) {
List nums = Arrays.asList(1,2,3,4);
List> lists = permute(nums,0);
lists.forEach(System.out::println);
}
}
代碼理解：數(shù)組 {1,2,3} 的全排列，我們馬上知道有{1,2,3},{1,3,2},{2,1,3},{2,3,1},{3,1,2},{3,2,1}排列，具體過(guò)程就是通過(guò)遞歸縮小規(guī)模，
做 {1,2,3} 排列，先做 {2,3} 排列，前面在加上 1 即可，繼續(xù)縮小，就是做 {3} 的排列。排列就是同一個(gè)位置把所有不同的數(shù)都放一次，
那么代碼實(shí)現(xiàn)上可使用交換元素法，比如首個(gè)位置和所有元素都交換一遍，不就是全部可能了嗎。這樣，首個(gè)位置所有可能就遍歷了
一遍，然后在遞歸完后，恢復(fù)(回溯)一下，就是說(shuō)每次交換都是某一個(gè)下標(biāo)位置，去交換其他所有元素。
再來(lái)個(gè)全排列的算法實(shí)現(xiàn)，代號(hào)B，也是使用回溯的思想：
public class Backtrack {
public static void main(String[] args) {
int[] nums = {1,2,3,4};
List track = new LinkedList<>();
List> res = backtrack(nums,track);
System.out.println(res);
}
// 存儲(chǔ)最終結(jié)果
private static List> result = new LinkedList<>();
// 路徑：記錄在 track 中
// 選擇列表：nums 中不存在于 track 的那些元素
// 結(jié)束條件：nums 中的元素全都在 track 中出現(xiàn)
private static List> backtrack(int[] nums,List track){
// 結(jié)束條件
if (track.size() == nums.length){
result.add(new LinkedList<>(track));
return null;
}
for (int i = 0; i < nums.length; i++) {
if (track.contains(nums[i]))
continue;
// 做選擇
track.add(nums[i]);
backtrack(nums,track);
// 撤銷(xiāo)選擇
track.remove(track.size()-1);
}
return result;
}
}
代碼解析：對(duì) {1,2,3} 做全排列，先將 List[0] 放入鏈表，如果鏈表中存在該元素，就忽略繼續(xù)，繼續(xù)放入List[0+1]，同樣的，
存在即忽略繼續(xù)，直到將List中所有元素，無(wú)重復(fù)的放入鏈表，這樣就完成了一次排列。這個(gè)算法的技巧，是利用了鏈表的
有序性，第一個(gè)位置會(huì)因?yàn)榛厮荻鴩L試放入所有的元素，同樣，第二個(gè)位置也會(huì)嘗試放入所有的元素。
畫(huà)出個(gè)決策樹(shù)：
以 {1-3-2} 為例，如果鏈表第一個(gè)位置為1，那第二個(gè)位置為 {2,3} 之一，{1}由于屬于存在的重復(fù)值忽略，
如果第二個(gè)位置放了{(lán)3}，那第三個(gè)位置就是{2}，就得出了一個(gè)結(jié)果。
我們對(duì)比一下以上兩個(gè)算法實(shí)現(xiàn)： 特別注意，算法B是真正的遞歸嗎？有沒(méi)有縮小計(jì)算規(guī)模？
時(shí)間復(fù)雜度計(jì)算公式：分支個(gè)數(shù) * 每個(gè)分支的計(jì)算時(shí)間
算法A的分支計(jì)算只有元素交換，按Arraylist處理，視為O(1)，算法B分支計(jì)算包含鏈表查找為O(N)，
算法A：N！* O(1) ，階乘級(jí)別，耗時(shí)不送。
算法B：N^n * O(N) ，指數(shù)級(jí)別，會(huì)爆炸！
我使用10個(gè)數(shù)全排測(cè)試如下(嚴(yán)謹(jǐn)?shù)闹v，兩者有數(shù)據(jù)結(jié)構(gòu)不同的影響，并不是說(shuō)僅有算法上的差異)：
總結(jié)：回溯和遞歸是兩種思想，可以融合，也可以單獨(dú)使用！
全文完！
我近期其他文章：
1?Redis高級(jí)應(yīng)用
2?聊聊算法——BFS和DFS
3?微服務(wù)通信方式——gRPC
4?分布式任務(wù)調(diào)度系統(tǒng)
5?Dubbo學(xué)習(xí)系列之十八(Skywalking服務(wù)跟蹤)
只寫(xiě)原創(chuàng)，敬請(qǐng)關(guān)注
關(guān)于找一找教程網(wǎng)
本站文章僅代表作者觀點(diǎn)，不代表本站立場(chǎng)，所有文章非營(yíng)利性免費(fèi)分享。
本站提供了軟件編程、網(wǎng)站開(kāi)發(fā)技術(shù)、服務(wù)器運(yùn)維、人工智能等等IT技術(shù)文章，希望廣大程序員努力學(xué)習(xí)，讓我們用科技改變世界。
[聊聊算法——回溯算法]http://www.zyiz.net/tech/detail-135184.html
總結(jié)
以上是生活随笔為你收集整理的回溯java算法_聊聊算法——回溯算法的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。
- 上一篇： java 关闭另一个jvm_JVM安全退
- 下一篇： java中有哪几种注释方式_在 Java