在本文中,我們將主要介紹Dijkstra算法和A*算法,從成本計(jì)算的角度出發(fā),并逐步展開討論。我們將從廣度優(yōu)先搜索開始,然后引入Dijkstra算法,與貪心算法進(jìn)行比較,最終得出A*算法。
成本計(jì)算
在路徑規(guī)劃中,成本計(jì)算的一個(gè)主要因素是距離。距離可以作為一種衡量路徑長短的度量指標(biāo),通常使用歐幾里得距離、曼哈頓距離或其他合適的距離度量方法來計(jì)算。本文主要介紹歐幾里得距離與曼哈頓距離。




廣度優(yōu)先搜索
廣度優(yōu)先搜索(Breadth First Search,BFS )是一種圖遍歷算法,按照廣度方向逐層遍歷所有可達(dá)節(jié)點(diǎn)。
BFS的基本思想是通過維護(hù)一個(gè)隊(duì)列,逐層訪問節(jié)點(diǎn)。具體步驟如下:
1.將起始節(jié)點(diǎn)放入隊(duì)列中,并標(biāo)記為已訪問。
2.當(dāng)隊(duì)列非空時(shí),執(zhí)行以下步驟:
- 從隊(duì)列中取出一個(gè)節(jié)點(diǎn),記為當(dāng)前節(jié)點(diǎn),并標(biāo)記為已訪問。
- 如果該節(jié)點(diǎn)是目標(biāo)節(jié)點(diǎn),則返回結(jié)果。
- 將當(dāng)前節(jié)點(diǎn)的所有未訪問過的鄰居節(jié)點(diǎn)放入隊(duì)列中。
3.如果隊(duì)列為空,則表示已經(jīng)遍歷完所有可達(dá)節(jié)點(diǎn),算法結(jié)束。
算法框圖
