c++深搜與寬搜的解題思路

来源:https://www.cnblogs.com/zhangqixun/archive/2023/01/27/17069009.html
-Advertisement-
Play Games

寫在開頭:本文章提供深搜與寬搜的解題思路,無具體題目對應的代碼,如想瞭解,請到個人主頁查找,感謝觀看。 深度優先搜索(DFS): 遞歸,即函數調用自身,以逐步減小問題 的規模。但在一些問題中,並不是所有的 遞歸路徑都是有效的。 如圖所示迷宮,很可能會進入橙色所標識 的“死衚衕”,只能回到之前的路徑, ...


寫在開頭:本文章提供深搜與寬搜的解題思路,無具體題目對應的代碼,如想瞭解,請到個人主頁查找,感謝觀看。


 

深度優先搜索(DFS):

遞歸,即函數調用自身,以逐步減小問題 的規模。但在一些問題中,並不是所有的 遞歸路徑都是有效的。 如圖所示迷宮,很可能會進入橙色所標識 的“死衚衕”,只能回到之前的路徑,直到 找到綠色的解為止。

這種方法被稱為回溯法。 回溯法往往會嘗試一條儘可能深而完整的搜索路線,直至完全無 法繼續遞歸時才回溯,因而需要用深度優先搜索(DFS) 實現。


 

所以學會深度優先搜索前一定要深刻理解遞歸,先來看一段代碼:

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 void dfs(int x){
 4     if(x==0) 
 5         return;
 6     cout<<x<<endl;
 7     dfs(x-1);
 8     cout<<"*"<<x<<endl;
 9 }
10 int main(){
11     dfs(5);
12     return 0;
13 } 

 

 

結果為:

 
5
4
3
2
1
*1
*2
*3
*4
*5
 

因為函數的不斷嵌套,cout<<"*"<<x<<endl;  始終不會運行,只有x-1=0時才會一層一層由小到大執行這一行。


 

下麵是回溯的一般形式:

   
 1 回溯演算法的一般形式如下:
 2 void dfs(int k) { // k代表遞歸層數,或者說要填第幾個空
 3     if(所有空已經填完了){
 4         判斷最優解/記錄答案;
 5         return;    
 6     }
 7     for (枚舉這個空能填的選項)
 8         if (這個選項是合法的){//查看這個情況有沒有被占位 
 9             記錄下這個空(保存現場);//有時還需占位,例如四階數獨中的行、列、塊記錄 
10             dfs(k+1);
11             取消這個空(恢復現場);//如果占位了還需要取消占位 
12         }
13 }

 

 

 

 




 

 

 

廣度優先搜索(BFS):

深搜會儘快完成一個可行的解,再回溯嘗試其他的可能性。 當解相對稀疏,或問題很大時,深搜可能陷入過深、過窄的“陷阱”,這個時候就需要用到寬搜。

廣度優先搜索可以保證在求解最近、最短、最快等一類問題時, 搜索到的首個解就是最優解。

考慮另一種思路,從起點出發,類似於 潑水一般,讓水流順著多個方向同時蔓延。 這種方法被稱為洪泛法。 洪泛法會擴展相同層更多的可能性以拓寬廣 度,往往會使用廣度優先搜索(BFS) 實現。


 

先來瞭解一些關於隊列的函數(結果附在每行結束):

   
 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 int main(){
 4     queue<int> a;
 5     cout<<a.empty()<<endl;//1
 6     a.push(10);//{10}
 7     cout<<a.front()<<endl;//{10}
 8     cout<<a.empty()<<endl;//0
 9     a.pop();//{}
10     cout<<a.empty()<<endl;//1    
11         
12     a.push(12);
13     a.push(13);
14     a.push(14);//{12,13,14}
15     cout<<a.front()<<endl;//{12}
16     
17     return 0;
18 } 
 

這樣再理解廣度優先搜索的演算法就簡單多了:

1 Q.push(初始狀態); // 將初始狀態入隊
2 while (!Q.empty()) {
3 State u = Q.front(); // 取出隊首
4 Q.pop();//出隊
5 for (枚舉所有可擴展狀態) // 找到u的所有可達狀態v
6 if (是合法的) // v需要滿足某些條件,如未訪問過、未在隊內等
7 Q.push(v); // 入隊(同時可能需要維護某些必要信息)
8 }

 


總結:

 

 

回溯法/深度優先搜索(上圖 a) :

  快速構造解,使用遞歸。不撞南牆心不死。 但進入死路就回頭了。

洪泛法/廣度優先搜索(上圖 b):

   尋找最優解,使用隊列 從起點開始,逐層往外擴展。

  優化技巧(剪枝):將不可能的解提前剪掉。

 


您的分享是我們最大的動力!

-Advertisement-
Play Games
更多相關文章
  • AngularJS的重要概念 MVC模式 AngularJS最早按照MVC模式設計,在這種設計模式下,AngularJS組件可以分為: M: Model,即模型,是應用程式中用於處理應用程式數據邏輯的部分,在AngularJS中: 即作用域對象(當前為$rootScope), 它可以包含一些屬性或方 ...
  • 預設情況下:Photoshop 導出切片為【GIF】格式 當你很嗨皮的把【GIF】調整為【PNG】或【JPG】格式,並保存時: 你會發現,自己的圖片格式莫名其妙還是【GIF】: 但,我們的期望是: 原因是“因為我們沒有選中全部切片,並將其格式設置為【PNG】”,解決方案(選中全部切片設置為png或其 ...
  • 閉包和作用域 變數聲明 var 聲明特點 在使用var聲明變數時,變數會被自動添加到最接近的上下文 var存在聲明提升。var聲明會被拿到函數或全局作用域的頂部,位於作用域中所有代碼之前。 可多次重覆聲明。而重覆的var聲明則會被忽略 let 聲明特點 let聲明存在塊級作用域 let聲明(創建過程 ...
  • 如果你在項目中使用了 vuex模塊化,並且在項目中使用actions中函數調用頻率高,推薦瞭解一下這種方式。 比如下麵兩種方式調用 , 第一個是直接傳參設置, 第二個是添加了非同步ajax返回內容 在回調到等下我們要封裝的js中的成功回調里,然後這個成功回調就會反饋給組件 1.創建文件utils/vu ...
  • 一、Lua應用場景 游戲開發 獨立應用腳本 Web 應用腳本 擴展和資料庫插件如:MySQL Proxy 和 MySQL WorkBench 安全系統,如入侵檢測系統 教程採用Aide Lua Pro或AndLua+開發安卓應用。在學習開發安卓應用前,先學習lua的基礎課程。 二、配置手機開發環境 ...
  • 實現Spring底層機制-01 主要實現:初始化IOC容器+依賴註入+BeanPostProcessor機制+AOP 前面我們實際上已經使用代碼簡單實現了: Spring XML 註入 bean (Spring基本介紹02) Spring 註解方式註入 bean (Spring管理Bean-IOC- ...
  • 簡介: 訪問者模式,屬於行為型的設計模式。表示一個作用於某對象結構中的各元素的操作。它是你可以在不改變各元素的類的前提下定義作用於這些元素的新操作。 適用場景: 類中有易於變化的演算法。 希望數據結構與數據分離。 優點: 便於增加新的操作,相當於增加一個訪問者。訪問者模式將有關行為集中到一個訪問者對象 ...
  • 1.簡介 1.1 gRPC的起源 RPC是Remote Procedure Call的簡稱,中文叫遠程過程調用。用於解決分散式系統中服務之間的調用問題。通俗地講,就是開發者能夠像調用本地方法一樣調用遠程的服務。所以,RPC的作用主要體現在這兩個方面: 屏蔽遠程調用跟本地調用的區別,讓我們感覺就是調用 ...
一周排行
    -Advertisement-
    Play Games
  • Timer是什麼 Timer 是一種用於創建定期粒度行為的機制。 與標準的 .NET System.Threading.Timer 類相似,Orleans 的 Timer 允許在一段時間後執行特定的操作,或者在特定的時間間隔內重覆執行操作。 它在分散式系統中具有重要作用,特別是在處理需要周期性執行的 ...
  • 前言 相信很多做WPF開發的小伙伴都遇到過表格類的需求,雖然現有的Grid控制項也能實現,但是使用起來的體驗感並不好,比如要實現一個Excel中的表格效果,估計你能想到的第一個方法就是套Border控制項,用這種方法你需要控制每個Border的邊框,並且在一堆Bordr中找到Grid.Row,Grid. ...
  • .NET C#程式啟動閃退,目錄導致的問題 這是第2次踩這個坑了,很小的編程細節,容易忽略,所以寫個博客,分享給大家。 1.第一次坑:是windows 系統把程式運行成服務,找不到配置文件,原因是以服務運行它的工作目錄是在C:\Windows\System32 2.本次坑:WPF桌面程式通過註冊表設 ...
  • 在分散式系統中,數據的持久化是至關重要的一環。 Orleans 7 引入了強大的持久化功能,使得在分散式環境下管理數據變得更加輕鬆和可靠。 本文將介紹什麼是 Orleans 7 的持久化,如何設置它以及相應的代碼示例。 什麼是 Orleans 7 的持久化? Orleans 7 的持久化是指將 Or ...
  • 前言 .NET Feature Management 是一個用於管理應用程式功能的庫,它可以幫助開發人員在應用程式中輕鬆地添加、移除和管理功能。使用 Feature Management,開發人員可以根據不同用戶、環境或其他條件來動態地控制應用程式中的功能。這使得開發人員可以更靈活地管理應用程式的功 ...
  • 在 WPF 應用程式中,拖放操作是實現用戶交互的重要組成部分。通過拖放操作,用戶可以輕鬆地將數據從一個位置移動到另一個位置,或者將控制項從一個容器移動到另一個容器。然而,WPF 中預設的拖放操作可能並不是那麼好用。為瞭解決這個問題,我們可以自定義一個 Panel 來實現更簡單的拖拽操作。 自定義 Pa ...
  • 在實際使用中,由於涉及到不同編程語言之間互相調用,導致C++ 中的OpenCV與C#中的OpenCvSharp 圖像數據在不同編程語言之間難以有效傳遞。在本文中我們將結合OpenCvSharp源碼實現原理,探究兩種數據之間的通信方式。 ...
  • 一、前言 這是一篇搭建許可權管理系統的系列文章。 隨著網路的發展,信息安全對應任何企業來說都越發的重要,而本系列文章將和大家一起一步一步搭建一個全新的許可權管理系統。 說明:由於搭建一個全新的項目過於繁瑣,所有作者將挑選核心代碼和核心思路進行分享。 二、技術選擇 三、開始設計 1、自主搭建vue前端和. ...
  • Csharper中的表達式樹 這節課來瞭解一下表示式樹是什麼? 在C#中,表達式樹是一種數據結構,它可以表示一些代碼塊,如Lambda表達式或查詢表達式。表達式樹使你能夠查看和操作數據,就像你可以查看和操作代碼一樣。它們通常用於創建動態查詢和解析表達式。 一、認識表達式樹 為什麼要這樣說?它和委托有 ...
  • 在使用Django等框架來操作MySQL時,實際上底層還是通過Python來操作的,首先需要安裝一個驅動程式,在Python3中,驅動程式有多種選擇,比如有pymysql以及mysqlclient等。使用pip命令安裝mysqlclient失敗應如何解決? 安裝的python版本說明 機器同時安裝了 ...