在本文中，我們將主要介紹Dijkstra算法和A*算法，從成本計算的角度出發(fā)，并逐步展開討論。我們將從廣度優(yōu)先搜索開始，然后引入Dijkstra算法，與貪心算法進(jìn)行比較，最終得出A*算法。
成本計算
在路徑規(guī)劃中，成本計算的一個主要因素是距離。距離可以作為一種衡量路徑長短的度量指標(biāo)，通常使用歐幾里得距離、曼哈頓距離或其他合適的距離度量方法來計算。本文主要介紹歐幾里得距離與曼哈頓距離。
廣度優(yōu)先搜索
廣度優(yōu)先搜索（Breadth First Search，BFS ）是一種圖遍歷算法，按照廣度方向逐層遍歷所有可達(dá)節(jié)點。
BFS的基本思想是通過維護(hù)一個隊列，逐層訪問節(jié)點。具體步驟如下：
1.將起始節(jié)點放入隊列中，并標(biāo)記為已訪問。
2.當(dāng)隊列非空時，執(zhí)行以下步驟：
- 從隊列中取出一個節(jié)點，記為當(dāng)前節(jié)點，并標(biāo)記為已訪問。
- 如果該節(jié)點是目標(biāo)節(jié)點，則返回結(jié)果。
- 將當(dāng)前節(jié)點的所有未訪問過的鄰居節(jié)點放入隊列中。
3.如果隊列為空，則表示已經(jīng)遍歷完所有可達(dá)節(jié)點，算法結(jié)束。
算法框圖
