迭代加深
深度優先搜索是選擇一個分支,直到盡頭才會開始回溯。但在遇到搜索樹的每個節點的分支數目非常多,并且答案其實只是在很淺的節點上。那么如果在一開始深搜選錯了分支,就很可能在不包含答案的深層子樹上浪費大量的時間。
那么此時,我們就可以使用迭代加深的思想,從小到大限制搜索的深度。如果在當前深度限制下搜索不到答案,那么就增加深度,重新進行一次搜索。
雖然理論上重新搜索的代價似乎是挺不必要的,但是隨著層數的深入,每層節點數會呈指數性增長。這點重復量和深層子樹的規模相比,不值一提。
總之,當搜索樹規模隨著層次的深入增長很快,并且我們能夠確保答案在一個較淺層的節點時,就可以用這個技巧。