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

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

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

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

圖 2.

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

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

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

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

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

蛋疼的差事

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

觸動(dòng)

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

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

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

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

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

陳元杰

2012/7/22