本篇簡(jiǎn)述一下迭代加深搜索，并列出了偽代碼幫助大家理解。

迭代加深是一種每次限制搜索深度的深度優(yōu)先搜索。

（1）本質(zhì)：它的本質(zhì)還是深度優(yōu)先搜索，只不過(guò)在搜索的同時(shí)帶上了一個(gè)深度d ，當(dāng)d達(dá)到設(shè)定的深度時(shí)就返回，一般用于找最優(yōu)解。如果一次搜索沒(méi)有找到合法的解，就讓設(shè)定的深度+1 ，重新從根開(kāi)始。

既然是為了找最優(yōu)解，為什么不用BFS呢？我們知道BFS的基礎(chǔ)是一個(gè)隊(duì)列，隊(duì)列的空間復(fù)雜度很大，當(dāng)狀態(tài)比較多或者單個(gè)狀態(tài)比較大時(shí)，使用隊(duì)列的BFS就顯出了劣勢(shì)。事實(shí)上，迭代加深就類(lèi)似于用DFS方式實(shí)現(xiàn)的BFS，它的空間復(fù)雜度相對(duì)較小。

當(dāng)搜索樹(shù)的分支比較多時(shí)，每增加一層的搜索復(fù)雜度會(huì)出現(xiàn)指數(shù)級(jí)爆炸式增長(zhǎng)，這時(shí)前面重復(fù)進(jìn)行的部分所帶來(lái)的復(fù)雜度幾乎可以忽略，這也就是為什么迭代加深是可以近似看成BFS的。

（2）步驟：首先設(shè)定一個(gè)較小的深度作為全局變量，進(jìn)行DFS。每進(jìn)入一次DFS，將當(dāng)前深度d++ ，當(dāng)發(fā)現(xiàn)d大于設(shè)定的深度就返回。如果在搜索的途中發(fā)現(xiàn)了答案就可以回溯，同時(shí)在回溯的過(guò)程中可以記錄路徑。如果沒(méi)有發(fā)現(xiàn)答案，就返回到函數(shù)入口，增加設(shè)定深度，繼續(xù)搜索。

（3）偽代碼：

void IDDFS(u,d) {
    if(d>設(shè)定深度) return;
    else for(each edge(u,v)) IDDFS(v,d+1);
    return;
}

（4）解題策略

在大多數(shù)的題目中，廣度優(yōu)先搜索還是比較方便的，而且容易判重。當(dāng)發(fā)現(xiàn)廣度優(yōu)先搜索在空間上不夠優(yōu)秀，而且要找最優(yōu)解的問(wèn)題時(shí)，就應(yīng)該考慮迭代加深。