算法設(shè)計(jì)與分析 課件 第四章 回溯法

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

S={1，2，3}

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

S={1，2，3}

，求它的三個(gè)元素的全排列。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;

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

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

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

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

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

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

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

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

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

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