上回我們完成了一項人工智慧的應用--RNN。接下來想用經典的傳教士與食人族的益智問題來說明人工智慧經常用來計算最佳路徑的A*演算法。但在開始介紹A*演算法前，先介紹兩樣同樣常使用於路徑規劃的演算法—廣度優先搜尋(BFS)和深度優先搜尋(DFS)。

廣度優先搜尋(BFS)

廣度優先搜尋(BFS)

圖片來源：https://zh.wikipedia.org/zh-tw/%E5%B9%BF%E5%BA%A6%E4%BC%98%E5%85%88%E6%90%9C%E7%B4%A2

而上圖為一個廣度優先搜尋例子，節點上的數字為節點展開的先後順序。

廣度優先搜尋的概念即為從原點開始做第一層搜尋，接著將節點所有的可能展開節點放至佇列(queue)之中，我們稱為open list，並將原點放置到closed list之中。接著在第二層搜尋要做的事就是將剛剛放進佇列中的所有節點展開所有可能節點，最後把展開的所有節點再放置到open list之中，而已展開的放進closed list之中。如此一直反覆操作，直到open list內沒有節點存在。

深度優先搜尋(DFS)

深度優先搜尋(DFS)

圖片來源：https://zh.wikipedia.org/zh-tw/%E6%B7%B1%E5%BA%A6%E4%BC%98%E5%85%88%E6%90%9C%E7%B4%A2

上圖為一個深度優先搜尋的例子，節點上的數字為節點展開之先後順序。

深度優先搜尋的概念為從原點開始做展開，但這次並不是一次展開所有的可能節點了，這次先展開其中的一個節點，將已展開的節點丟進堆疊(stack)之中，也就是open list，繼續往下展開，一次都只展開一個，直到遇到盡頭便將尾巴的節點放進closed list之中，然後倒退回前一個節點繼續展開其他的可能節點。如此反覆循環，直到open list中沒有節點。