软件学报
軟件學報
연건학보
JOURNAL OF SOFTWARE
2003年
2期
183-189
,共7页
算法%计算复杂性%进化树%基因组%翻转距离
算法%計算複雜性%進化樹%基因組%翻轉距離
산법%계산복잡성%진화수%기인조%번전거리
讨论翻转距离星树问题,将3SAT问题归约到目标序列部分固定的翻转距离星树问题,证明实例中当有向符号序列个数为3时,若目标序列符号顺序固定,且有部分符号方向给定,则只确定其余符号方向以使得目标序列与已知3条给定序列翻转距离之和最小所对应的翻转距离星树问题也是NP-难解问题.同时,还给出了该问题的多项式时间近似算法.
討論翻轉距離星樹問題,將3SAT問題歸約到目標序列部分固定的翻轉距離星樹問題,證明實例中噹有嚮符號序列箇數為3時,若目標序列符號順序固定,且有部分符號方嚮給定,則隻確定其餘符號方嚮以使得目標序列與已知3條給定序列翻轉距離之和最小所對應的翻轉距離星樹問題也是NP-難解問題.同時,還給齣瞭該問題的多項式時間近似算法.
토론번전거리성수문제,장3SAT문제귀약도목표서렬부분고정적번전거리성수문제,증명실례중당유향부호서렬개수위3시,약목표서렬부호순서고정,차유부분부호방향급정,칙지학정기여부호방향이사득목표서렬여이지3조급정서렬번전거리지화최소소대응적번전거리성수문제야시NP-난해문제.동시,환급출료해문제적다항식시간근사산법.
