路徑導(dǎo)航與啟發(fā)式搜索

問(wèn)題介紹

介紹需要求解的問(wèn)題

隨著生活水平的不斷發(fā)展，我們出行的需求越來(lái)越高，需要到達(dá)的目的地也越來(lái)越遠(yuǎn)，很多地方都是我們不熟悉的地方。在那些地方怎么才能從一個(gè)點(diǎn)到達(dá)另一個(gè)點(diǎn)？在這么多可能的路徑中哪一條才是最短的？或者說(shuō)，車(chē)流量最少的、速度最快的、花費(fèi)時(shí)間最少的、途徑收費(fèi)項(xiàng)目最少的……

這樣的問(wèn)題，在現(xiàn)實(shí)生活中，我們成為路徑導(dǎo)航問(wèn)題，或者是尋路問(wèn)題等。

模型的建立

現(xiàn)在把問(wèn)題抽象成一個(gè)長(zhǎng)、寬都是100的正方形，在這個(gè)正方形中依次排布了100×100的單位邊長(zhǎng)為1的小正方形，小正方形表示的是每個(gè)點(diǎn)。用2種不同的顏色表示每個(gè)點(diǎn)的含義：例如，黑色表示這是一個(gè)障礙物，不能通行；白色表示這個(gè)點(diǎn)是可以通行的道路。

不失一般性，上面的模型也適用于現(xiàn)實(shí)中的導(dǎo)航。100×100的正方形，可以類(lèi)似地?cái)U(kuò)展成200×200、1000×800。同時(shí)，道路就用白色的點(diǎn)表示，建筑物是黑色的點(diǎn)，河流是黑色的點(diǎn)，但是河流上的橋梁是白色的點(diǎn)……

在這樣一張地圖上，給定一個(gè)起點(diǎn)，給定一個(gè)終點(diǎn)，需要找到一條從起點(diǎn)到終點(diǎn)的合法路徑，并盡可能使得這條路是最短的。我們定義最短，意思是經(jīng)過(guò)的步數(shù)最少，此時(shí)每經(jīng)過(guò)一個(gè)小正方形，權(quán)重加1。

不失一般性，這樣找到的路徑在現(xiàn)實(shí)中也是有意義的。例如，在上面的求解中，每經(jīng)過(guò)一個(gè)小正方形，權(quán)重加1，如果在現(xiàn)實(shí)生活中，我們想要找到一條花費(fèi)時(shí)間最少的路（盡管這條路不是最短的），那么我們可以根據(jù)不同路口的車(chē)流量不同，對(duì)相應(yīng)的小正方形賦予不同的權(quán)重；又例如，如果我們不想走高速，那么可以把高速路對(duì)應(yīng)的小正方形的花銷(xiāo)定義為無(wú)窮大……

為什么要采用我們介紹的方法求解

很容易想到的是，我們生活的世界如此龐大，“條條大路通羅馬”，不可能枚舉出所有的可能的路徑，然后排個(gè)序，找到最短的。

甚至，就是對(duì)于上面抽象出的這個(gè)100×100的小正方形，其中存在的路徑可能也太多了，即使在計(jì)算機(jī)的幫助下，枚舉所有可能，然后找到最短路，這效率也非常低。

所以我們需要用到啟發(fā)式算法、局部搜索算法。

啟發(fā)式搜索是利用問(wèn)題擁有的啟發(fā)信息來(lái)引導(dǎo)搜索，達(dá)到減少搜索范圍、降低問(wèn)題復(fù)雜度的目的。

啟發(fā)式搜索中，定義了一個(gè)評(píng)價(jià)函數(shù)對(duì)各個(gè)子結(jié)點(diǎn)進(jìn)行計(jì)算，其目的就是用來(lái)估算出“有希望”的結(jié)點(diǎn)來(lái)。

要對(duì)OPEN表進(jìn)行排序的時(shí)候，就按照這種“希望”進(jìn)行排序。最有希望通向目標(biāo)結(jié)點(diǎn)的待擴(kuò)展結(jié)點(diǎn)會(huì)被優(yōu)先擴(kuò)展。

程序設(shè)計(jì)與算法分析

一般圖搜索框架重塑

在這個(gè)問(wèn)題中，采用的算法框架仍舊是一般圖搜索框架，這在上一次作業(yè)《皇后問(wèn)題》中已經(jīng)給出了詳細(xì)的算法說(shuō)明和完整代碼。

這里只簡(jiǎn)要重塑這個(gè)框架。

while (true) {
    if (open.isEmpty())
        return false;
    Node currentNode = open.poll();
    closed.add(currentNode);
    if (isTarget(currentNode)) {
        latest = currentNode;
        return true;
    }
    ArrayList<Node> m = expand(currentNode);
    if (m.isEmpty()) 
        continue;
    else 
        setPointer(m, currentNode);
}

需要修改的地方是設(shè)置父節(jié)點(diǎn)時(shí)候，要注意對(duì)OPEN表和CLOSED表的維護(hù)，其中對(duì)OPEN表排序需要按照啟發(fā)式函數(shù)的評(píng)估值來(lái)排序。

由于每次都是評(píng)估值最小的排在最前面，所以其實(shí)可以在加入到OPEN表的時(shí)候就直接加入到恰當(dāng)?shù)奈恢?，于是，OPEN表可以用優(yōu)先級(jí)隊(duì)列PriorityQueue來(lái)實(shí)現(xiàn)。

if (!open.contains(node) && !closed.contains(node)) {
    
} else if (open.contains(node)) {
    if (newDissipative < node.getDissipative()) {
        
    }
} else if (newDissipative < node.getDissipative()) {
    
}

數(shù)據(jù)存放形式與數(shù)據(jù)結(jié)構(gòu)定義

? OPEN表：用于存放剛生成的節(jié)點(diǎn)

? CLOSED表：用于存放將要擴(kuò)展或已擴(kuò)展的節(jié)點(diǎn)

? Node：表示結(jié)點(diǎn)

? parent：指向父節(jié)點(diǎn)

數(shù)據(jù)域成員聲明

? source：起點(diǎn)

? terminal：終點(diǎn)

? maze：地圖，值為true表示可以通行，值為false表示這是障礙物

? result：最終找到的路徑，以鏈表的形式返回

? progress：找路期間曾經(jīng)試圖訪(fǎng)問(wèn)過(guò)的點(diǎn)，以鏈表的形式返回

方法聲明

/**
 * 評(píng)估函數(shù)的h(x)的值
 * @param source 起點(diǎn)
 * @param terminal 終點(diǎn)
 * @param parent 當(dāng)前的點(diǎn)的父親
 * @param node 當(dāng)前的點(diǎn)
 * @return h(x)的值
 */
private double heuristic(Node source, Node terminal, Node parent, Node node) 

/**
 * 獲得給定的點(diǎn)的鄰居，鄰居的定義是周?chē)?個(gè)點(diǎn)
 * @param node 給定的點(diǎn)
 * @return 給定點(diǎn)的鄰居
 */
private ArrayList<Node> getNeighbours(Node node) 

/**
 * 判斷當(dāng)前點(diǎn)是不是合法，合法的定義是不超過(guò)地圖邊界，且不是障礙物
 * @param x 橫坐標(biāo)
 * @param y 縱坐標(biāo)
 * @return 如果合法，返回true，否則，false
 */
private boolean isValid(int x, int y) 

/**
 * 判斷當(dāng)前點(diǎn)是不是終點(diǎn)
 * @param node 當(dāng)前點(diǎn)
 * @return 如果已經(jīng)到了終點(diǎn)，返回true，否則，false
 */
private boolean isTarget(Node node) 

/**
 * 以鏈表的形式返回最終找到的路徑
 * @return 最終找到的路徑
 */
public LinkedList<Node> getResult() 

/**
 * 以鏈表的形式獲得曾經(jīng)試圖訪(fǎng)問(wèn)過(guò)的點(diǎn)
 * @return 曾經(jīng)試圖訪(fǎng)問(wèn)過(guò)的點(diǎn)
 */
public LinkedList<Node> getProgress()

圖形用戶(hù)界面相關(guān)、交互相關(guān)

為了方便程序的調(diào)試，以及為了比較三種算法之間的優(yōu)劣，我順手寫(xiě)了圖形用戶(hù)界面。

因?yàn)檫@部分內(nèi)容與本次作業(yè)的核心算法關(guān)系不大，所以下面不再詳細(xì)給出這部分的數(shù)據(jù)定義、算法描述，只簡(jiǎn)要做出如下說(shuō)明：

黑色：障礙，表示不能通過(guò)的地方

白色：道路，表示可以走的地方

紅色：最終的路徑

藍(lán)色：曾經(jīng)試圖尋找的點(diǎn)，藍(lán)色區(qū)域越大，說(shuō)明搜索效率越低，找了那么多才找到這條路，藍(lán)色區(qū)域越小說(shuō)明搜索效率越高

算法

題目描述中有一些地方有歧義

為了更加清晰地表示下面的3種算法，做如下約定：

1．輸入一定合法

不論是地圖還是起點(diǎn)終點(diǎn)，輸入的格式和數(shù)據(jù)一定合法，不存在非法數(shù)據(jù)或者錯(cuò)誤格式。

2．下標(biāo)從0開(kāi)始

所描述的點(diǎn)，例如(5,4)表示的是第6行第5列。

3．8個(gè)方向是等價(jià)的

不存在“上、下、左、右”比“左上、左下、右上、右下”要優(yōu)先的情況

4．走1步的花銷(xiāo)定義為1

不論這一步是水平還是垂直走，還是斜著走，只要是走1步，花銷(xiāo)就是1

從(0,0)走到(1,1)，是右下，這里花銷(xiāo)不是，仍取1

5．從起點(diǎn)到終點(diǎn)的最優(yōu)路線(xiàn)只看花銷(xiāo)

只要花銷(xiāo)是一樣的，那么這幾條路只是走法上的不同，在優(yōu)劣程度上認(rèn)為是一樣

例如，下面2種走法，看作是等價(jià)的，區(qū)別只是走法的不同，而沒(méi)有優(yōu)劣之分，因?yàn)樗麄兊幕ㄤN(xiāo)都是5

最短路徑算法

算法描述

首先看Dijkstra算法的描述：

這個(gè)算法是通過(guò)為每個(gè)頂點(diǎn) v 保留目前為止所找到的從s到v的最短路徑來(lái)工作的。初始時(shí)，原點(diǎn) s 的路徑權(quán)重被賦為 0 （d[s] = 0）。若對(duì)于頂點(diǎn) s 存在能直接到達(dá)的邊（s,m），則把d[m]設(shè)為w（s, m）,同時(shí)把所有其他（s不能直接到達(dá)的）頂點(diǎn)的路徑長(zhǎng)度設(shè)為無(wú)窮大，即表示我們不知道任何通向這些頂點(diǎn)的路徑（對(duì)于所有頂點(diǎn)的集合 V 中的任意頂點(diǎn) v， 若 v 不為 s 和上述 m 之一， d[v] = ∞）。當(dāng)算法結(jié)束時(shí)，d[v] 中存儲(chǔ)的便是從 s 到 v 的最短路徑，或者如果路徑不存在的話(huà)是無(wú)窮大?！摱我米訵ikipedia

那么就可以得到算法的主要思想。

首先從起點(diǎn)出發(fā)，試著往周?chē)?個(gè)點(diǎn)走，這時(shí)候這8個(gè)點(diǎn)都是1步就能到達(dá)的。之后，取這8個(gè)點(diǎn)的其中一個(gè)（因?yàn)檫@8個(gè)點(diǎn)距離起點(diǎn)都是1，所以都是最短的），繼續(xù)找它的周?chē)?個(gè)點(diǎn)，那么這些點(diǎn)的都是距離起點(diǎn)需要2步才能到達(dá)的。

每次都取待擴(kuò)展的結(jié)點(diǎn)中，距離起點(diǎn)最短的結(jié)點(diǎn)往外擴(kuò)展，這樣搜索出來(lái)的路可以保證是最短路徑。

在算法的實(shí)現(xiàn)過(guò)程中，如果一個(gè)點(diǎn)周?chē)?個(gè)點(diǎn)，有障礙物，或者已經(jīng)超出了地圖的邊界，那么直接丟棄。

偽代碼表示

于是，可以得到Dijkstra算法的偽代碼描述。

對(duì)于圖G中的每一個(gè)點(diǎn)V
初始化d[v] = Infinity，previous[v] = undefined   
d[s] = 0
S = empty
Q = 所有的V
while Q 非空
u = 取出(Q)中最小的點(diǎn)
把u加入到S
對(duì)于u能夠走到的每一個(gè)v
if d[v] > d[u] + w(u,v)
d[v] = d[u] + w(u,v)，previous[v] = u

流程圖

從這里可以看到，如果用一般圖搜索框架來(lái)實(shí)現(xiàn)Dijkstra算法，用OPEN表存放所有的待擴(kuò)展的結(jié)點(diǎn)，每次取出最小值，就是一個(gè)以當(dāng)前“最短值”作為標(biāo)準(zhǔn)的優(yōu)先級(jí)隊(duì)列，而每次取出的u，相當(dāng)于是更新父節(jié)點(diǎn)，并且維護(hù)OPEN表和CLOSED表。

image-20210328201448802

image-20210328201502641

那么對(duì)于一般圖搜索框架，需要修改以下部分。

for (Node node : m) {
    double newDissipative = 計(jì)算出新的評(píng)估值;
    if (!open.contains(node) && !closed.contains(node)) {
        node.setDissipative(newDissipative);
        open.add(node);
        node.setParent(parent);
    } else if (open.contains(node)) {
        if (newDissipative < node.getDissipative()) {
            node.setDissipative(newDissipative);
            node.setParent(parent);
        }
    } else if (newDissipative < node.getDissipative()) {
        node.setDissipative(newDissipative);
        node.setParent(parent);
        closed.remove(node);
        open.add(node);
    }
}

在這里，新的評(píng)估值就是 parent.getDissipative()+1。

A*算法

算法描述

啟發(fā)式搜索算法A，一般簡(jiǎn)稱(chēng)為A算法，是一種典型的啟發(fā)式搜索算法。

其基本思想是：定義一個(gè)評(píng)價(jià)函數(shù)f，對(duì)當(dāng)前的搜索狀態(tài)進(jìn)行評(píng)估，找出一個(gè)最有希望的結(jié)點(diǎn)來(lái)擴(kuò)展。

評(píng)價(jià)函數(shù)的形式如下：

當(dāng)

在算法的評(píng)價(jià)函數(shù)中，使用的啟發(fā)函數(shù)是處在的下界范圍，即滿(mǎn)足時(shí)，則把這個(gè)算法稱(chēng)為算法。

算法實(shí)際上是分支界限和動(dòng)態(tài)規(guī)劃原理及使用下界范圍的相結(jié)合的算法。

首先令就是最短路徑算法中的評(píng)估值。也就是說(shuō)，始終是距離起點(diǎn)的距離。

事實(shí)上，最短路徑算法是極端情況下的算法，這時(shí)候，一定滿(mǎn)足下界范圍條件，所以一定能找到最佳路徑（只要問(wèn)題有解），這里的最佳路徑指的是最短路徑。

下面逐一考慮。

啟發(fā)式函數(shù)的選取

標(biāo)準(zhǔn)啟發(fā)式函數(shù)可以采用曼哈頓距離。

dx = abs(node.x - goal.x)
dy = abs(node.y - goal.y)
h(n) = dx + dy

相鄰方塊之間的最低成本顯然為1，這是因?yàn)槲覀兛梢猿?個(gè)方向前進(jìn)，從上文的約定中，可以發(fā)現(xiàn)，8個(gè)方向是等價(jià)的。

不失一般性，如果認(rèn)為斜著走比橫平豎直地走要花費(fèi)更大的成本，那么對(duì)應(yīng)的，只是相差一個(gè)常系數(shù)D，例如，這個(gè)為。在這里，為了簡(jiǎn)化問(wèn)題，取。

更進(jìn)一步，也可以使用對(duì)角線(xiàn)距離。

地圖允許對(duì)角線(xiàn)移動(dòng)，所以需要一個(gè)不同的啟發(fā)式函數(shù)。

dx = abs(node.x - goal.x)
dy = abs(node.y - goal.y)
h(n) = D * (dx + dy) + (D2 - 2 * D) * min(dx, dy)

首先計(jì)算不能走對(duì)角線(xiàn)的時(shí)候需要走的距離，然后減去走對(duì)角線(xiàn)可以省下的距離。

當(dāng)的時(shí)候，上面這個(gè)等式的值其實(shí)就是切比雪夫距離，而當(dāng)且時(shí)，上面這個(gè)等式的值其實(shí)就是可視距離。

在我的算法中，我將會(huì)采用作為啟發(fā)式函數(shù)，也就是可視距離。

多思考一步。

如果地圖允許以任意角度移動(dòng)，而不僅限于那8個(gè)方向，那么歐幾里得距離也是可以作為啟發(fā)式函數(shù)的。

dx = abs(node.x - goal.x)
dy = abs(node.y - goal.y)
h(n) = D * sqrt(dx * dx + dy * dy)

但是，如果是這種情況，那么可能無(wú)法直接使用A*，因?yàn)間(n)與h(n)不匹配。由于歐幾里德距離比曼哈頓或?qū)蔷嚯x短，所以仍然會(huì)得到最短路徑，但A*的運(yùn)行時(shí)間會(huì)更長(zhǎng)。

——該段引用自斯坦福大學(xué)GameProgramming - Heuristics

至此，我已經(jīng)找到了啟發(fā)式函數(shù)的計(jì)算方法。

但是在查閱相關(guān)文獻(xiàn)的時(shí)候，我看到了進(jìn)一步的優(yōu)化方法，所以我認(rèn)為有必要在這里提及一下斯坦福大學(xué)GameProgramming – Heuristics中提到的一個(gè)Breaking ties*的算法。

heuristic *= (1.0 + p)
p <(minimum cost of taking one step)/(expected maximum path length)

這略微打破了啟發(fā)式的“可接受性”，但在游戲中它幾乎從不重要。、

這種“破壞”的推動(dòng)的結(jié)果是，A*探索的地圖比以前少得多。

當(dāng)然，如果有障礙，它仍然需要探索以找到解決方案，但，在障礙通過(guò)后，A *探索的很少。

image-20210328202154806

除了上面提到的方法，還可以用另一種方法來(lái)計(jì)算“Breaking Ties”。

dx1 = current.x - goal.x
dy1 = current.y - goal.y
dx2 = start.x - goal.x
dy2 = start.y - goal.y
cross = abs(dx1*dy2 - dx2*dy1)
heuristic += cross*0.001

但是考慮到這次作業(yè)的地圖規(guī)模比較小，是100×100，而且事實(shí)上，我本地測(cè)試過(guò)斯坦福大學(xué)的這種“Breaking Ties”的優(yōu)化，但是效果很不明顯，并沒(méi)有比最基本的A*算法快了多少（雖然確實(shí)少搜索了那么一些格子，但是數(shù)量差別不大），所以最終我沒(méi)有采用這種優(yōu)化方法。

偽代碼表示

OPEN=(s)
f(s)=g(s)+h(s)
LOOP:
if OPEN為空 return FAIL
取出OPEN表的第一個(gè)元素n
if n是目標(biāo) return SUCCESS
從OPEN表移除n，加入到CLOSED表
擴(kuò)展n為{m}
計(jì)算f(n,mi)=g(n,mi)+h(mi)
標(biāo)記m到n的指針
mj加入到OPEN表
if f(n,mk)<f(mk) f(mk)=f(n,mk)
if f(n,ml)<f(ml) f(ml)=f(n,ml)并重新放回OPEN表
OPEN表按照f(shuō)值從小到大排序（如果使用優(yōu)先級(jí)隊(duì)列自動(dòng)完成，這一步省略）
GO LOOP

局部搜索

局部搜索算法是從爬山法改進(jìn)而來(lái)。

局部搜索算法中最基本的思想，即在搜索過(guò)程中，始終向著離目標(biāo)最接近的方向搜索。

局部搜索從一個(gè)初始解出發(fā)，然后搜索解的鄰域，如有更優(yōu)的解則移動(dòng)至該解并繼續(xù)執(zhí)行搜索，否則返回當(dāng)前解。局部搜索的優(yōu)點(diǎn)是簡(jiǎn)單、靈活及易于實(shí)現(xiàn)，缺點(diǎn)是容易陷入局部最優(yōu)且解的質(zhì)量與初始解和鄰域的結(jié)構(gòu)密切相關(guān)。常見(jiàn)的改進(jìn)方法有模擬退火、禁忌搜索等。

——該段引用自Wikipedia

下面從最簡(jiǎn)單的局部搜索來(lái)分析。

第1種方案，每次都取最小的走，這個(gè)算最基本的局部搜索。

第2種方案，也是只看，但是有一定的概率取差的，這個(gè)算是局部搜索的改進(jìn)。

考慮一種極端情況，有一定概率取差的，這個(gè)概率無(wú)限趨于0，也就是只取比自己好的，不會(huì)取比自己查的，就回到了第1種方案。

第3種也是只看，但有一定概率取差的，而且這個(gè)概率會(huì)變。

模擬退火就屬于這種方案。當(dāng)溫度較高的時(shí)候，接受劣解的概率比較大，在初始高溫下，幾乎以100%的概率接受劣解。隨著溫度的下降，接受劣解的概率逐漸減少，直到溫度趨于0時(shí)，接受劣解的概率也同時(shí)趨于0。這樣將有利于算法從局部最優(yōu)解中跳出，求得問(wèn)題的全局最優(yōu)解。

在實(shí)際的代碼過(guò)程中，我經(jīng)過(guò)測(cè)試，發(fā)現(xiàn)對(duì)于100×100的規(guī)模的圖，因?yàn)槠瘘c(diǎn)終點(diǎn)已經(jīng)給定，所以直接使用第1種方案就已經(jīng)得到了令人滿(mǎn)意的結(jié)果。

相比之下，第2和第3種方案因?yàn)橐肓穗S機(jī)的過(guò)程，計(jì)算量加大，且不可控性加大，對(duì)求解這類(lèi)問(wèn)題并沒(méi)有顯著性的改善（雖然在求解超大規(guī)模問(wèn)題的時(shí)候能夠提高效率），因此，最后我并沒(méi)有采用任何優(yōu)化的算法進(jìn)行局部搜索，我只用了最原始的方案。

實(shí)驗(yàn)結(jié)果

程序運(yùn)行說(shuō)明

image-20210328202331121

gui包內(nèi)的三個(gè)類(lèi)都是處理圖形用戶(hù)界面的，與尋路部分的核心代碼無(wú)關(guān)。

handler包內(nèi)的ConstanValue是一些常量的定義，Darw類(lèi)負(fù)責(zé)繪圖，InputHandler負(fù)責(zé)交互用戶(hù)的輸入。

main包的代碼是核心代碼，Node是輔助類(lèi)，用來(lái)記錄每個(gè)點(diǎn)的信息，Main類(lèi)是主程序部分。

程序運(yùn)行的入口是navigator項(xiàng)目的main包的Main類(lèi)的main()方法。

程序運(yùn)行后會(huì)給出Prompt，只要按照提示依次輸入，以回車(chē)結(jié)束就可以了。

image-20210328202345627

如果程序能夠找到解，會(huì)在圖形用戶(hù)界面繪制這樣一條路徑。

GUI界面中，黑色代表障礙物，白色代表可以走的路，藍(lán)色代表曾經(jīng)試圖搜索過(guò)的區(qū)域，紅色代表最后的路徑。

image-20210328202354705

如果不存在這樣一條路徑，程序會(huì)給出提示。

img

需要注意的是，地圖文件名區(qū)分大小寫(xiě)，且需要與程序處于同一個(gè)工作目錄，除非給定的是絕對(duì)路徑，而不單純是文件名。

- 請(qǐng)確保輸入文件位于程序的工作目錄

- 即Project目錄，而非bin（Release、Debug）目錄

- 除非修改過(guò)配置，那么服從配置文件的工作目錄

- 請(qǐng)確保文件是UTF-8格式編碼的

- 請(qǐng)確保文件具有讀取權(quán)限

- 請(qǐng)確保文件名大小寫(xiě)正確

正確性驗(yàn)證

首先考慮極端的情況。

在一張完全空白的圖上，即沒(méi)有任何障礙物的時(shí)候，應(yīng)該無(wú)論如何都能找到一條路徑。

而且顯然的是，這條路一定會(huì)盡可能朝著起點(diǎn)終點(diǎn)的連線(xiàn)走斜著過(guò)去，直到45°角走到橫平豎直的時(shí)候，再直接過(guò)去。

image-20210328202513178

image-20210328202519149

再考慮具有障礙物的情況。

image-20210328202529097

image-20210328202534923

顯然也是正確的，首先往目標(biāo)的方向走，然后遇到障礙物了，就貼著障礙物走，繞過(guò)障礙物以后，直接往目標(biāo)方向走。

注意一個(gè)細(xì)節(jié)。

image-20210328202543993

在這一部分，路徑?jīng)]有傻傻的直接朝著目標(biāo)方向走，雖然繼續(xù)往右是距離目標(biāo)最近的。

但是繼續(xù)往右，3步以后就會(huì)撞到障礙物，然后不得不繼續(xù)向下，那么這時(shí)候就會(huì)多很多沒(méi)用的步驟。

我的程序，在一直往右走到某個(gè)點(diǎn)以后，非常聰明地發(fā)現(xiàn)繼續(xù)向右并不是最好的選擇，而這個(gè)時(shí)候右下方可以有效地走到障礙物的邊緣，然后繼續(xù)。

同樣的，繞過(guò)障礙物以后，也有類(lèi)似的細(xì)節(jié)。

image-20210328202552721

這兩個(gè)細(xì)節(jié)也同時(shí)說(shuō)明了，啟發(fā)式函數(shù)，我選的是很好的。

最后考慮一種無(wú)解的情況。

三種算法都能規(guī)避這種情況，正常判斷出無(wú)解。

image-20210328202600358

一般情況，以老師發(fā)的測(cè)試數(shù)據(jù)的0.1.txt和0.55.txt，分別選取一個(gè)代表。

image-20210328202608480

image-20210328202613628

image-20210328202617843

image-20210328202621923

三種算法的比較

下面是不同的地圖下，3中算法的路徑圖，可以發(fā)現(xiàn)，紅色線(xiàn)條的路徑找的都是一樣的，關(guān)鍵的不同點(diǎn)在于藍(lán)綠色部分的大小不一樣，也就是搜索的空間（效率）有高低。

	最短路徑算法	A*算法	局部搜索
empty	image-20210328202653596	image-20210328202659101	image-20210328202706779
block	image-20210328202711532	image-20210328202716408	image-20210328202722607
0.1	img	img	img
0.55	img	img	img

在empty圖中，我是從(10,10)走到(30,30)，3種算法都是花費(fèi)21步。

但是明顯的是，A*算法比最短路徑算法少了很多搜索范圍，因?yàn)樗M可能往目標(biāo)方向走。

而局部搜索甚至不考慮距離起點(diǎn)的距離，一昧的往終點(diǎn)走，它的搜索空間就是最終答案，一點(diǎn)都不浪費(fèi)。

在block圖中我是從(6,0)走到(24,60)，藍(lán)綠色的區(qū)域大小區(qū)別更明顯了。

最短路徑算法幾乎查完了整張圖才能找到終點(diǎn)。

A*算法找的就明顯少了很多，只有一小塊區(qū)域。

而局部搜索甚至更高效，直接往目的地方向去，只在障礙物的邊緣多找了那么一小圈。

一般情況下，也可以看出，最短路徑的搜索效率是最差的。

即使面對(duì)如此多的障礙物，A*搜索的搜索區(qū)域也比最短路徑少，而局部搜索就更少。

image-20210328202811833

image-20210328202815965

程序源代碼

核心代碼

package main;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.PriorityQueue;

import handler.ConstantValue;
import handler.Draw;
import handler.InputHandler;;

public class Main {

    public static void main(String[] args) throws Exception {
        // 處理輸入
        InputHandler inputHandler = new InputHandler();
        inputHandler.input();
        boolean[][] maze = inputHandler.getMaze();
        Node source = inputHandler.getSource();
        Node terminal = inputHandler.getTerminal();
        // 開(kāi)始搜索
        Search s = new Search(source, terminal, maze);
        if (s.start()) {
            // 找到結(jié)果，就獲得結(jié)果，并繪制，然后輸出
            LinkedList<Node> progress = s.getProgress();
            LinkedList<Node> result = s.getResult();
            Draw.draw(maze, progress, result);
            System.out.println("總共走了 " + result.size() + " 步。");
            System.out.println("找到路徑，請(qǐng)查看圖形用戶(hù)界面。");
        } else {
            // 找不到結(jié)果，就是答案不存在
            // Draw.draw(maze, new LinkedList<Node>(), new LinkedList<Node>());
            System.out.println("不存在這樣一條路徑！");
        }

    }
}

class Search {

    private Node source; // 起點(diǎn)
    private Node terminal; // 終點(diǎn)
    private boolean[][] maze = new boolean[ConstantValue.SIZE][ConstantValue.SIZE]; // 迷宮

    public Search(Node source, Node terminal, boolean[][] maze) {
        this.source = source;
        this.terminal = terminal;
        this.maze = maze;
    }

    PriorityQueue<Node> open = new PriorityQueue<Node>(); // OPEN表
    LinkedList<Node> closed = new LinkedList<Node>(); // CLOSED表
    LinkedList<Node> progress = new LinkedList<Node>(); // 哪些區(qū)域是被搜索過(guò)的，用來(lái)比較算法優(yōu)劣
    Node latest;

    public boolean start() {
        /*
         * 起點(diǎn)的權(quán)重定義為0 事實(shí)上，因?yàn)槠瘘c(diǎn)一定在路徑中，所以無(wú)所謂它的g(x)和h(x)到底是什么，直接定義為0就好了
         * 
         */
        source.setDissipative(0);

        open.add(source);

        while (true) {
            if (open.isEmpty()) {
                return false;
            }
            Node currentNode = open.poll();
            progress.add(currentNode);
            closed.add(currentNode);
            if (isTarget(currentNode)) {
                latest = currentNode;
                return true;
            }
            ArrayList<Node> m = expand(currentNode);
            if (m.isEmpty()) {
                continue;
            } else {
                setPointer(m, currentNode);
            }
        }
    }

    private void setPointer(ArrayList<Node> m, Node parent) {
        for (Node node : m) {

            double newDissipative;

            /*
             * 三種算法的區(qū)別只是這里的評(píng)估值不一樣
             */

            // // 最短路徑算法
            // newDissipative = parent.getDissipative() + 1;

            // A*算法
            newDissipative = parent.getDissipative() + 1;
            newDissipative += heuristic(source, terminal, parent, node);

            // // 局部搜索算法
            // newDissipative = heuristic(source, terminal, parent, node);

            // 如果不在OPEN表，且不在CLOSED表，更新評(píng)估值，設(shè)置父結(jié)點(diǎn)，然后加入OPEN表
            if (!open.contains(node) && !closed.contains(node)) {
                node.setDissipative(newDissipative);
                open.add(node);
                node.setParent(parent);
            } else if (open.contains(node)) {
                // 如果在OPEN表中，且新的評(píng)估值小于舊的評(píng)估值，更新評(píng)估值，然后更新父結(jié)點(diǎn)
                if (newDissipative < node.getDissipative()) {
                    node.setDissipative(newDissipative);
                    node.setParent(parent);
                }
            } else if (newDissipative < node.getDissipative()) {
                // 不然就是在CLOSED表中，如果新的評(píng)估值小于舊的評(píng)估值，然后更新父結(jié)點(diǎn)，然后從CLOSED表中移除并加入OPEN表
                node.setDissipative(newDissipative);
                node.setParent(parent);
                closed.remove(node);
                open.add(node);
            }
        }
    }

    /**
     * 評(píng)估函數(shù)的h(x)的值
     * 
     * @param source
     *            起點(diǎn)
     * @param terminal
     *            終點(diǎn)
     * @param parent
     *            當(dāng)前的點(diǎn)的父親
     * @param node
     *            當(dāng)前的點(diǎn)
     * @return h(x)的值
     */
    private double heuristic(Node source, Node terminal, Node parent, Node node) {
        return Math.abs(terminal.x - node.x) + Math.abs(terminal.y - node.y)
                + (Math.sqrt(2) - 2) * Math.min(Math.abs(terminal.x - node.x), Math.abs(terminal.y - node.y));
    }

    private ArrayList<Node> expand(Node node) {
        return getNeighbours(node);
    }

    /**
     * 獲得給定的點(diǎn)的鄰居，鄰居的定義是周?chē)?個(gè)點(diǎn)
     * 
     * @param node
     *            給定的點(diǎn)
     * @return 給定點(diǎn)的鄰居
     */
    private ArrayList<Node> getNeighbours(Node node) {
        ArrayList<Node> m = new ArrayList<Node>();
        for (int i = -1; i <= 1; ++i) {
            for (int j = -1; j <= 1; ++j) {
                if (i == 0 && j == 0)
                    continue;
                int x = node.x + i;
                int y = node.y + j;

                if (isValid(x, y)) {
                    m.add(new Node(x, y));
                }
            }
        }
        return m;
    }

    /**
     * 判斷當(dāng)前點(diǎn)是不是合法，合法的定義是不超過(guò)地圖邊界，且不是障礙物
     * 
     * @param x
     *            橫坐標(biāo)
     * @param y
     *            縱坐標(biāo)
     * @return 如果合法，返回true，否則，false
     */
    private boolean isValid(int x, int y) {
        if (x < 0 || x >= ConstantValue.SIZE || y < 0 || y >= ConstantValue.SIZE)
            return false;
        return (maze[x][y]);
    }

    /**
     * 判斷當(dāng)前點(diǎn)是不是終點(diǎn)
     * 
     * @param node
     *            當(dāng)前點(diǎn)
     * @return 如果已經(jīng)到了終點(diǎn)，返回true，否則，false
     */
    private boolean isTarget(Node node) {
        return (node.x == terminal.x && node.y == terminal.y);
    }

    /**
     * 以鏈表的形式返回最終找到的路徑
     * 
     * @return 最終找到的路徑
     */
    public LinkedList<Node> getResult() {
        LinkedList<Node> result = new LinkedList<Node>();
        Node node = latest;
        while (node != null) {
            result.addFirst(node);
            node = node.getParent();
        }
        return result;
    }

    /**
     * 以鏈表的形式獲得曾經(jīng)試圖訪(fǎng)問(wèn)過(guò)的點(diǎn)
     * 
     * @return 曾經(jīng)試圖訪(fǎng)問(wèn)過(guò)的點(diǎn)
     */
    public LinkedList<Node> getProgress() {
        return progress;
    }
}

package main;

import java.awt.Point;

public class Node extends Point implements Comparable<Node> {

    private static final long serialVersionUID = 1L;

    private Node parent;
    private double dissipative;

    public double getDissipative() {
        return dissipative;
    }

    public void setDissipative(double dissipative) {
        this.dissipative = dissipative;
    }

    public Node getParent() {
        return parent;
    }

    public void setParent(Node parent) {
        this.parent = parent;
    }

    public Node(int x, int y) {
        super(x, y);
        parent = null;
    }

    @Override
    public int compareTo(Node o) {
        if (dissipative < o.dissipative)
            return -1;
        else if (dissipative == o.dissipative)
            return 0;
        else
            return 1;
    }

}

圖形用戶(hù)界面與交互相關(guān)

package gui;

public class Field {
    private int width;
    private int height;
    private Road[][] field;
    
    public Field(int width, int height) {
        this.width = width;
        this.height = height;
        field = new Road[height][width];
    }
    
    public int getWidth() { return width; }
    public int getHeight() { return height; }
    
    public Road replace(int row, int col, Road newRoad) {
        Road ret = field[row][col];
        field[row][col] = newRoad;
        return ret;
    }
    
    public Road get(int row, int col) {
        return field[row][col];
    }
    
    public void clear() {
        for ( int i=0; i<height; i++ ) {
            for ( int j=0; j<width; j++ ) {
                field[i][j] = null;
            }
        }
    }
}

package gui;

import java.awt.Color;
import java.awt.Graphics;
 
public class Road {
    
    
    private Color color;
    
    public Road(Color color) {
        this.color = color;
    }

    public void draw(Graphics g, int x, int y, int size) {
        g.setColor(color);
        g.drawRect(x, y, size, size);
        g.fillRect(x, y, size, size);
    }
}

package gui;

import java.awt.Dimension;
import java.awt.Graphics;

import javax.swing.JPanel;

import handler.ConstantValue;

public class View extends JPanel {

    private static final long serialVersionUID = 1L;
    
    private Field theField;
    
    public View(Field field) {
        theField = field;
    }

    @Override
    public void paint(Graphics g) {
        super.paint(g);
        for ( int row = 0; row<theField.getHeight(); row++ ) {
            for ( int col = 0; col<theField.getWidth(); col++ ) {
                Road road = theField.get(row, col);
                if ( road != null ) {
                    road.draw(g, col*ConstantValue.GRID_SIZE, row*ConstantValue.GRID_SIZE, ConstantValue.GRID_SIZE);
                }
            }
        }
    }

    @Override
    public Dimension getPreferredSize() {
        return new Dimension(theField.getWidth()*ConstantValue.GRID_SIZE+1, theField.getHeight()*ConstantValue.GRID_SIZE+1);
    }

}

package handler;

import java.awt.Color;

public class ConstantValue {
    public static final int SIZE = 100;
    public static final int GRID_SIZE = 500 / SIZE;
    public static final Color COLOR_FOR_PROGRESS = new Color(0x3C, 0xF5, 0xEB);
    public static final Color COLOR_FOR_RESULT = Color.RED;
    public static final Color COLOR_FOR_BLOCK = Color.BLACK;
    public static final Color COLOR_FOR_PASSABLE_AREA = Color.WHITE;
    public static final String GUI_TITLE = "路徑導(dǎo)航 by 張臻煒";

    private ConstantValue() {

    }

}

package handler;

import java.awt.Color;
import java.util.LinkedList;

import javax.swing.JFrame;

import gui.Field;
import gui.Road;
import gui.View;
import main.Node;

public class Draw {

    public static void draw(boolean[][] maze, LinkedList<Node> progress, LinkedList<Node> result) {
        Field field = new Field(ConstantValue.SIZE, ConstantValue.SIZE);
        for (int row = 0; row < field.getHeight(); row++) {
            for (int col = 0; col < field.getWidth(); col++) {
                Color c;
                if (maze[row][col] == true) {
                    c = ConstantValue.COLOR_FOR_PASSABLE_AREA;
                } else {
                    c = ConstantValue.COLOR_FOR_BLOCK;
                }
                field.replace(row, col, new Road(c));
            }
        }

        for (Node node : progress) {
            Color c = ConstantValue.COLOR_FOR_PROGRESS;
            field.replace(node.x, node.y, new Road(c));
        }

        for (Node node : result) {
            Color c = ConstantValue.COLOR_FOR_RESULT;
            field.replace(node.x, node.y, new Road(c));
        }

        View view = new View(field);
        JFrame frame = new JFrame();
        frame.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
        frame.setResizable(false);
        frame.setTitle(ConstantValue.GUI_TITLE);
        frame.add(view);
        frame.pack();
        frame.setVisible(true);

    }

}

package handler;

import java.io.File;
import java.io.FileNotFoundException;
import java.util.Scanner;

import main.Node;

public class InputHandler {
    String fileName;
    Node source;
    Node terminal;

    public void input() {
        Scanner in = new Scanner(System.in);
        System.out.println("請(qǐng)輸入地圖的文件名：");
        fileName = in.nextLine();
        System.out.println("請(qǐng)輸入起點(diǎn)的橫縱坐標(biāo)，以一個(gè)空格分隔，以回車(chē)結(jié)束：");
        source = new Node(in.nextInt(), in.nextInt());
        System.out.println("請(qǐng)輸入終點(diǎn)的橫縱坐標(biāo)，以一個(gè)空格分隔，以回車(chē)結(jié)束：");
        terminal = new Node(in.nextInt(), in.nextInt());
        in.close();
    }

    public String getFileName() throws Exception {
        if (fileName == null) {
            throw new Exception("請(qǐng)先輸入文件名");
        } else {
            return fileName;
        }

    }

    public Node getSource() throws Exception {
        if (source == null) {
            throw new Exception("請(qǐng)先輸入起點(diǎn)！");
        } else {
            return source;
        }

    }

    public Node getTerminal() throws Exception {
        if (terminal == null) {
            throw new Exception("請(qǐng)先輸入終點(diǎn)！");
        } else {
            return terminal;
        }

    }

    public boolean[][] getMaze() throws FileNotFoundException {
        Scanner in = new Scanner(new File(fileName));
        boolean[][] maze = new boolean[ConstantValue.SIZE][ConstantValue.SIZE];
        for (int i = 0; i < ConstantValue.SIZE; ++i) {
            String s = in.nextLine();
            for (int j = 0; j < ConstantValue.SIZE; ++j) {
                maze[i][j] = (s.charAt(j) == '0');
            }
        }
        in.close();
        return maze;
    }

}