概念

什么是回溯法？

回溯法的基本思想：對(duì)一個(gè)包括有很多結(jié)點(diǎn)，每一個(gè)結(jié)點(diǎn)有若干個(gè)搜索分支的問(wèn)題，把原問(wèn)題分解為對(duì)若干個(gè)子問(wèn)題求解的算法。

我們簡(jiǎn)單分析一下這句話，其實(shí)就是當(dāng)搜索到某個(gè)結(jié)點(diǎn)，發(fā)現(xiàn)無(wú)法再繼續(xù)搜索下去的時(shí)候，就讓搜索過(guò)程回溯（也稱(chēng)退回）到該結(jié)點(diǎn)的上一個(gè)結(jié)點(diǎn)，繼續(xù)搜索這個(gè)結(jié)點(diǎn)的其他尚未搜索過(guò)的分支，然后一遍一遍重復(fù)這個(gè)步驟，直到搜索到問(wèn)題的解或搜索完了全部可搜索分支沒(méi)有解存在為止。

迷宮問(wèn)題

說(shuō)到回溯法，就不得不說(shuō)使用回溯思想最經(jīng)典的一個(gè)問(wèn)題：迷宮問(wèn)題。

我們規(guī)定：2 為墻壁 0為道路 由圖可見(jiàn)，我們有4種不同的通路。?

我們?cè)O(shè)置入口為（1,1）出口為（7,7）

①. 我們?cè)谥鞣椒ɡ锵瘸跏蓟粋€(gè)迷宮，用二維數(shù)組來(lái)實(shí)現(xiàn)。

②. 我們定義四個(gè)成員變量，并且設(shè)置入口出口坐標(biāo)

③. 實(shí)現(xiàn)我們迷宮通路的算法，在尋找下一個(gè)通路點(diǎn)時(shí)，我們就用到了回溯的思想。

完整的實(shí)現(xiàn)代碼！

總結(jié)

多練還是最好的途徑，迷宮是一個(gè)很典型的問(wèn)題，大家一定要多多理解其中的思路！

下一講我們就要介紹樹(shù)的相關(guān)知識(shí)啦 ：）

PS：有什么問(wèn)題或者不解的地方可以評(píng)論，我都會(huì)一一就行回復(fù)的，如果有錯(cuò)誤或者言語(yǔ)不明的地方，還請(qǐng)大神多多指點(diǎn)！