楊會(huì)廷
　　(東方地球物理公司 物探技術(shù)研究中心,，河北 涿州 072750）

       摘要：當(dāng)前軟件普遍采用爬蟲程序完成部分測試功能，分析當(dāng)前測試用的爬蟲程序,，發(fā)現(xiàn)耗時(shí)最多的是查找可用路徑,。為了避免撒網(wǎng)式的、無明確目地的,、重復(fù)查找,，提出了將集合因子最短路徑算法應(yīng)用于當(dāng)前的爬蟲程序中，以改善并提高爬蟲程序在軟件測試中的效率和有效性,。此算法可以大大縮減爬蟲程序在查找有效可用路徑的時(shí)間,，提高整個(gè)測試的效率。
　　關(guān)鍵詞：最短路徑,；軟件測試,；集合因子　　

0引言
　　為了滿足市場的需要，一般軟件都需要支持多個(gè)語言版本,，例如：微軟的Windows 系統(tǒng)和Office軟件需要支持幾百種語言,。因此針對(duì)多個(gè)語言的本地化軟件測試不可避免地提上了日程。在本地化軟件測試中,，除了本地化的功能測試外,，為了保證本地化軟件的翻譯質(zhì)量，往往需要對(duì)軟件的所有本地化頁面進(jìn)行檢查,。對(duì)于支持幾百種語言的軟件,，如何快速有效地獲取多種語言的所有本地化頁面就成為降低此項(xiàng)測試成本的關(guān)鍵［1］。
1如何獲取所有軟件頁面
　　一個(gè)軟件有多少界面對(duì)于開發(fā)者來說是透明的,。如何獲取一個(gè)軟件所有的界面,，對(duì)于不同的軟件設(shè)計(jì)會(huì)有不同的策略。基于Web的軟件尤為如此,。
　?。?）訪問URL列表: 這個(gè)策略是針對(duì)基于Web的軟件才可以使用。整個(gè)軟件所有不同的頁面對(duì)應(yīng)的是不同且唯一的URL,。通過訪問不同的URL以獲取軟件所有界面是比較簡單的方式,。前提就是需要獲取整個(gè)軟件的URL 列表。不過目前大多數(shù)基于Web 的軟件,，特別是外網(wǎng)可以訪問的軟件,，為了保證軟件的安全都要屏蔽掉實(shí)際的URL。所以要獲取整個(gè)軟件的不同URL 列表也不是容易的事,。
　?。?）定制腳本：目前許多軟件在開發(fā)的階段就同時(shí)開始定制許多測試腳本，并在以后的開發(fā)測試階段反復(fù)用來測試以保證軟件功能正常,。但是這些腳本一般都是由開發(fā)人員編寫的,，主要針對(duì)軟件的功能和復(fù)雜的業(yè)務(wù)邏輯，并且主要運(yùn)行在英文版的軟件上,，很少運(yùn)行在本地化的軟件上,。根據(jù)調(diào)查，大概只有6.7%的軟件開發(fā)小組會(huì)把腳本在本地化軟件上試運(yùn)行,。所以很多開發(fā)腳本都很難直接運(yùn)行在本地化的軟件上并獲取本地化的界面［2］,。
　　（3）自動(dòng)爬蟲：目前自動(dòng)爬蟲的程序有很多,。用戶只需要提供登錄信息,，爬蟲程序就能自動(dòng)查找頁面上可能產(chǎn)生的新頁面元素，并依次觸發(fā),，循環(huán)迭代直到找到所有頁面,。為了減少本地化測試成本，對(duì)于支持多種語言的軟件,，要獲取多種語言的本地化頁面,，采取自動(dòng)爬蟲程序是一個(gè)很好的選擇。讓多個(gè)線程同時(shí)分別運(yùn)行在多個(gè)語言環(huán)境下截取所有頁面,，從而可以大大節(jié)省成本,。如果讓爬蟲程序撒網(wǎng)式查找并自由運(yùn)行，則整個(gè)運(yùn)行過程比較冗長,。為了優(yōu)化爬蟲程序,，加入最短路徑算法，使得整個(gè)爬蟲程序更有效［3］,。
2集合因子最短路徑算法的介紹
　　隨著社會(huì)的發(fā)展,，最短路徑問題在現(xiàn)實(shí)生活中占據(jù)的地位越來越重要,。求解這一類問題的方法有很多，包括Floyd算法,、Dijkstra算法,、BellmanFord算法、動(dòng)態(tài)規(guī)劃算法和智能優(yōu)化算法等,。最短路徑問題是圖論研究中的一個(gè)經(jīng)典算法問題,，旨在尋找圖（由節(jié)點(diǎn)和路徑組成的）中兩節(jié)點(diǎn)之間的最短路徑。算法的具體形式包括［4］：
　?。?）確定起點(diǎn)的最短路徑問題：即已知起始節(jié)點(diǎn),，求最短路徑的問題。
　?。?）確定終點(diǎn)的最短路徑問題：與確定起點(diǎn)的問題相反,，該問題是已知終結(jié)節(jié)點(diǎn)，求最短路徑的問題,。在無向圖中該問題與確定起點(diǎn)的問題完全等同,，在有向圖中該問題等同于把所有路徑方向反轉(zhuǎn)的確定起點(diǎn)的問題。
　?。?）確定起點(diǎn)終點(diǎn)的最短路徑問題：即已知起點(diǎn)和終點(diǎn),，求兩節(jié)點(diǎn)之間的最短路徑,。
　?。?）全局最短路徑問題：求圖中所有的最短路徑。
　　用于解決最短路徑問題的算法被稱作“最短路徑算法”,，有時(shí)被簡稱作“路徑算法”,。這里主要介紹可以應(yīng)用于自動(dòng)爬蟲程序的集合因子最短路徑算法。
　　2.1集合因子最短路徑算法介紹
　　集合因子最短路徑算法是單源最短路徑算法,，用于計(jì)算一個(gè)節(jié)點(diǎn)到其他所有節(jié)點(diǎn)的最短路徑,。其主要特點(diǎn)是以起始點(diǎn)為中心向外層擴(kuò)展，在擴(kuò)散過程中每次擴(kuò)散都以一個(gè)集合為因子,，直到擴(kuò)展到所有節(jié)點(diǎn)為止,。
　　問題描述：在無向圖G=(V,E)中，假設(shè)每條邊E［i］的長度為w［i］,，找到由頂點(diǎn)V0到其余各點(diǎn)的最短路徑［5］,。
　　2.2算法描述
　　2.2.1算法思想原理
　　設(shè)G=(V,E)是一個(gè)帶權(quán)無向圖，把圖中頂點(diǎn)集合V分成兩組,，第一組為已求出最短路徑的頂點(diǎn)集合（用S表示,，初始時(shí)S中只有一個(gè)源點(diǎn)，以后每次求得最短路徑的頂點(diǎn), 就被加入到集合S中,，直到全部頂點(diǎn)都加入到S中,，算法就結(jié)束了）,，第二組為其余未確定最短路徑的頂點(diǎn)集合（用U表示），按最短路徑長度的遞增次序依次把第二組的頂點(diǎn)加入S中,。在加入的過程中,，總保持從源點(diǎn)v到S中各頂點(diǎn)的最短路徑長度不大于從源點(diǎn)v到U中任何頂點(diǎn)的最短路徑長度。此外,，每個(gè)頂點(diǎn)對(duì)應(yīng)一個(gè)距離,，S中的頂點(diǎn)的距離就是從v到此頂點(diǎn)的最短路徑長度，U中的頂點(diǎn)的距離是從v到此頂點(diǎn)只包括S中的頂點(diǎn)為中間頂點(diǎn)的當(dāng)前最短路徑長度,。
　　2.2.2算法過程描述
　　算法過程如下：
　?。?）初始時(shí)，S只包含源點(diǎn),，即S＝{v},，v的距離為0。U包含除v外的其他頂點(diǎn),，即:U={其余頂點(diǎn)},，若v與U中頂點(diǎn)u有邊，則<u,v>正常有權(quán)值,，若u不是v的出邊鄰接點(diǎn),，則<u,v>權(quán)值為∞。
　?。?）從U中選取距離v最小的頂點(diǎn)集合<k1,k2>,，把k1、k2加入S中（該選定的距離就是v到k1=v到k2, 且是最短路徑長度）,。
　?。?）以<k1、k2>組成的集合為新考慮的中間點(diǎn),，修改U中各頂點(diǎn)的距離,；若從源點(diǎn)v到頂點(diǎn)u的距離（經(jīng)過頂點(diǎn)ki）比原來距離（不經(jīng)過頂點(diǎn)ki）短，則修改頂點(diǎn)u的距離值,，修改后的距離值的頂點(diǎn)ki的距離加上邊上的權(quán),。
　　（4）重復(fù)步驟（2）和（3）直到所有頂點(diǎn)都包含在S中,。
　　2.3算法適用范圍
　?。?）單源最短路徑；
　?。?）有向圖和無向圖,。
3集合因子最短路徑算法在爬蟲程序中的應(yīng)用
　　每個(gè)軟件一般都有一個(gè)登錄頁面，把登錄后的第一個(gè)頁面命名序號(hào)為001,，然后以從上到下,，從左到右的順序分別定義自動(dòng)爬蟲程序掃描出來的新頁面,，分別是002、003等,。而每個(gè)頁面之間的距離,，即權(quán)值，都為1（實(shí)際中,，訪問不同頁面需要的時(shí)間是不同的,，這里在服務(wù)器性能很好的情況下，忽略訪問時(shí)間的不同,，都設(shè)定為1）,。所有頁面從第一個(gè)頁面001出發(fā)，可以直接到達(dá)或者經(jīng)過若干個(gè)節(jié)點(diǎn)后到達(dá),。其他不同的節(jié)點(diǎn)間也可能存在到達(dá)的路徑,。這樣由所有頁面作為節(jié)點(diǎn)組成一個(gè)所有頁面可到達(dá)的圖，且每個(gè)節(jié)點(diǎn)之間的距離都為1,。由于整個(gè)軟件過于龐大,，下面只畫出部分節(jié)點(diǎn)來說明問題，如圖1所示,。

　　設(shè)001為源點(diǎn),，求001到其他各頂點(diǎn)〈002，003,，004,，005，006,，007,，008,，009,，010，011,，012,，013〉的最短路徑。算法執(zhí)行步驟如表1,。

4試驗(yàn)數(shù)據(jù)和性能對(duì)比
　　通過對(duì)比數(shù)據(jù)更能體現(xiàn)這一算法應(yīng)用在爬蟲程序中的優(yōu)勢,，如表2所示。下面的數(shù)據(jù)采集采用的是相同性能和型號(hào)的服務(wù)器,，且使用相同軟件,。整個(gè)軟件共有956張圖。程序運(yùn)行過程中,，在剛開始速度會(huì)比較快,，到后面時(shí)由于需要花費(fèi)更多時(shí)間判斷處理,，速度會(huì)慢下來。表2中的數(shù)據(jù)屬于平均數(shù)據(jù),。需要運(yùn)行多個(gè)語言平臺(tái)時(shí),，是多個(gè)表1算法執(zhí)行步驟步驟S集合中U集合中1選入 001，此時(shí)S=<001>
　　此時(shí)最短路徑001→001=0
　　以集合<001>為中間點(diǎn)集合開始找U=<002,003,004,005,006,007,008,009,010,011,012,013>
　　001→002=1
　　001→003=1
　　001→004=1
　　001→005=1
　　001→其他U中的節(jié)點(diǎn)=∞2選入002,、003,、004、005,，此時(shí)S=<001,002,003,004,005>,，001→001=0，
　　001→002=1,，
　　001→003=1,，
　　001→004=1，
　　001→005=1,，
　　以集合<002,，003，004,，005>為中間點(diǎn)集合,，從001→002，001→003,，001→004,，001→005最短路徑開始找U=<006,007,008,009,010,011,012,013>
　　002→U中的節(jié)點(diǎn)=∞
　　003→006=1
　　003→007=1
　　003→008=1
　　004→U中的結(jié)點(diǎn)=∞
　　005→008=1（由于003→008=1已存在，直接放棄此條路徑）3選入006,、007,、008，
　　此時(shí),，S=<001,002,003,004,005,006,007,008>,，
　　001→001=0，001→002=1,，001→003=1,，001→004=1，001→005=1,，001→003→006=2,，001→003→007=2，001→003→008=2,，
　　以集合<006,，007，008>為中間點(diǎn)集合,，從001→003→006=2,，001→003→007=2,，001→003→008=2
　　分別為最短路徑開始找U=<009,010,011,012,013>
　　006→U中的節(jié)點(diǎn)=∞
　　007→010=1
　　007→011=1
　　008→009=1
　　008→012=14選入010、011,、009,，012，此時(shí),，S=<001,002,003,004,005,006,007,008,009,010,011,012>,，
　　001→001=0，001→002=1,，001→003=1,，001→004=1，001→005=1,，001→003→006=2,，001→003→007=2，001→003→008=2,，001→003→007→010=3,，001→003→007→011=3，001→003→008→009=3,，001→003→008→012=3,，
　　以集合<009，010,，011,，012>為中間點(diǎn)集合，從001→003→007→010=3,，
　　001→003→007→011=3,，
　　001→003→008→009=3，
　　001→003→008→012=3,，
　　分別為最短路徑開始找U=<013>
　　009→013=1
　　010→U中的節(jié)點(diǎn)=∞
　　011→U中的節(jié)點(diǎn)=∞
　　012→U中的節(jié)點(diǎn)=∞5選入013,，此時(shí)，S=<001,002,003,004,005,006,007,008,009,010,011,012,013>,，001→001=0,，
　　001→002=1，001→003=1,，001→004=1，001→005=1,，001→003→006=2,，001→003→007=2，001→003→008=2,，001→003→007→010=3,，001→003→007→011=3,，001→003→008→009=3，001→003→008→012=3,，001→003→008→009→013=4U集合已空,，查找完畢線程訪問同一個(gè)服務(wù)器，只要改變?yōu)g覽器的語言即可,。從實(shí)驗(yàn)數(shù)據(jù)可以看到在使用集合因子最短路徑算法后,，不論是單個(gè)線程還是多個(gè)線程，整個(gè)程序的運(yùn)行時(shí)間會(huì)大大縮短,，性能大幅度提高,。
5結(jié)論
　　通過把集合因子最短路徑算法應(yīng)用在自動(dòng)爬蟲程序中，使得程序無論在單位時(shí)間的吞吐率還是單位事務(wù)的響應(yīng)速度都大大提高,。對(duì)于某些支持多個(gè)語言的軟件來說集合因子最短路徑算法會(huì)使得程序運(yùn)行效率大幅度提高,。
　　參考文獻(xiàn)
　　［1］ 張茂林.軟件自動(dòng)測試的研究與程序?qū)崿F(xiàn)［J］.北京航空航天大學(xué)學(xué)報(bào), 1997, 23 (1):7480.
　?。?］ 凌永發(fā), 張?jiān)粕? 郭秀萍. 軟件測試自動(dòng)化的腳本技術(shù) ［J］. 云南民族學(xué)院學(xué)報(bào)(自然科學(xué)版),，2002, 11(1):544548.
　　［3］ 王華偉,崔啟亮.軟件本地化——本地化行業(yè)透視與實(shí)現(xiàn)指南［M］.北京:電子工業(yè)出版社,2005.
　?。?］ 侯俊杰.深入淺出MFC(第2 版)［M］. 武漢:華中科技大學(xué)出版社,2005.
　?。?］ 李春葆.數(shù)據(jù)結(jié)構(gòu)教程［M］.北京：清華大學(xué)出版社，2005.