基本款的演算法介紹
在人工智慧中,「搜尋」是解決問題的起點:先把問題建模成節點與路徑,再用搜尋演算法一步步找出答案。本文以概念介紹(不討論程式實作)四種基本搜尋演算法:廣度優先搜尋(BFS)、深度優先搜尋(DFS),以及 DFS 的兩個改良版本——深度限制搜尋(DLS)與迭代加深搜尋(IDDFS)。
為什麼 AI 需要搜尋?
我們希望機器幫我們找到答案,所以建立一個問題之後,我們必須藉由搜尋一些資料幫助我們找到答案。
什麼是廣度優先搜尋(BFS)?
廣度優先搜尋的概念是:選擇一個點做完起點,拜訪起點附近的下一個點,走訪過的元素做標記,直到節點元素全被拜訪過,就會再往下一層直到全部的節點被拜訪過為止。
假設起始點為 0,且每一節點由左至右的順序來搜尋下個節點,則結果為: 0, 1, 2, 3, 4, 5, 6
什麼是深度優先搜尋(DFS)?
深度優先搜尋的概念是:隨意選擇一個方向,並盡可能往這個方向的深度搜尋下去,走訪過的元素做標記,直到遇到死路或者該元素已被拜訪過,就會換另外一條路。
假設起始點為 0,且每一節點由左至右的順序來搜尋下個節點,則結果為: 0, 1, 3, 4, 2, 5, 6
DFS 的問題怎麼解?DLS 與 IDDFS
深度優先搜尋是個盲目的搜尋,有著「一失足成千古恨」的問題——一旦選錯方向,就可能沿著錯誤的路徑一路走到底。所以必須針對這個問題進行解決。
DFS + 限制搜尋的層數 = DLS:深度限制搜尋(Depth-Limited Search)是深度優先搜尋的變體,它設定了搜尋深度的上限。這種方法透過將超過特定深度的節點視為無後繼節點來解決 DFS 可能遇到的無限路徑問題。
DFS + 迭代深度搜尋 = IDDFS:迭代加深深度優先搜尋(Iterative Deepening DFS)結合了 BFS 的完整性和最佳性與 DFS 的空間效率。它透過逐次增加搜尋深度來反覆搜尋,保證了在統一步驟成本下的完整性和最佳性。
重點整理
- BFS 一層一層拜訪節點,保證找得到最淺的解,但需要較多記憶體。
- DFS 沿單一路徑深入,空間效率高,但方向選錯就「一失足成千古恨」。
- DLS 用深度上限避免無限路徑;IDDFS 逐步加深深度,同時保有 BFS 的完整性與 DFS 的空間效率。
常見問題
BFS 和 DFS 差在哪?
BFS(廣度優先搜尋)先把同一層的節點全部拜訪完才往下一層走;DFS(深度優先搜尋)則沿著一個方向盡可能深入,走到死路才回頭換路。BFS 較耗記憶體但能找到最淺的解,DFS 省空間但可能在錯誤路徑上走很深。
什麼是深度限制搜尋(DLS)?
DLS 是 DFS 的變體,為搜尋設定深度上限,把超過該深度的節點視為沒有後繼節點,藉此避免 DFS 陷入無限路徑。
什麼是迭代加深搜尋(IDDFS)?
IDDFS 反覆執行深度逐次加大的 DLS(深度 1、2、3……),結合了 BFS 的完整性、最佳性與 DFS 的空間效率,是在未知深度問題上常用的折衷方案。
Leave a Reply