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

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

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

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

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