第五講-搜索和動態(tài)規(guī)劃課件

搜索與動態(tài)規(guī)劃

《基礎(chǔ)》搜索與動態(tài)規(guī)劃

《基礎(chǔ)》1 深度優(yōu)先搜索深度優(yōu)先搜索屬于圖算法的一種,英文縮寫為DFS即DepthFirstSearch.其過程簡要來說是對每一個可能的分支路徑深入到不能再深入為止,而且每個節(jié)點只能訪問一次.

遞歸，回溯，暴力。就像走迷宮，走遍任何一條路徑，碰到死路。走不了了，就回頭找到最近的分叉路，走另一條。以此類推，直到找到出口。所以相當(dāng)暴力，基本上比賽不會出太赤裸裸的暴力搜索。用暴力搜索的要小心的估算復(fù)雜度，不輕易寫。 深度優(yōu)先搜索深度優(yōu)先搜索屬于2遞歸#include<iostream>usingnamespacestd;intf(intx){ if(x<=1)return1; elsereturnf(x-1);}intmain(){ intx; while(cin>>x) cout<<f(x)<<endl; return0;}遞歸#include<iostream>3 樹搜索到有@的點，當(dāng)樹層數(shù)稍微多時，指數(shù)級增長復(fù)雜度.#!((#)*$)!@(*#(條件剪枝！ 樹搜索到有@的點，當(dāng)樹層數(shù)稍微多時，指數(shù)級增長復(fù)雜度4遞歸:回溯方法例：皇后問題QQQQ遞歸:回溯方法例：皇后問題QQQQ53.回溯方法()()3.回溯方法()()63.回溯方法()()((1,1))Q3.回溯方法()()((1,1))Q73.回溯方法()()((1,1))((1,1)(2,3))QQ3.回溯方法()()((1,1))((1,1)(2,83.回溯方法()()((1,1))((1,1)(2,3))Q3.回溯方法()()((1,1))((1,1)(2,93.回溯方法()()((1,1))((1,1)(2,3))((1,1)(2,4))QQ3.回溯方法()()((1,1))((1,1)(2,103.回溯方法()()((1,1))((1,1)(2,3))((1,1)(2,4))((1,1)(2,4)(3.2))QQQ3.回溯方法()()((1,1))((1,1)(2,113.回溯方法()()((1,1))((1,1)(2,3))((1,1)(2,4))((1,1)(2,4)(3.2))QQ3.回溯方法()()((1,1))((1,1)(2,123.回溯方法()()((1,1))((1,1)(2,3))((1,1)(2,4))((1,1)(2,4)(3.2))Q3.回溯方法()()((1,1))((1,1)(2,133.回溯方法()()((1,1))((1,1)(2,3))((1,1)(2,4))((1,1)(2,4)(3.2))3.回溯方法()()((1,1))((1,1)(2,143.回溯方法()()((1,1))((1,1)(2,3))((1,1)(2,4))((1,1)(2,4)(3.2))((1,2))Q3.回溯方法()()((1,1))((1,1)(2,153.回溯方法()()((1,1))((1,1)(2,3))((1,1)(2,4))((1,1)(2,4)(3.2))((1,2))((1,2)(2,4))QQ3.回溯方法()()((1,1))((1,1)(2,163.回溯方法()()((1,1))((1,1)(2,3))((1,1)(2,4))((1,1)(2,4)(3.2))((1,2))((1,2)(2,4))((1,2)(2,4)(3,1))QQQ3.回溯方法()()((1,1))((1,1)(2,173.回溯方法()()((1,1))((1,1)(2,3))((1,1)(2,4))((1,1)(2,4)(3.2))((1,2))((1,2)(2,4))((1,2)(2,4)(3,1))((1,2)(2,4)(3,1)(4,3))QQQQ3.回溯方法()()((1,1))((1,1)(2,183.回溯方法遞歸的思想：當(dāng)前狀態(tài)目標(biāo)狀態(tài)g3.回溯方法遞歸的思想：當(dāng)前狀態(tài)目標(biāo)狀態(tài)g19Hdu2510符號三角形/showproblem.php?pid=2510符號三角形的第1行有n個由“+”和”-“組成的符號，以后每行符號比上行少1個，2個同號下面是”+“，2個異號下面是”-“。計算有多少個不同的符號三角形，使其所含”+“和”-“的個數(shù)相同。n=7時的1個符號三角形如下:

++-+-++

+----+

-+++-

-++-

-+-

--

+

Hdu2510符號三角形http://acm.hdu.20怎么做遞歸：dfs(introw,intval,intplus,intmin);建立一個數(shù)組，暴力填寫+和-，最后判斷是否合法。合法就num++。這個思路很容易想到，想到后馬上看數(shù)據(jù)范圍，n<=24，貌似不大。暴力寫寫，掛了。打表吧。還是不行，跑不出結(jié)果怎么打表，囧剪枝！！計算出一共會有多少個+，這樣一旦+或者-的數(shù)量超過這個數(shù)，就可以回溯了。怎么做遞歸：dfs(introw,intval,in21n<=24#include<iostream>usingnamespacestd;inta[]={0,0,0,4,6,0,0,12,40,0,0,171,410,0,0,1896,5160,0,0,32757,59984,0,0,431095,822229};intmain(){intn;while(cin>>n,n)cout<<n<<""<<a[n]<<endl;return0;}

n<=24#include<iostream>usin22Pku1088滑雪/JudgeOnline/problem?id=1088記憶化搜索,對于dfs(intx,inty)如果dp[x][y]==-1進行計算，不然返回dp[x][y]計算時,dp[x][y]=max(dfs(x-1,y),dfs(x+1,y),dfs(x,y-1),dfs(x,y+1))+1;(如果周圍比它小的話)Pku1088滑雪http://acm.pku.e23推薦題目：Foj：140817341543推薦題目：Foj：24廣度優(yōu)先搜索bfs

breadth-firstsearch@14513211671615124*2820113917191018如果*想碰到@，需要多少步。DFS寫寫看吧。Bfs用隊列。Structnode{Intx;Inty;Intnum;}Boolflag[100][100];廣度優(yōu)先搜索bfs

breadth-firstsearc25Hdu3220Alice’sCube上海賽區(qū)的題目，清華10+分鐘過的題目，全場100+多隊，幾乎所有的隊伍都過的題目，但是做出來的速度卻相差很多。40分鐘內(nèi)寫出來，并一次ac的。Hdu3220，會的可以去寫寫。Bfs+位壓縮。/showproblem.php?pid=3220Hdu3220Alice’sCube上海賽區(qū)的題目，26 題目大意：給定一個幾何體，每個點都有一個值，0或者1，每次可以把線段相鄰的兩個點的值互換，問需要幾步，可以讓1-8號節(jié)點是0，而9到16號為1 題目大意：給定一個幾何體，每個點都有一個值，27做法首先，肯定要很認(rèn)真的看清哪些點是相鄰的，為了提高ac率，要檢查兩三遍。比賽場上有人沒用位壓縮的，肯定超時了，后來跑了很久后，終于打表過。浪費很多時間。對于16個點，int有32位，我們可以令每一位對應(yīng)好節(jié)點號，比如3就是0..011這樣每次送入隊列的只是一個數(shù)字，這個數(shù)字就能用16個點的信息，如果用結(jié)構(gòu)體，里面再定義boolflag【16】，就會超時。做法首先，肯定要很認(rèn)真的看清哪些點是相鄰的，為了提高ac率，28 做法未壓縮的目標(biāo)狀態(tài)：256-1=255初始態(tài)：自己用二進制轉(zhuǎn)十進制法轉(zhuǎn)得到x；structnode{intnum;intzt;};用到stl<queue>開始時s.num=0;s.zt=x; 做法未壓縮的目標(biāo)狀態(tài)：256-1=25529做法(偽代碼)Q.push(s);While(!q.empty()){Tmp=q.front();Q.pop();該變一步，得到tmp2tmp2.num=tmp1.num+1,q.push(tmp2)；If(tmp2.zt=目標(biāo)狀態(tài)){打印num；break;}}做法(偽代碼)Q.push(s);30 廣度優(yōu)先搜索Bfs用在地圖搜索的非常多。如何提高效率。以題目而定。常用：優(yōu)先隊列優(yōu)化。就是（堆）例子：草地-2平地-1草地-2草地-2雪地-3平地-1平地-1雪地-3雪地-3雪地-3草地-2平地-1 廣度優(yōu)先搜索Bfs用在地圖搜索的非常多。草地平31Bfs簡介Bfs用隊列的思想，先進先出。Hdu1242Rescue/showproblem.php?pid=1242Bfs簡介Bfs用隊列的思想，先進先出。32做法兩種1：記憶化bfs，用一張二維表，存到達每個點所要的最短步數(shù)，初始化為inf(無窮大);每次用bfs到達的步數(shù)如果小于該點的原值，更新，并入隊。直到隊列為空；2：優(yōu)先隊列，每次選取步數(shù)最少的點出來，第一次到達目標(biāo)點的步數(shù)就是最小步數(shù)。做法兩種1：記憶化bfs，用一張二維表，存到達每個點所要的最33Bfs用到的stl。#include<queue>Structnode{intx,inty,intnum;}queue<node>q2;priority_queue<node>q1;可以自動選取優(yōu)先級最高的點出來擴展。比如上題中的消耗體力最少的點出來擴展。提高效率。Bfs用到的stl。#include<queue>34Priority_queue其實就是《數(shù)據(jù)結(jié)構(gòu)》將會學(xué)到的“堆”，能在log級的復(fù)雜度內(nèi)找到最小的值，并調(diào)整堆。自己寫堆效率較高，代碼量大。且復(fù)雜容易出錯。一般情況下stl的這個函數(shù)效率也足夠高了。很方便。結(jié)構(gòu)體小于號重載后，每次選取步數(shù)最小的點出來。Priority_queue其實就是《數(shù)據(jù)結(jié)構(gòu)》將會學(xué)到的“35Bfs

題目：Fzu1205Poj1724Hdu2267Bfs

題目：Fzu120536A*算法A*算法37動態(tài)規(guī)劃不得不說的例子：數(shù)字三角形動態(tài)規(guī)劃38動態(tài)規(guī)劃與遞歸動態(tài)規(guī)劃思想：求c(n,m);遞歸寫法：intc(intn,intm){ if(m==0)return1; if(m==1)returnn; if(n==m)return1; returnc(n-1,m-1)+c(n-1,m);}動態(tài)規(guī)劃與遞歸動態(tài)規(guī)劃思想：39動態(tài)規(guī)劃寫法 for(i=0;i<n;i++) { for(j=0;j<=i;j++) { if(j==0||i==j) C[i][j]=1; else C[i][j]=C[i-1][j]+C[i-1][j-1]; } }動態(tài)規(guī)劃寫法 for(i=0;i<n;i++)40區(qū)別動態(tài)規(guī)劃往往效率很高。而遞歸寫法，由于層層遞歸，速度很慢。當(dāng)n，m=（30，15）的時候，得出結(jié)果就需要好幾秒了，如果n，m=（100，50）發(fā)現(xiàn)時間上等的超出我們的耐性了。而動態(tài)規(guī)劃只是100*50的數(shù)組處理，馬上就有結(jié)果。動態(tài)規(guī)劃，要想好動態(tài)規(guī)劃的方程，幾乎每場比賽都有1題。區(qū)別動態(tài)規(guī)劃往往效率很高。而遞歸寫法，由于層層遞歸，速度很慢41Fzu1004Fzu100442For(i=n;i>=1;i--)For(j=1;j<=I;j++)dp[i][j]+=max(dp[i+1][j],dp[i+1][j+1]);輸出dp[0][0]For(i=n;i>=1;i--)43不得不說的另一個例子：背包問題Hdu2602BoneCollector/showproblem.php?pid=2602不得不說的另一個例子：背包問題Hdu2602BoneC440-1背包題目模型：N個物體：兩個屬性：重量和價值如上：5個物體，背包容量10個重量5個物體的價值：12345重量54321如何選取其中的物體，使價值和最大，當(dāng)然重量又不能超過背包的最大允許量。0-1背包題目模型：45動態(tài)規(guī)劃每次加入一個物體的考慮，只有取與不取的情況，保留最大值。弄懂思想代碼很短。初次接觸則不好懂n個物體，m的背包容量for(i=0;i<n;i++) for(j=m;j>=w[i];j--) dp[j]=max(dp[j],dp[j-w[i]]+v[i]);動態(tài)規(guī)劃每次加入一個物體的考慮，只有取與不取的情況，保留最大46無窮背包只要從小往大dp就行了for(i=0;i<n;i++) for(j=0；j<=m;j++) dp[j]=max(dp[j],dp[j-w[i]]+v[i]);無窮背包只要從小往大dp就行了47

USACO2.2SubsetSums

題目如下：

對于從1到N的連續(xù)整集合合，能劃分成兩個子集合，且保證每個集合的數(shù)字和是相等的。

舉個例子，如果N=3，對于{1，2，3}能劃分成兩個子集合，他們每個的所有數(shù)字和是相等的：

{3}and{1,2}

這是唯一一種分發(fā)（交換集合位置被認(rèn)為是同一種劃分方案，因此不會增加劃分方案總數(shù)）

如果N=7，有四種方法能劃分集合{1，2，3，4，5，6，7}，每一種分發(fā)的子集合各數(shù)字和是相等的:

{1,6,7}and{2,3,4,5}{注1+6+7=2+3+4+5}

{2,5,7}and{1,3,4,6}

{3,4,7}and{1,