PKU上面的1077是經(jīng)典題目——八數(shù)碼，在《人工智能》這門(mén)課中是重點(diǎn)的研究對(duì)象，引領(lǐng)前面幾章的內(nèi)容，可見(jiàn)其在搜索方面的典型性。

已知：3*3的格子，以及每個(gè)格子的數(shù)字（1~8和一個(gè)'x'，兩兩不同），每次只能夠移動(dòng)x那個(gè)格子，并且只能往左右上下四個(gè)方向移動(dòng)
目標(biāo)：某種狀態(tài)，在該題中為
            1 2 3
            4 5 6
            7 8 x
未知（所求）：如何從給出的一個(gè)狀態(tài)，經(jīng)過(guò)一系列的移動(dòng)，到達(dá)目標(biāo)狀態(tài)

解決問(wèn)題從提出問(wèn)題開(kāi)始：
1.已知和未知有啥關(guān)系？
答：目標(biāo)狀態(tài)是由已知狀態(tài)一步步移到的。
2.是否一定存在解呢？
答：從題目得知，有時(shí)候會(huì)得不到解（當(dāng)僅僅只有兩個(gè)數(shù)字不在原來(lái)的位置上時(shí)無(wú)解）。
3是否在以前遇到過(guò)類似的問(wèn)題？
答：象棋上馬的走法，從一個(gè)點(diǎn)到達(dá)目的點(diǎn)的搜索過(guò)程，因此考慮可以用類似的方法來(lái)尋找答案，也就是搜索。
4.除了搜索還有其他方法可以解決這個(gè)問(wèn)題么？
答：暫時(shí)沒(méi)有人發(fā)現(xiàn)，
5.如何搜索？
答：從起始位置開(kāi)始，向四個(gè)方向嘗試，一旦往一個(gè)方向嘗試了，則要防止呆會(huì)又往原來(lái)的位置嘗試的問(wèn)題，于是除了一開(kāi)始外，其他的每次最多只能往3個(gè)方向的嘗試。
6.如何判斷當(dāng)前狀態(tài)是否已經(jīng)是目標(biāo)狀態(tài)？
答：每行每列都和目標(biāo)狀態(tài)的比較。

好，我于是很快的寫(xiě)出來(lái)一個(gè)DFS的程序（DFS不需要額外的空間，不需要記住狀態(tài)到達(dá)哪里，比BFS容易寫(xiě)）
運(yùn)行后，發(fā)現(xiàn)出錯(cuò)，通過(guò)用斷點(diǎn)調(diào)試了一會(huì)后，處理了幾個(gè)小錯(cuò)誤后，遇到一個(gè)問(wèn)題：
7.我的程序總是得不出結(jié)果。
答：因?yàn)镈FS的話，你必須要確定他會(huì)到達(dá)一個(gè)終點(diǎn)就回溯，問(wèn)題就出在我的程序不會(huì)出現(xiàn)無(wú)路可走的情況，因?yàn)樗粫?huì)判斷當(dāng)前狀態(tài)是否已經(jīng)是之前走過(guò)的，所以會(huì)一步循環(huán)走下去，甚至明明一步就能到達(dá)目的地，他還是要走無(wú)限遠(yuǎn)的路，直到程序被迫跳出。
8.如何處理這個(gè)問(wèn)題？
答：既然是因?yàn)檫f歸的無(wú)限深度，那我們就給他一個(gè)深度極限，當(dāng)?shù)竭_(dá)這個(gè)深度時(shí)，就返回。接下來(lái)的問(wèn)題是：
9.這個(gè)深度該是多少？
答：一個(gè)深度就代表一步，八數(shù)碼的問(wèn)題最多需要走多少步就一定能夠到達(dá)目標(biāo)呢？（注意，是一定），如果這個(gè)深度開(kāi)太小了，有可能找不到解，如果這個(gè)深度開(kāi)太大了，又會(huì)讓程序不斷遞歸下去。所以需要自己試驗(yàn)。

我先設(shè)了個(gè)100，發(fā)現(xiàn)可以得出結(jié)果，但是那個(gè)步數(shù)也就是100步左右（因?yàn)镈FS找到的路徑不是最短的，而是最靠近某一個(gè)方向的），和sample output的19步不同啊，于是我改成19步，結(jié)果出來(lái)的答案也是19步，只是和給出的不同，為了驗(yàn)證我的答案也是正確的，我撕了一張紙，在上面寫(xiě)了個(gè)八數(shù)碼，并且按照我給出的步驟去走，最終確實(shí)到達(dá)目標(biāo)了，可見(jiàn)我的算法是正確的。

10.求的不是最短步驟，能行么？
答：再次檢查題目，發(fā)現(xiàn)并沒(méi)有要求最短路徑，并且題目顯示是Special Judge，可見(jiàn)應(yīng)該可以。

最終提交時(shí)，我把深度定為500（因?yàn)槎?000時(shí)我自己的程序崩潰了），居然一次性過(guò)了，花費(fèi)的空間是208K，時(shí)間是 875MS，再看一個(gè)師弟的提交，空間是9816K，時(shí)間是438MS，可見(jiàn)DFS和BFS的區(qū)別。


然后我又分別試了下將深度改為200，350，結(jié)果都是TLE，證明一個(gè)問(wèn)題：

有時(shí)候花費(fèi)較長(zhǎng)的時(shí)間一次性找到一個(gè)解，比花費(fèi)較短的時(shí)間而多次找不到解，要來(lái)得快。