算法設計與分析 課件 第四章 回溯法

回溯法第四章主講人：楊圣云E-mail:yang@回溯法的思想回溯法是屬于搜索法的一類算法，主要特點是在可能解空間的搜索過程中，根據某個條件回溯，再開啟新的搜索，如此不斷的重復，直至找到滿足要求的一個解或所有解?；卮鹨韵滤膫€問題：1、如何構建可能解空間？2、采用什么樣的搜索過程？3、回溯條件是什么？4、什么是滿足要求和終止條件？回溯法的簡單示例簡單全排列問題：對于集合

S={1，2，3}

，求它的三個元素的全排列。請先思考以下問題：1、如何構建可能解空間？一種可能解空間{X1，X2，X3}其中X1，X2，X3是集合S的任一元素。2、什么樣的搜索過程？用三個for嵌套搜索這個可能解空間。3、回溯條件是什么？只要X1、X2、X3有兩個相同就回溯（或者開啟新的搜索）。4、什么是滿足要求？X1、X2、X3不相同且前面沒出現(xiàn)與他們一樣的序列。回溯法的簡單示例簡單全排列問題：對于集合

S={1，2，3}

，求它的三個元素的全排列。intmain(){intnums[]={1,2,3};for(inti=0;i<3;i++){for(intj=0;j<3;j++){if(j==i)continue;for(intk=0;k<3;k++){if(k==i||k==j)continue;

//輸出一個序列：nums[i],nums[j],nums[k]閱讀這個代碼段，思考并回答前面四個問題。通過簡單示例理解算法思想！回溯法:求解全排列問題的框架簡單全排列問題：對于集合

S={1，2，3…，n}

，求它的n個元素的全排列。請先思考以下問題：1、如何構建可能解空間？2、什么樣的搜索過程？3、回溯條件是什么？4、什么是滿足要求？新問題：有沒有n變化，但代碼不變的框架？for嵌套方式的代碼，會因n變化而變化?；厮莘?求解全排列問題的框架簡單全排列問題：對于集合

S={1，2，3…，n}

，求它的n個元素的全排列。for嵌套方式的代碼，會因n變化而變化。新問題：有沒有n變化，但代碼不變的框架？多叉樹的深度優(yōu)先遍歷框架是一種好的不變框架！回溯法:求解全排列問題的框架簡單全排列問題：對于集合

S={1，2，3…，n}

，求它的n個元素的全排列。多叉樹的深度優(yōu)先遍歷框架是一種好的不變框架！對四個問題的回答：1、多叉樹表示可能解空間。2、DFS進行搜索。3、回溯即對樹的剪枝。4、滿足要求即訪問到葉子節(jié)點。回溯法:求解全排列問題的框架代碼voidbacktrack(std::vector<int>&permutation){//如果當前的排列已經包含了所有的元素，那么就找到了一個新的排列if(permutation.size()==m){results.push_back(permutation);return;}//滿足條件-4for(size_ti=0;i<nums.size();i++){//多叉樹中同一層的兄弟節(jié)點-1，2if(visited[i]){continue;}//剪枝：開始搜索此節(jié)點的右兄弟，沒有則父節(jié)點的右兄弟，如此逐級搜索-3visited[i]=true;permutation.push_back(nums[i]);

backtrack(permutation);//繼續(xù)搜索它的子樹，遞歸地生成剩余元素的所有排列-1，2visited[i]=false;//回溯，撤銷前面的選擇-3permutation.pop_back();//開始搜索此節(jié)點的右兄弟，沒有則父節(jié)點的右兄弟，如此逐級搜索-3}}//理解并記住這個代碼框架與四個問題的對應部分??！回溯法:求解組合問題現(xiàn)實世界的問題中，還有一大類問題，它們的最終解與元素順序無關，但與是否包含某些元素有關，這類算法問題被稱為是組合問題。簡單示例：對于集合

S={1，2，3，...，N}，求解集合S的所有可能組合（集合S的所有子集）。依照回溯法框架：構造可能解樹、DFS遍歷這棵樹、回溯剪枝、終止條件？回溯法:求解組合問題依照回溯法框架：構造可能解樹、DFS遍歷這棵樹、回溯、設置終止條件。構造具體問題的可能解樹是一個難點，但在代碼中這棵樹是不存在的！回溯法:求解組合問題的框架代碼voiddfs(intindex){

if(index==S.size()){result.push_back(currentSubset);return;}////如果索引等于集合的長度，返回結果//選擇不包括當前元素在子集中dfs(index+1);//二叉樹空節(jié)點的子樹//選擇包括當前元素在子集中currentSubset.push_back(S[index]);//二叉樹實節(jié)點的子樹dfs(index+1);//回溯：移除最后一個元素，回到它的父節(jié)點currentSubset.pop_back();}};//理解并記住這個代碼框架代碼與四個問題的對應部分！！回溯法:N-皇后問題N-皇后問題，其中需要在棋盤上安排皇后，使得它們互不攻擊。這個問題的解決方案涉及到皇后的所有可能排列，并且每種排列都需要通過回溯法來檢驗是否有效！典型的多叉排列樹表示可能解空間。回溯法:0-1背包問題0-1背包問題，它要求在不超過背包最大承重的情況下，從一系列具有不同重量和價值的物品中選擇出最優(yōu)組合。結果與元素的排列順序無關，典型的組合問題，解空間樹是一棵完全二叉樹。回溯條件？終止條件？回溯法:物流派送問題已知n個城市的全連通矩陣T，要找出一個最短的可能物流派送路線，使得派送者訪問每個城市一次并返回原始城市。排列問題？組合問題？20回溯法:物流派送問題排