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

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

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

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

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

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

最終提交時，我把深度定為500（因為定為1000時我自己的程序崩潰了），居然一次性過了，花費的空間是208K，時間是 875MS，再看一個師弟的提交，空間是9816K，時間是438MS，可見DFS和BFS的區(qū)別。


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

有時候花費較長的時間一次性找到一個解，比花費較短的時間而多次找不到解，要來得快。