[演算法] 深度優先搜尋(Depth-first Search) - iT 邦幫忙

30天學演算法和資料結構系列第18 篇 ... 表示目前是否有使用此數字total = 0 #代表可行解總共有幾種def dfs(step, total, a, ... +i))==1: print (a,b,c,d,e,f,g,h,i). 2019iT邦幫忙鐵人賽 DAY 18 0 SoftwareDevelopment 30天學演算法和資料結構系列第 18篇 [演算法]深度優先搜尋(Depth-firstSearch) 2019鐵人賽 演算法 python python3 python3 ramonliao 2018-11-0223:52:133961瀏覽 還記得之前有討論過的列舉法嗎？今天我們來做個延伸。

之前的列舉法是將用for迴圈的方式，一層一層的舉出所有的可能，然後將所有舉出的可能和我們所設定的條件相比對，若符合則輸出。

但這邊問題來了，題目設定的是0到9的數字，那若將題目加以變更從1到100，甚至1到1000呢？那for迴圈不就要寫千百次？那是不可能的。

所以有了遞迴的方法。

深度搜尋(Depth-firstSearch)，其實就是遞迴的一種運用沒錯，一層一層地找出所有可能，但程式碼卻會簡潔的多。

直接舉個例子吧。

之前用列舉法所要找的數字排列，以符合方程式。

[1,2,3,4,5,6,7,8,9] 將數字1到9填入上面的方程式，使之為1。

接下來我們會用兩個陣列，一個是用來放數字並嘗試運算解的陣列，另一個是用來標示數字是否被取用的陣列。

深度優先搜尋法 a=[] book=[] foriinrange(10): a.append(0)#設數字9+1個空盒子 book.append(0)#設數字9+1個空盒子，表示目前是否有使用此數字 total=0#代表可行解總共有幾種 defdfs(step,total,a,book):#step代表目前的位置 ifstep==9:#如果站在索引為9的盒子表示0~8共九個位置都已有待運算的數字 ifa[0]/(a[1]*10.+a[2])+a[3]/(a[4]*10.+a[5])+a[6]/(a[7]*10.+a[8])==1: total+=1#如果滿足解，可行解+1 print(a) returntotal#返回之前的一步(最接近呼叫的地方) #站在地step位置，按照0~8的順序一一的嘗試 foriinrange(9): ifbook[i]==0:#如果book[i]等於0，代表這個位置的數字可以用 a[step]=i+1#將可用數字給到空盒子裡(因為i為索引，所以要加1) book[i]=1#表示這個位置的數字已被取用 total=dfs(step+1,total,a,book)#藉由遞迴來找出更深層的解 book[i]=0#但記得要把剛才嘗試過的數字重置，才能進行下一次的嘗試 returntotal total=dfs(0,total,a,book) print(total/2)#因為有重複解，所以要除以2 列舉法 fromcopyimportcopy list_1to9=[1,2,3,4,5,6,7,8,9] #在b層建一個新的1-9，然後pop掉取過的，C層再複製b取過的，建一個新的1-9，pop調取過的 #d層再複製c層取過的，建新的1-9.....以下同上。

這樣就最後一行就不用再把取過的加回去了。

#如果再稍稍修改，效率會再更好喔 forainlist_1_to_9:#a從list_1to9取數字 list_a=copy(list_1to9)#list_a複製list_1to9 list_a.remove(a)#將a選取的數字從list_a去除，留下可以繼續被選取的字給b forbinlist_a:#b從list_a取數字 list_b=copy(list_a)#list_b複製list_a list_b.remove(b)#將b選取的數字從list_b去除，留下可以繼續被選取的字給c forcinlist_b: list_c=copy(list_b) list_c.remove(c) fordinlist_c: list_d=copy(list_c) list_d.remove(d) foreinlist_d: list_e=copy(list_d) list_e.remove(e) forfinlist_e: list_f=copy(list_e) list_f.remove(f) forginlist_f: list_g=copy(list_f) list_g.remove(g) forhinlist_g: list_h=copy(list_g) list_h.remove(h) foriinlist_h: #這時候選取完所有的數字，並填入方程式進行驗證，如果為是，輸出結果；如果為否，則沿著迴圈h到迴圈a一一測試各種可能。

if(a/(b*10.+c)+d/(e*10.+f)+g/(h*10.+i))==1: print(a,b,c,d,e,f,g,h,i) 可以比較看看兩者的差別。

留言 追蹤 檢舉 上一篇 [演算法]插補搜尋(InterpolationSearch) 下一篇 [演算法]費氏搜尋(FibonacciSearch) 系列文 30天學演算法和資料結構 共31篇 目錄 RSS系列文 訂閱系列文 204人訂閱 27 [演算法]並查集(Union-findAlgorithm) 28 [演算法]最短路徑(Dijkstra演算法) 29 [演算法]最短路徑(Bellman-Ford演算法) 30 [演算法]最短路徑(Bellman-Ford演算法-佇列優化) 31 [完結]總整理＋後記 完整目錄 尚未有邦友留言 立即登入留言 iT邦幫忙鐵人賽 參賽組數 1087組 團體組數 52組 累計文章數 20485篇 完賽人數 572人 鐵人賽最新文章 資料驗證(golang)(Day23) .NetCoreWebApi_筆記22_Swagger自訂文件並讀取API註解描述 [Day??]2021iThome鐵人賽-頒獎典禮@2022.01.08‧輔仁大學 [Day33]HexoxNexT-顯示最新文章、導入GoogleAnalytics的坑 【Day31】新加坡工作後續的時程 重構原本的內容(golang)(Day22) Laravel-jQueryAJAX範例 2022/1/2更新 .NetCoreWebApi_筆記21_Swagger及OpenAPI介紹與配置使用方式_API管理與測試探討 .NetCoreWebApi_筆記20_api結合ADO.NET資料庫操作part8_新聞文章查詢 前往鐵人賽 技術推廣專區 [Day2]抓取每日收盤價 [Day1]基本工具安裝 利用python取得永豐銀行API的Nonce [Day03]tinyML開發板介紹 永豐金融API測試員 [Day01]在享受tinyML這道美食之前 [Day3]使用ta-lib製作指標 [Day4]函數打包與買進持有報酬率試算 計算API所需要的參數:HashID 計算API所需要的參數:IV 前往鐵人賽 熱門問題 中華電信企業資安攻擊名稱HTTP-APACHE-LOG4j2-BODY6-RCE 40人小公司用的郵件伺服器 急救！將ImageView傳到另一個頁面 關於團隊合作 正航ERP相關問題 資安宣導文案 請問有哪位好心人能借一下百度帳號... 請教SQL大師，如何在GROUPBY分群裡找出組別最多筆數量的組別名稱 [已解決]急!!!csv匯入MySQLWorkbench出現錯誤訊息請問如何解決 C#如何將資料庫的每個字元從原本的(ascii編碼)逐一轉成(utf8編碼) IT邦幫忙 站方公告 【2021iThome鐵人賽】登登登！究竟獎落誰家，2021iThome鐵人賽得獎名單正式揭曉 熱門tag 看更多 13th鐵人賽 12th鐵人賽 11th鐵人賽 鐵人賽 2019鐵人賽 2018鐵人賽 javascript 2017鐵人賽 windows php python windowsserver linux c# 程式設計 資訊安全 css vue.js sql 分享 熱門回答 40人小公司用的郵件伺服器 關於團隊合作 資安宣導文案 SVN版本控制的選擇 python檔案計算問題 [已解決]急!!!csv匯入MySQLWorkbench出現錯誤訊息請問如何解決 C#如何將資料庫的每個字元從原本的(ascii編碼)逐一轉成(utf8編碼) 正航ERP相關問題 為什麼Visualstudio查詢資料庫資料會顯示 中華電信企業資安攻擊名稱HTTP-APACHE-LOG4j2-BODY6-RCE 熱門文章 【Day31】新加坡工作後續的時程 2021法遵科技與電腦稽核專題競賽-賀雲科大、逢甲、北商大、中正、致理科大、亞洲科大等學校隊伍獲獎，培育智慧法遵與AI稽核人才邁向國際~ Laravel-jQueryAJAX範例 [Day33]HexoxNexT-顯示最新文章、導入GoogleAnalytics的坑 【徵才】台北中山區-知名航空貨運-資訊網管人員 重構原本的內容(golang)(Day22) 科學家與研究生的關係研究篇 [Day??]2021iThome鐵人賽-頒獎典禮@2022.01.08‧輔仁大學 30天Python自學:Day01 印表機維修五種常見故障，若遇到問題就能先自己排除了 一週點數排行 更多點數排行 海綿寶寶(antijava) Gary(mosbbs) raytracy(raytracy) 一級屠豬士(hitomitanaka) Samuel(kuanyu) ccenjor(ccenjor) 居然解出來了(partyyaya) horace_work(horace_work) 純真的人(jer5173) souda(souda) × At 輸入對方的帳號或暱稱 Loading 找不到結果。

標記 {{result.label}} {{result.account}} 關閉