連連看的A*搜索 VS 深度優(yōu)先搜索

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

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

注意：此時已經(jīng)沒必要再用轉(zhuǎn)彎次數(shù)作為A*搜索的啟發(fā)函數(shù)了。

圖 2.

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

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

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

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

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

蛋疼的差事

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

觸動

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

也看了我即將要搬進(jìn)去的地方，一個字“大”，兩個字“豪華”！哈哈，陽臺、獨(dú)立衛(wèi)生間，good。650/月very good。

既然要做這個行業(yè)絕對不能停止學(xué)習(xí)，絕對不能滿足現(xiàn)狀，不然僅僅在公司的框架上填空，毫無創(chuàng)造性一點(diǎn)激情也沒有。

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

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

陳元杰

2012/7/22