基于搜索的路徑規(guī)劃算法基本都是一個(gè)套路，它們都是根據(jù)啟發(fā)函數(shù)重備用節(jié)點(diǎn)的集合中來尋找下一個(gè)節(jié)點(diǎn)，不同的啟發(fā)函數(shù)也就有不同的搜索類算法。

搜索類算法是離散化的算法，體現(xiàn)在整個(gè)圖的區(qū)域是由有限個(gè)小方塊區(qū)域組成的。我們暫且把這些小方塊區(qū)域稱為“節(jié)點(diǎn)”。因此，整個(gè)區(qū)域被有限個(gè)節(jié)點(diǎn)填充，且每個(gè)節(jié)點(diǎn)的鄰居節(jié)點(diǎn)為有限個(gè)。

設(shè)置兩個(gè)集合OPEN,CLOSE，OPEN初始狀態(tài)設(shè)為{x_init}，CLOSE 初始狀態(tài)設(shè)為空集。

依據(jù)不同的啟發(fā)式函數(shù)，從open集中選擇一個(gè)點(diǎn)加入到close集中，然后拓展open集，如上圖，右下角的某個(gè)點(diǎn)被某種啟發(fā)式函數(shù)選中，加入到close集中，并相繼拓展open集

下面介紹下搜索類算法的前進(jìn)過程：

當(dāng)上述偽碼退出循環(huán)后，沿著x_goal的父節(jié)點(diǎn)往前回溯極為路徑

各搜索類算法的區(qū)別在于第三行啟發(fā)函數(shù)的類型的不同，導(dǎo)致連接的節(jié)點(diǎn)不同。