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