A 左手摸墻算法的描述。
- 當(dāng)左手邊沒有墻時(shí)，左轉(zhuǎn)前進(jìn)一步；
- 當(dāng)左手邊有墻且前方?jīng)]有墻時(shí)，前進(jìn)一步；
- 當(dāng)左手邊有墻且前方也有墻時(shí)，右轉(zhuǎn)前進(jìn)一步；
右手摸墻算法，只需將上面的“左”換作“右”，“右”換作“左”。
B 摸墻算法存在的問題，路徑冗余度搞高
比如在一個(gè)封閉房間中，左手摸墻算法和右手摸墻算法，使用的總能耗差異很大。
這個(gè)問題需要用用遺傳算法的思想剞劂。
多次使用左手和右手摸墻算法，依靠積累經(jīng)驗(yàn)來得到概率結(jié)論，然后根據(jù)不同條件進(jìn)行學(xué)習(xí)之后得知下一次采取哪種摸墻。
C 摸墻算法的性能改善
這個(gè)策略只是用與多次重復(fù)走一個(gè)迷宮的情況，對(duì)于走陌生的迷宮，不適用。
當(dāng)作出一次移動(dòng)時(shí)，在路徑中查找先前是否經(jīng)過相同的點(diǎn)，如果有那么就說明到這一步為止完成了一個(gè)圈子，在遺傳算法中，把它從路徑中除去。
多次行動(dòng)測(cè)試后，將會(huì)改善能耗效果，得到一點(diǎn)經(jīng)驗(yàn)概率結(jié)果。
去除圈子的算法是：
假設(shè)左手摸墻走，取得所有已經(jīng)過路徑記為dimension[all]
遍歷dimension all to 0， 碰見重復(fù)的路徑節(jié)點(diǎn)，證明，這個(gè)點(diǎn)所經(jīng)歷的左手摸墻路徑是一個(gè)圈
將這個(gè)點(diǎn)標(biāo)記，以后在這里跳過這個(gè)位置的左手摸墻而采用直走跳過這個(gè)節(jié)點(diǎn)。
思考：如何給小車在開放空間中，做環(huán)形路徑點(diǎn)的標(biāo)記？
D 深度優(yōu)先搜索算法：
程序運(yùn)行時(shí)將按照從上到下，從左到右的順序遍歷整棵樹。
對(duì)于真實(shí)環(huán)境的物理小車，需要為小車安裝指南針或者陀螺儀才行。理論上加速度傳感器也能做到，但是算法上也許要稍微復(fù)雜一點(diǎn)。
深度優(yōu)先算法按以下規(guī)則執(zhí)行遍歷：
- 1，判斷當(dāng)前節(jié)點(diǎn)是否為目標(biāo)節(jié)點(diǎn)，如是，返回成功。
- 2，檢查當(dāng)前節(jié)點(diǎn)是否還有未訪問過的子節(jié)點(diǎn)，若否goto 4。 => 4，檢查當(dāng)前節(jié)點(diǎn)是否有上層節(jié)點(diǎn)，若有訪問上層節(jié)點(diǎn)，設(shè)為當(dāng)前節(jié)點(diǎn)。goto 1。
- 3，訪問子節(jié)點(diǎn)，設(shè)為當(dāng)前節(jié)點(diǎn)，設(shè)已訪問。goto 1。
- 5，返回失敗。
E 廣度優(yōu)先搜索算法：
-
1、從圖中某個(gè)頂點(diǎn)V0出發(fā)，并訪問此頂點(diǎn)；
2、從V0出發(fā)，訪問V0的各個(gè)未曾訪問的鄰接點(diǎn)W1，W2，…,Wk;然后,依次從W1,W2,…,Wk出發(fā)訪問各自未被訪問的鄰接點(diǎn)；
3、重復(fù)步驟2，直到全部頂點(diǎn)都被訪問為止。
廣度優(yōu)先的好處在于，如果有多個(gè)出口，那么第一個(gè)被找到的出口消耗時(shí)間最短，廣度最小，也即路勁最短。
另一個(gè)額外的好處是，可以知道所有的出口。得到一個(gè)統(tǒng)計(jì)結(jié)果。