计算机工程与设计
計算機工程與設計
계산궤공정여설계
COMPUTER ENGINEERING AND DESIGN
2014年
6期
2170-2173
,共4页
最长公共子序列%最优予结构%动态规划%随机路径选择%最优解
最長公共子序列%最優予結構%動態規劃%隨機路徑選擇%最優解
최장공공자서렬%최우여결구%동태규화%수궤로경선택%최우해
the longest common subsequence%optimal substructure%dynamic programming%random path selection%optimal solution
针对传统算法只能求出一个最长公共子序列而无法求出多个最长公共子序列,设计了一种可求多个最长公共子序列的算法.简述了最长公共子序列的算法原理,描述了求最长公共子序列长度的动态规划算法,在此基础上求出一个最长公共子序列,通过对算法改进得到可求多个最长公共子序列的随机路径选择算法.该算法具有计算速度快、占用内存小、计算机易于实现等优点.其核心是寻优路径的选择,提出了寻找最优解的路径选择问题,讨论并给出了搜索多个可行解的快速算法,该算法充分利用了动态规划算法计算过程中提供的寻优方向信息得到最优路径的随机选择算法,与传统算法相比可求多个最长公共子序列.
針對傳統算法隻能求齣一箇最長公共子序列而無法求齣多箇最長公共子序列,設計瞭一種可求多箇最長公共子序列的算法.簡述瞭最長公共子序列的算法原理,描述瞭求最長公共子序列長度的動態規劃算法,在此基礎上求齣一箇最長公共子序列,通過對算法改進得到可求多箇最長公共子序列的隨機路徑選擇算法.該算法具有計算速度快、佔用內存小、計算機易于實現等優點.其覈心是尋優路徑的選擇,提齣瞭尋找最優解的路徑選擇問題,討論併給齣瞭搜索多箇可行解的快速算法,該算法充分利用瞭動態規劃算法計算過程中提供的尋優方嚮信息得到最優路徑的隨機選擇算法,與傳統算法相比可求多箇最長公共子序列.
침대전통산법지능구출일개최장공공자서렬이무법구출다개최장공공자서렬,설계료일충가구다개최장공공자서렬적산법.간술료최장공공자서렬적산법원리,묘술료구최장공공자서렬장도적동태규화산법,재차기출상구출일개최장공공자서렬,통과대산법개진득도가구다개최장공공자서렬적수궤로경선택산법.해산법구유계산속도쾌、점용내존소、계산궤역우실현등우점.기핵심시심우로경적선택,제출료심조최우해적로경선택문제,토론병급출료수색다개가행해적쾌속산법,해산법충분이용료동태규화산법계산과정중제공적심우방향신식득도최우로경적수궤선택산법,여전통산법상비가구다개최장공공자서렬.
