基于構件組裝的若干圖算法開發(fā)與生成研究.pdf

1、當前，我們已經進入了大數據和云計算時代，隨之而來的是對軟件產品多樣性需求的爆炸式增長。然而，以往的軟件開發(fā)方法存在許多問題，如開發(fā)效率低下、算法程序缺乏正確性和可靠性等，越來越無法滿足日益增長的軟件需求。因此，如何提高軟件開發(fā)的效率和可靠性一直是許多研究者關注的焦點。大量的實踐表明，基于構件的軟件復用技術由于具備開發(fā)高可靠性和高效率軟件的特性，為解決這一難題提供了行之有效的思路。利用可重用程序構件庫中的構件可以組裝成各種應用程序，這樣可

2、以減少大量的重復性勞動，最終實現算法程序生成的自動化。
　　生成式程序設計方法為構件復用及組裝以生成軟件系統提供支持，由領域工程和應用工程兩個過程組成，前者包括領域分析、領域設計和領域實現三個階段，其中領域分析針對某一特定的領域，分析領域中的通用性和可變性，提取一組復用性足夠的領域需求，最后對提取的領域需求進行抽象以生成所需的領域模型；后者則是在產生的領域模型基礎上，組裝可復用構件進行軟件開發(fā)。
　　PAR方法是一種支持算法

3、程序形式化和自動化開發(fā)的新型軟件開發(fā)方法，其定義的Radl算法設計語言和Apla抽象程序設計語言能夠大幅度簡化算法，為實現開發(fā)算法的高效率、高精確性提供有力保證。PAR平臺是用于支撐PAR方法的新型軟件開發(fā)平臺，提供了有效的預定義組合數據類型，使得編程更加容易和可靠。
　　本文基于PAR方法及其平臺，研究了經構件組裝開發(fā)和生成若干圖算法的問題，開展的主要工作及研究結果有：
　　(1)分析和綜述了生成式程序設計、軟件復用技術、

4、PAR方法及其平臺。
　　(2)通過分析廣度優(yōu)先類算法和深度優(yōu)先類算法的共性和可變性，設計了這兩類算法的兩個泛型算法構件relax和dfs及相關算子構件，并給出了相應的Apla語言實現。
　　(3)借助PAR方法中的泛型機制，將泛型算法構件和相應算子構件組裝，生成了廣度優(yōu)先遍歷算法、Dijkstra算法、Floyd算法等廣度優(yōu)先類算法以及深度優(yōu)先遍歷算法、創(chuàng)建鄰接表算法、拓撲排序、強連通分量求解等深度優(yōu)先類算法，并在PAR平