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

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

2、以減少大量的重復(fù)性勞動(dòng)，最終實(shí)現(xiàn)算法程序生成的自動(dòng)化。
　　生成式程序設(shè)計(jì)方法為構(gòu)件復(fù)用及組裝以生成軟件系統(tǒng)提供支持，由領(lǐng)域工程和應(yīng)用工程兩個(gè)過程組成，前者包括領(lǐng)域分析、領(lǐng)域設(shè)計(jì)和領(lǐng)域?qū)崿F(xiàn)三個(gè)階段，其中領(lǐng)域分析針對(duì)某一特定的領(lǐng)域，分析領(lǐng)域中的通用性和可變性，提取一組復(fù)用性足夠的領(lǐng)域需求，最后對(duì)提取的領(lǐng)域需求進(jìn)行抽象以生成所需的領(lǐng)域模型；后者則是在產(chǎn)生的領(lǐng)域模型基礎(chǔ)上，組裝可復(fù)用構(gòu)件進(jìn)行軟件開發(fā)。
　　PAR方法是一種支持算法

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

4、PAR方法及其平臺(tái)。
　　(2)通過分析廣度優(yōu)先類算法和深度優(yōu)先類算法的共性和可變性，設(shè)計(jì)了這兩類算法的兩個(gè)泛型算法構(gòu)件relax和dfs及相關(guān)算子構(gòu)件，并給出了相應(yīng)的Apla語言實(shí)現(xiàn)。
　　(3)借助PAR方法中的泛型機(jī)制，將泛型算法構(gòu)件和相應(yīng)算子構(gòu)件組裝，生成了廣度優(yōu)先遍歷算法、Dijkstra算法、Floyd算法等廣度優(yōu)先類算法以及深度優(yōu)先遍歷算法、創(chuàng)建鄰接表算法、拓?fù)渑判?、?qiáng)連通分量求解等深度優(yōu)先類算法，并在PAR平