欢迎您！东篱公司
退出
-
申报数据库
-
立项数据库
-
成果数据库
-
项目获奖数据库
中文摘要：
提出了对换排序的赋权模型，定义一个长度为l的对换的费用是f（l）=l^n，α〉0；分别给出了当0〈α〈1和1〈α〈2时，二元序列赋权对换排序问题的近似算法；证明了当α≥2时。起泡排序算法是此问题的精确算法．
英文摘要：
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^n, α 〉 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.
同期刊论文项目
同项目期刊论文
期刊信息
位置：