擁抱「資料結構」的「演算法」(28) - 深度優先與廣度優先搜尋法

 

前言

圖形也有搜尋演算法可以使用，例如深度優先搜尋法與廣度深度優先搜尋法，一起來看看吧

生活常識

你在超市購物時，都是怎麼選購貨架上的物品？是使用左右掃射，還是上下掃瞄呢？哪一種方式可以最快找到你想買的東西呢？



圖片來源:https://www.pexels.com/zh-tw/photo/1005638/

你玩過迷宮嗎？這是個很考驗運氣、耐性、智慧與勇氣的遊戲，從起點走到終點，會出現很多路徑，面臨多條路徑的選擇時，常常會出現選擇障礙，因為如果選錯可能就會走回頭路，你會怎麼決定你的策略呢？

  1. 隨機選一條路之後就勇往直前等遇到死路在做打算，
  2. 每個路徑會先去探一小段路之後再做打算

不管是哪一種，都很有可能走得頭昏眼花、四肢不聽使喚，最後還不見得能順利過關XD，不知道你有沒有聽過一種可以快速破解迷宮的方法，叫做沿牆走，不過只適用於某些類型的迷宮，最土法煉鋼的方式就是勇敢嘗試，試到最後面一定會找到出口，只怕時間不夠或是你已經感到心疲力竭先放棄了，那要怎麼預防迷路呢？可以學習童話故事中丟麵包屑的方式，讓自己清楚知道要注意哪些路徑



圖片來源:https://www.pexels.com/zh-tw/photo/1904204/

專業知識

圖形說明

如果對於樹或圖形結構不熟悉的話，可以參考前幾天的文章，圖形是由許多頂點與邊組成的，而樹也是圖的一種，當今天我們在某著頂點，想要到達某個頂點時，會經過某些路徑，而要如何快速找到這兩個頂點之間的相連路徑，就是演算法要做的事情

判斷是否走過

由於目標頂點位於圖形的哪個位置我們並不知道，檢查該頂點是不是我們要尋找的頂點，在搜尋過程中為了清楚知道哪些頂點是已經搜尋過的(就像走迷宮可以丟麵包屑或做記號)，我們必須透過其他的資料結構堆疊、佇列或是使用遞迴演算法來輔助我們記憶已訪問過的頂點或路徑，才不會做重覆性的搜尋

深度優先搜尋法 Depth-first Search

選擇路徑

如果要找 A 走到 G 的路徑，請找一個與 A 相鄰的點且沒有走過的點，重覆以下兩個動作直到找到目標點或所有點都被走過為止

  • 有找到：判斷是否為目標點，如果不是則將此點紀錄為已走過，並以此點為新的點，再繼續往下找與新點相鄰且沒有走過的點，例如， B 與 A 相鄰，B 不是 G 點，所以再去找與 B 相鄰的點，找到 C
  • 沒找到：回到前面的點，然後再去找到其他沒有走過的相鄰點做搜尋，例如，與 C 點相鄰的點都走過了，還是找不到 G 點，那就要回到 B，再去找與 B 相鄰且沒有走過的點



例子

如果以二元樹作為例子，其實搜尋方式就很類似前序走訪，例如從節點 1 走到節點 6，如果這是一個迷宮，使用深度搜尋實際走的樣子會長這樣



只是要特別注意的是走訪過的節點不能再度走訪，所以使用堆疊後進先出的特性來記錄還沒有走過的節點，如果忘記堆疊的可以參考前幾天的文章



由上圖可發現，深度優先會一直往下一層搜尋，直到樹葉節點還找不到未走過的節點時，才會往上一層找沒有走過的節點，搜尋順序為：1、2、4、5、6、6、7

廣度優先搜尋法 Breadth-first Search

選擇路徑

如果要找 A 走到 G 的路徑，請找一個與 A 相鄰的點且沒有走過的點，重覆以下兩個動作直到找到目標點或所有點都被走過為止

  • 有找到：判斷是否為目標點，如果不是則將此點紀錄為已走過，並回到上一個基準節點去尋找其他與基準節點相鄰的點，例如，A 為基準點 B，A 與 B 相鄰，但 B 不是 G 點，所以需要回到 A 點，再去找與 A 相鄰且沒有走過的點，會找到 C
  • 沒找到：表示與基準節點相鄰的點都不是目標點，則找新的基準點，例如，以 A 為基準點的相鄰節點都走過了，則可使用 B 當作基準點，再去找與 B 相連的節點



例子

如果以二元樹作為例子，其實搜尋方式如下圖，例如從節點 1 走到節點 6，如果這是一個迷宮，使用廣度搜尋實際走的樣子會長這樣



只是要特別注意的是走訪過的節點不能再度走訪，所以使用佇列後進先出的特性來記錄還沒有走過的節點，如果忘記佇列的可以參考前幾天的文章



由上圖可發現，廣度優先會往同一層搜尋，直到找不到未走過節點時，才會往下一層找沒有走過的節點，搜尋順序為：1、2、3、4、5、6、7

今日小結

深度與廣度誰比較好呢？其實還是要看使用的情境，如果已經有個很明確的目標，那深度也許是不錯的選擇，但資源有限的情況下，可能廣度會比較好，個人看法，參考參考XD

今日謎題

小美遇到的人生的十字入口，入口位於下圖的上方，有三個入口，行經路線只要經過線條，就必須強制轉彎，途中會經過許多字母，其中一條路可以組成一個有意義的單字，小美不知道該如何選擇，請問你能幫他找到對他最有意義的一條路徑嗎？



昨日謎題

謎題說明：認識到費式數列的規則之後，再去認識其他的類似也有其他規則的數列，這段數列 1, 1, 1, 2, 2, 3, 4, 5, 7, 9, 12, 16, ？，其實是巴都萬數列



簡單來說，P(3) = P(1) + P(0) = 1 + 1 = 2，也就是說每一個數字，都是由往前推的第三個數字與第二個數字相加而來，再舉一個例子，16 = 7(往前推的第三個數字) + 9(往前推的第二個數字)，所以問號處的數字會由 9 + 12 而組成，所以答案是 21，你答對了嗎？

留言

張貼留言

這個網誌中的熱門文章

CPE 一顆星選集題目說明與解答 - Java 筆記與心得分享

以下是自己的 CPE 一顆星選集 解題紀錄 (共有 49 題) 每次考試都會從一顆星選集中抽 1 提出來考 算是比較能把握的部分，重點筆記整理如下 內容包含題目說明、程式碼、註解說明、解答、考古題統計(下方土黃色日期) 解題使用的程式語言是  JAVA  目前有提供 10 題的試閱 另有提供完整 49 題的完整解答 ( pdf 檔 )， 共 305 頁， 售價 $399 元 ， 若有需要請來信購買 greens2314@gmail.com 推薦閱讀： 建議熟讀 java 基本觀念，與使用 eclipse 練習， 等熟悉之後再到瘋狂程設考試(一定要懂如何查 JAVA API 與使用英漢字典) Java 考試常用的方法或類別 Eclipse 常用小技巧 CPE 一顆星選集： 編號 | 題目名稱 | 歷屆考古題日期 1. Vito's family (CPE10406, UVA10041) 2024/04/23 可與第 40 題一起看 2. Hashmat the brave warrior (CPE10407, UVA10055) 3. Primary Arithmetic (CPE10404, UVA10035) 　 2011/05/25、2023/03/21 4. The 3n + 1 problem (CPE10400, UVA100) 　 2010/06/09 5. You can say 11 (CPE10460, UVA10929) 　 2011/12/20 6. Bangla Numbers (CPE10414, UVA10101) 　 2018/12/18 7. List of Conquests (CPE21924, UVA10420) 　 2019/03/26 　　可與 第 8, 11, 43 題一起看 字元與字串 8. What's Cryptanalysis? (CPE10402, UVA10008) 　　可與 第 7, 11, 43 題一起看 9. Decode the Mad man (CPE10425, UVA10222) 　 2021/10/19 10. Problem J: Summing Digits (CPE10473, UVA11332) ...
Read more »

Visual Studio 自動排版格式化程式碼

圖片
在團隊開發過程中，什麼時候是程式碼瘋狂修改的階段呢， 無非就是Code Review了，有時候卡個幾天或是幾個月都是有可能的， 裡面常出現的comment，每次幾乎都會出現的就是排版的問題， 例如空白多一個少一個，括號還沒換行等等的小瑕疵， 對於心思不夠細膩的人而言，真的十分的惱人 團隊中喜歡將大括號換行， 例如： if(true) {   //code } else {   //code } 那也許有些團隊喜歡： if(true){   //code }else{   //code } 有時候不只括號要不要換行，連else要不要換行都有各自的喜好， 所以有時候要統一使用團隊規定的喜好真的會有眼殘的時候， 自己檢查老半天可能還是有漏網之魚， 但現在不用擔心啦！ 只要使用Format 格式化文件就能為你分憂解勞， 設定方式如下： 編輯 > 進階 > 格式化文件 Visual Studio會根據你的環境設定幫你自動重新排版 設定方式如下： 工具 > 選項 切換到 文字編輯器 > C# >程式碼樣式 > 格式化 > 新行 這邊可以設定很多換行的邏輯， 將對應的項目打勾跟取消勾選，下面的黑色區域會顯示排版的格式， 可根據自己或是團隊的喜好去做調整，即可自動排出你想要的格式囉！ 如果覺得 編輯 > 進階 > 格式化文件 這個選項太難找到， 可以參考這篇文章，將他加入在明顯的工具列區域喔 http://greens2314.blogspot.tw/2017/09/visual-studio-2015.html
Read more »

1. Vito's family (CPE10406, UVA10041) - CPE一顆星解答與說明

圖片
    👉   CPE 一顆星選集列表(49題) 題目說明與解答 題目 Vito 在紐約有非常多的親戚，他希望在紐約找到一間房子，這間房子到每個親戚家的距離總和，要是最少的距離 輸入說明 輸入資料包含很多筆測試資料 每筆測資，包含親戚數量與每位親戚家的街號 親戚數量介於1~499、街道範圍介於1~29999 多位親戚可住在同一條街 輸出說明 針對每筆測試資料，計算出 Vito 到每位親戚家的最短距離總和 街與街的距離 = 街道數字相減取絕對值 解題技巧 中位數 是指一組數字的中間數字；即是有一半數字的值大於中位數，而另一半數字的值小於中位數，其意義是在所有資料中居於中間位置的代表 排序 街道的數字同時代表距離，透過排序，可得知中位數 解題過程 取得輸入 取得資料筆數 根據資料筆數取得親戚數量 根據親戚數量取得街道編號 將街道編號存入陣列中 將親戚的街道位置 由小至大 排序 呼叫 Arrays 類別提供的 sort() 方法 https://docs.oracle.com/javase/7/docs/api/java/util/Arrays.html 假設親戚有 5 位，分別住在：2、5、8、4、2街 排序後為：2 、2、4、5、8街 計算中位數 中位數在陣列中的索引 = 親戚數量 / 2 假設親戚有 5 位( 奇數) ，分別住在：2、5、8、4、2街 排序後為：2 、2、4、5、8街，其中 4 為中位數，中位數有 1 個 5位親戚 / 2 = 2.5，取整數，陣列索引 2 的位置，儲存的是第 4 街 假設親戚有 4位 (偶數) ，分別住在：2、5、8、4街 排序後為：2 、4、5、8街，其中 4 或 5 為中位數， 中位數有 2 個，擇一即可 4位親戚 / 2 = 2，陣列索引 2 的位置，儲存的是 5 街 計算最小距離總和並印出 宣告 sum 變數，統計距離 使用 foreach 將各街道編號 減掉 中位數編號，取絕對值並進行家總 取絕對值要呼叫  Math.abs ()  方法 奇數情況 ： 中位數有 1 個 假設親戚有 5 位   ，分別住在： 2 、2、 4 、5、8 街 中位數 4 ，Vito 住在 4 街，到其他親戚家的距離總和即是最小值 9   偶數情況 ： ...
Read more »