遞推技術(shù)在算法設(shè)計(jì)中的應(yīng)用研究.pdf

1、算法是計(jì)算機(jī)科學(xué)的靈魂,算法的研究是計(jì)算機(jī)研究的重要領(lǐng)域之一。算法的可靠性、正確性和生產(chǎn)效率一直是算法設(shè)計(jì)領(lǐng)域中的關(guān)鍵問題,受到各國學(xué)者的高度重視。基于遞推技術(shù)的算法設(shè)計(jì)方法通過對(duì)問題程序規(guī)約的數(shù)學(xué)變換,得到問題求解的遞推關(guān)系,以此為基礎(chǔ)獲到問題的算法程序。由于問題求解的遞推關(guān)系是經(jīng)過嚴(yán)格數(shù)學(xué)變換得到的,因而可以保證遞推關(guān)系的正確性,從而保證了算法的正確性。同時(shí),由于最終所求解的算法是建立在遞推關(guān)系的基礎(chǔ)上,每一步的求解都建立在前面已求

2、解子問題解的基礎(chǔ)之上,避免了很多重復(fù)計(jì)算,因而可以有效地提高算法程序的效率。
　　另外,在經(jīng)歷了多年的發(fā)展歷程后,形成了五大類傳統(tǒng)的算法設(shè)計(jì)方法:分治法、貪心法、動(dòng)態(tài)規(guī)劃法、回溯法和分枝限界法。但是,當(dāng)算法設(shè)計(jì)者在面對(duì)一個(gè)具體的問題時(shí),到底采用哪種算法設(shè)計(jì)方法來求解問題,這并沒有一定的規(guī)律可遵循。我們經(jīng)過長期的研究發(fā)現(xiàn),基于遞推技術(shù)的算法設(shè)計(jì)方法可以解決某些傳統(tǒng)算法設(shè)計(jì)方法解決的問題,為算法設(shè)計(jì)提供了一較通用的途徑。
　　本