【摘要】 提出了对换排序的赋权模型,定义一个长度为l的对换的费用是f(l)=lα,α>0;分别给出了当0<α<1和1<α<2时,二元序列赋权对换排序问题的近似算法;证明了当α2时,起泡排序算法是此问题的精确算法.更多还原

【Abstract】 The problem of sorting binary strings with length-weighted transpositions is considered,i.e.the cost of a transposition of length l is f(l)=l~α,α>0,rather than 1.Approximation algorithms are given for 0<α<1 and 1<α<2 respectively,and bubble sort is proved to be an exact algorithm for this problem when α2.The results have direct applications in computational biology to the field of comparative genomics.更多还原