基于二維地圖的連通路徑快速查找算法

馬春艷 崔鵬 金明日

摘 要：連通路徑的關(guān)鍵問題是快速查找算法的問題，傳統(tǒng)的算法往往效率不高，本文針對游戲連連看的連通路徑問題，闡述了不同于以往的快速查找算法，該算法同時適用于在笛卡爾坐標(biāo)系中的二維坐標(biāo)平面內(nèi)尋找在兩次折線以內(nèi)的連通路徑，并明確給出了每次轉(zhuǎn)折點(diǎn)的坐標(biāo)，可以快速尋找出任意兩點(diǎn)的連通路徑。

關(guān)鍵詞：連通路徑；二維地圖；快速算法

在各種應(yīng)用中，經(jīng)常面對兩點(diǎn)的連通路徑問題，以往的路徑連通算法多為迭代式路徑探索，直到尋找到滿足條件的路徑為止，這種算法的優(yōu)點(diǎn)是算法簡單，代碼量少，但是缺點(diǎn)也是顯著的，迭代次數(shù)太大，效率很低，尤其是當(dāng)二維地圖的信息量很大時，數(shù)據(jù)計(jì)算量非常驚人。本文闡述了游戲連連看的路徑快速尋找算法，提高了算法的效率。

1 連連看游戲的連通路徑規(guī)則

第一，兩個結(jié)點(diǎn)圖片內(nèi)容相同；第二，兩個結(jié)點(diǎn)圖片所在的坐標(biāo)之間可以在兩次折線以內(nèi)（包括兩次）無障礙連通。

典型的連通路徑如下：

2 快速算法

（1）首先確定要連通的兩個結(jié)點(diǎn)以及他們在地圖中的坐標(biāo)，如下：A（3，4）和B（11，7）

⑵計(jì)算結(jié)點(diǎn)A的左、上、右、下四個方向上的空位直線排列組合，計(jì)算采用由結(jié)點(diǎn)中心坐標(biāo)向四周延伸的方法，這樣有助3 結(jié)論

在二維地圖中尋找任意兩點(diǎn)之間的連通路徑問題，采用探路和迭代并不一定是最佳選擇，根據(jù)需求的特點(diǎn)完全可以設(shè)計(jì)出簡潔，快速高效的算法，可以提高應(yīng)用程序的執(zhí)行效率，使用戶達(dá)到更好的體驗(yàn)。

[參考文獻(xiàn)]

[1]王霄，等.基于多連通域Voronoi圖的螺旋掃描路徑算法.農(nóng)業(yè)機(jī)械學(xué)報.2006.

[2]吳昊，等.幾種電力網(wǎng)絡(luò)圖的連通路徑拓?fù)渌惴ㄑ芯?電力系統(tǒng)保護(hù)與控制.2009.

[3]王英杰，等.基于有效路徑集合的節(jié)點(diǎn)間連通度估計(jì)方法研究.武漢理工大學(xué)學(xué)報.2009.

[4]2009 Thomas H.Cormen，Charles E.Leiserson，等.Intriduction Algorithms，Second Edition.北京：機(jī)械工業(yè)出版社.2006.

[5]龔劬.圖論與網(wǎng)絡(luò)最優(yōu)化算法.重慶：重慶大學(xué)出版社.