針對可計算n的最短加法鏈問題,提出了一種快速算法,利用貪心算法思路,從1開始不斷翻倍,當(dāng)翻倍后大于n時,進(jìn)行向前遍歷,使得結(jié)果小于等于n,在此基礎(chǔ)上利用深度優(yōu)先搜索算法得到當(dāng)前可行解及其深度d,深度超過d時對當(dāng)前分支不再進(jìn)行搜索以減少空間復(fù)雜度,但是當(dāng)加法鏈擴(kuò)散出去后時間復(fù)雜度上會呈指數(shù)增長,所以再結(jié)合一些剪枝函數(shù),進(jìn)行剪枝操作以減少時間復(fù)雜度,進(jìn)而在一個有效時間內(nèi)得到較好的解。針對7類挑戰(zhàn)問題,利用Eclipse平臺編寫改進(jìn)算法,給出具有最短加法鏈長度的數(shù)及其加法鏈表示;加法鏈能應(yīng)用到模指數(shù)的冪運算中,而模指數(shù)的冪運算是公鑰密碼學(xué)中的核心運算之一,因此改進(jìn)最短加法鏈的快速算法可以提高公鑰密碼體制的執(zhí)行速度。 

【文章來源】：沈陽師范大學(xué)學(xué)報(自然科學(xué)版). 2019,37(05)

【文章頁數(shù)】：5 頁

【文章目錄】：
0 引 言
1 貪心算法
2 深度優(yōu)先搜索算法
3 剪枝函數(shù)與優(yōu)化
4 結(jié)果分析
5 結(jié) 論


【參考文獻(xiàn)】：
期刊論文
[1]基于最短加法鏈狀態(tài)空間樹的IAPWS-IF97快速計算方法[J]. 芮嘉敏,孫振業(yè),程懋華.  汽輪機(jī)技術(shù). 2017(04)
[2]最短加法鏈的隨機(jī)冪樹方法[J]. 江順亮,許慶勇,黃偉,葉發(fā)茂,徐少平.  計算機(jī)科學(xué). 2015(03)
[3]幾種方冪模快速算法的加法鏈一致性分析[J]. 董付國,厲玉蓉.  計算機(jī)工程與應(yīng)用. 2010(36)
[4]最短加法鏈算法[J]. 王曉東.  小型微型計算機(jī)系統(tǒng). 2001(10)



本文編號：3388359