標題 淺談深搜與廣搜
眾所周知，DFS和BFS都是搜索中的入門技巧，今天我就來說一遍DFS和BFS這倆玩意
首先，是我們的DFS選手，用一個形象的比喻來比喻DFS的話，那就是DFS是一個單純的男孩，這個男孩在追求一個女孩的程序中是不到最后絕不放棄，直到被女孩拒絕后，他才會回溯，去尋找新的機會，
如圖所示，這個男孩追求一個女孩失敗后，會讀取存檔到上一個階段，走別的路線，如果每條路線都失敗了的話，這個男孩就會徹底放棄這個女孩，回到初始的位置，重新進行游戲，這就是我們的DFS小伙
接著來看看核心的代碼
void dfs(int girl, int u)//girl代表女孩編號,u代表走的劇情線
{
if (girl > /*女孩數*/) return;//你是個單身狗,游戲結束
if (u > /*本女孩路線數*/) {//說明這個女孩不愛你，放棄她吧
dfs(girl + 1, 0);//回溯存檔到下一個女孩
return;//刪檔
}
//下面的這個標記，是dfs非常關鍵的部分,要防止死回圈
vis[girl][u] = true;//本女孩的第u條劇情線走過
for (int i = /*劇情下一點*/; i < /*劇情的分支路線*/; i -> /*下一個分支*/) {
dfs(girl, i);//找尋下一個路線有沒有出路
vis[girl][u] = false;//記得存檔
if (/*這個路線走到最后女孩和你在一起*/) {
cout << "恭喜你" << endl;//happy end
return;//結束本次游戲
}
}
}
這就是DFS的核心思路了，走完一個地方,要在這個地方做好記號，同時存下自己的存檔，防止自己下一次又走回這個路線，那就浪費時間了，在本次存檔失敗后，就要找到自己上一次存檔，從上一次存檔繼續尋找有沒有GOOD END，如果這些存檔都沒有，那就死檔了，刪檔重來吧！！！
接著我們要來談談BFS了，我們的BFS選手，他和DFS選手不一樣，這個選手在追求女孩的時候，不會一個一個的去追求，而是會選擇同時他身邊的所有女孩（牛逼吼），只有BFS找到一個真正好的女孩后，他才會放棄其他女孩，
就像這幅圖一樣，這個男孩會對三個女孩同時示好，接著也會同時走這三個女孩的劇情線，直到走到一個真愛路線，他才會放棄周圍的其他女孩，對于這個男孩來說，他不需要存檔，他可以一口氣莽下去，把所有路線都走過去，直到走到GOOD END
接著來看看我們的核心代碼
void bfs()
{
queue</*劇情型別*/> lp;
lp.push(/*先把三個女孩推入佇列中*/);//同時找三個女孩示好
while (!lp.empty()) {//只要這個佇列不是空的,說明這個男孩還有機會
/*劇情型別*/ now = lp.front();//取出隊首
lp.pop();//隊首元素出隊
for (int i = /*可以走的女孩的下一個路線*/; i < /*這些女孩的全部劇情路線*/; i -> /*下一個劇情路線*/) {
if (/*如果這個劇情路線后面還有路*/) {
lp.push(/*這條劇情線*/);//讓這條線入隊
}
if (/*這個劇情的女孩是你的真愛*/) {
cout << "恭喜你" << endl;
break;//游戲結束
}
}
}
}
這就是BFS的核心思路了，他會走過他附近的每一個可能，只要這個可能接下來還有希望，他就會接著走，是一個高效率的“找女朋友的方式”？（要不你來試試）
最后呢，DFS和BFS各有優缺點
DFS的優點就是,他沒錢！每次只能追一個女孩,所以他每次只容納下一個女孩的劇情線,空間復雜度為O(n),而時間復雜度就截然不同了，他會一個一個的去尋找，直到找到真愛，倘若路線多的話,他可能一輩子都找不到,所以他時間復雜度非常高.
BFS的優點就是,他有錢！他的資金能夠支撐自己同時追求多個女孩，把每一個女孩的劇情線都走過，因此,BFS找真愛的路途就很短暫,他的效率非常高，所以時間復雜度非常小，而又因為他同時追求多個女孩，所以他的開銷大，花錢大把大把的花，空間復雜度O(很大很大)，
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/277425.html
標籤：其他