迭代加深

深度優(yōu)先搜索是選擇一個(gè)分支，直到盡頭才會(huì)開始回溯。但在遇到搜索樹的每個(gè)節(jié)點(diǎn)的分支數(shù)目非常多，并且答案其實(shí)只是在很淺的節(jié)點(diǎn)上。那么如果在一開始深搜選錯(cuò)了分支，就很可能在不包含答案的深層子樹上浪費(fèi)大量的時(shí)間。

那么此時(shí)，我們就可以使用迭代加深的思想，從小到大限制搜索的深度。如果在當(dāng)前深度限制下搜索不到答案，那么就增加深度，重新進(jìn)行一次搜索。

雖然理論上重新搜索的代價(jià)似乎是挺不必要的，但是隨著層數(shù)的深入，每層節(jié)點(diǎn)數(shù)會(huì)呈指數(shù)性增長(zhǎng)。這點(diǎn)重復(fù)量和深層子樹的規(guī)模相比，不值一提。

總之，當(dāng)搜索樹規(guī)模隨著層次的深入增長(zhǎng)很快，并且我們能夠確保答案在一個(gè)較淺層的節(jié)點(diǎn)時(shí)，就可以用這個(gè)技巧。