連連看的A*搜索 VS 深度優先搜索

這周在測試連連看的時候發現了嚴重的搜索算法錯誤問題。原先我用的A*只是比較兩個節點的轉彎次數，使用的hash標記就是遍歷過的節點不能再走。但是在這樣的情況下就不能保證走出正確的路徑。如圖1所示。S為起點，E為終點，黑色表示墻壁。從S開始遍歷的時候路徑1和2走到紅色位置的轉彎次數是相同的，然而在往下走一步1就永遠走不到終點了（轉彎次數超過了兩次）。所以這樣的hash標記是行不通的。不能一棒子打死走過的地方就不讓走。

既然設置了轉彎次數，hash標記可以使用轉彎次數來設定。如圖2所示。圖中的數字表示從起點到該節點的轉彎次數。在遍歷的時候通過判斷之前到達該節點的時候轉彎次數是否大于等于當前節點的轉彎次數。這樣上面所說的路徑2就可以順利通過紅色位置。到了下一個節點通過判斷路徑2的轉彎次數少于路徑1那么只需要保留路徑2走到終點即可。

注意：此時已經沒必要再用轉彎次數作為A*搜索的啟發函數了。

圖 2.

雖然這樣做避免了搜索不到終點的致命錯誤，但是效率上并不可觀。因為遍歷到某個點轉彎次數相同的情況很多，所以這樣的搜索帶來了大量的不必要的遍歷。后來我加了一個當前節點到終點的步數記錄。將步數這個條件作為啟發函數。這樣做可以將最可能打到終點的節點優先搜索。效率有顯著的提高。

但是我又想用這A*算法浪費了那么多的內存用來記錄各種中間值，深搜的話會不會更加快。因為只要超過2次轉彎就不必繼續遍歷。于是我寫了個深搜試了一下，的確比之前我個人認為已經不能再優化的A*算法要快的多。當然我測試的地圖是15*15的，并且A*算法搜索的路徑還可以將步數控制在最短。而深搜的遞歸會大量調用函數堆棧。但是……在這個問題上A*的優勢并沒有體現出來，1.連連看是不管距離遠近的 2.轉彎次數不超過兩次深搜的遞歸次數并不多。

綜上所述A*可以解決大多數擁有各種條件的搜索問題，但是對于連連看的搜索在15*15的地圖規模下深搜的確優于A*，內存和時間都比較省，時間幾乎每次都是0的。

最后我保留了兩個算法函數。可能有人會看不懂什么A*啊，什么啟發式搜索啊，什么hash…。其實A*就是廣搜加一個比較函數，那個比較函數就是啟發函數，通過它來排列隊列中節點的先后順序決定哪些節點應該先搜索。上文提到的hash標記，即最簡單的hash。舉個例子就是搜索地圖的時候標記已走過的地方防止重復遍歷。其實這些東西以前ACM的時候都用過，一直到不知道專業名詞….

順便提一下，杭電上的那道連連看數據太弱了，測試數據沒有包含我以上提到的情況。

蛋疼的差事

我表哥現在在浦江做婚紗攝影，叫我給他做個網站，為什么…為什么會這樣。我真的不會做網站，但是第一次和他說的時候我說你要的那點屁功能隨便寫寫就是了，你只要把圖片資料什么的弄來就好了。結果他發給我一個excel寫的都是寫什么…居然還寫了一個網址www.pjhssy.com 我頓時無語，在他眼里這域名也是程序員寫出來的。他的原話是這樣的：反正你全部幫我搞定，寫好了買什么空間什么的都弄好，除了買空間的錢你其他的想都別想（我還沒想這事他倒是事先說明了，好像我欠他錢一樣- -）。硬的不行他又說難道你忘了以前我在杭州的時候我是怎么對你的，每次來我這里玩都是熱情接待，上廁所我都讓你先去…。還有一大堆切扁的廢話，很無奈。

觸動

參觀了幾個同事的住處，房間慘不忍睹…..人全部在玩游戲…..，兩個用iphone的同事房間就和衛生間一樣大，只有一張床和一個放電腦的小桌子，衣服就掛在一根長度最多一米的木條上，iphone放在破桌子的隔層，這樣的場景很不協調，感覺就像傾家蕩產買了個手機…。對于工作生活他們似乎沒有目標，對于這份工作似乎并不是自己的興趣，反而像讀書是自己不得不做的事情。人生怎能如此無聊！

也看了我即將要搬進去的地方，一個字“大”，兩個字“豪華”！哈哈，陽臺、獨立衛生間，good。650/月very good。

既然要做這個行業絕對不能停止學習，絕對不能滿足現狀，不然僅僅在公司的框架上填空，毫無創造性一點激情也沒有。

我留在這里工作的目標，要自己寫一個完完全全的網絡游戲，可以很小，但是要包括多線程、數據庫、安全性考慮等。游戲模塊要盡可能多的使用C++的特性，將書上看過但是沒用過的東西都試試。到時候再換工作也不必要擔心自己的能力問題。

吃了晚飯之后走在學源街上，由于是暑假學生比較少，黃昏夕陽，安靜的街道很美。

陳元杰

2012/7/22