資源描述：
《DFS_深度優(yōu)先搜索.ppt》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫。
1、DFS——深度優(yōu)先搜索許杰浩從問題的某一種可能出發(fā),搜索從這種情況出發(fā)所能達(dá)到的所有可能,當(dāng)這一條路走到“盡頭”而沒達(dá)到目的地的時候,再倒回上一個出發(fā)點,從另一個可能出發(fā),繼續(xù)搜索.AB12345678910如從A找一條路到B的時候深度優(yōu)先搜索的搜索策略是：盡可能“深”的搜索某一分支。在深度優(yōu)先搜索中，對于最先發(fā)現(xiàn)的結(jié)點，如果還有以此為起點的未搜索邊，則沿此邊繼續(xù)搜索下去。當(dāng)結(jié)點V的所有邊都已經(jīng)被探尋過，搜索將回溯到發(fā)現(xiàn)點V的那條邊的始結(jié)點。重復(fù)此過程直至源結(jié)點可到達(dá)的所有結(jié)點為止12457368深搜的順序是：1-2-4-7---5-8---3-612
2、457368深搜的順序是：1-2-4-7---5-8---3-6偽代碼：voiddfs(intu){for(u的每一個子節(jié)點v){dfs(v);}}過程在可以看做是棧的結(jié)構(gòu)dfs(1)dfs(1)dfs(1)dfs(1)dfs(1)dfs(1)dfs(1)dfs(1)dfs(2)dfs(2)dfs(2)dfs(2)dfs(2)dfs(3)dfs(3)dfs(4)dfs(4)dfs(5)dfs(5)dfs(6)dfs(7)dfs(8)樹的深搜HALIFBCDEJGKS圖的深搜Hdu1241題目大意：給定一個圖，上邊有*和@兩種標(biāo)記，其中@表示石油，好多@
3、連在一起可以看成一個大的石油區(qū)，問在這個區(qū)域中有多少個石油區(qū)intdx[8]={-1,-1,-1,0,1,1,1,0};Intdy[8]={-1,0,1,1,1,0,-1,-1};Voiddfs(intx,inty){g[x][y]=‘*’;for(inti=0;i<8;i++){xx=x+dx[i];yy=y+dy[i];if(xx<0
4、
5、yy<0
6、
7、xx>=m
8、
9、yy>=n)continue;if(g[xx][yy]=='@')dfs(xx,yy);}}0127_3654yxPOJ2676題意：數(shù)獨，找出一個可行解即可（數(shù)獨規(guī)則：：把一個9行9列的
10、網(wǎng)格，再細(xì)分為9個3*3的子網(wǎng)格，要求每行、每列、每個子網(wǎng)格內(nèi)都只能使用一次1~9中的一個數(shù)字，即每行、每列、每個子網(wǎng)格內(nèi)都不允許出現(xiàn)相同的數(shù)字。）0是待填位置，其他均為已填入的數(shù)字。粗暴的方法DFS加回溯大概的框架：dfs(intx,inty){for(inti=1;i<=9;i++){if(這個位置能填i){g[x][y]=i;(找到下一個為0的位置為(xx,yy));dfs(xx,yy);g[x][y]=0;}}}Dfs的優(yōu)化剪枝：在求解問題的時候，有時沒必要將所有的可能結(jié)果都搜索一遍。如果在搜索一個新的節(jié)點的時候，如果可以判斷到這一個節(jié)點不會得
11、到解或是最優(yōu)解，就可以直接放棄往下的搜索，同理搜索過的狀態(tài)也可以直接放棄。ZOJ1008GnomeTetravex題目大意：有一個N*N(N<=5)的方格矩陣與N*N張卡片。每個卡片被劃分為4個三角形，每個三角形標(biāo)有一數(shù)字(范圍從0到9),分別將這些三角形稱作左三角形，右三角形，上三角形，下三角形。要求將這些卡片放置到這N*N的方格中，當(dāng)放置成功的時候要求任意相鄰的兩個方格中的卡片中相鄰的三角形數(shù)字相等。問能否按照要求放置成功，如果放置成功就輸出Possible，否則輸出Impossible。SampleInputSampleOutput2Game1:
12、Possible5914445668540443分析：如果我們先從這寫卡片中任意選取一個，放置在1行1列，然后選下一個卡片放1行2列（放置的時候我們要像判斷符不符合條件），依次下去問題就應(yīng)該解決了。但是如果第一個位置有n個選擇，第二個位置有n-1個選擇，第三個位置有n-2個選擇。。。如果所有的點都遍歷一遍那么時間效率將會是O(n!)，當(dāng)n=25,25!=15511210043330985984000000嗯，妥妥的超時了這時候就要進(jìn)行剪枝了。利用剪枝，去掉一些重復(fù)的情況。這個題怎么剪枝？如果這寫卡片中有10個是相同類型的，那么搜索的結(jié)果就變成了15！=
13、1307674368000所以這一個剪枝就是，記錄有多少種不同的卡牌，記錄同種卡牌的數(shù)量還有一些技巧就是:從上往下，從左往右去放，假設(shè)從0開始放，當(dāng)放到N*N的時候就是搜索成功的時候0123booldfs(intindex){if(index==N*N)returntrue;else{……}}習(xí)題：ZOJ1008ZOJ1004POJ2676經(jīng)典n皇后問題Thanks！
