| 二元序列的赋权对换排序问题 |
| |
| 引用本文： | 亓兴勤,何志红,赵洪銮. 二元序列的赋权对换排序问题[J]. 山东大学学报(理学版), 2006, 41(1): 82-85 |
| |
| 作者姓名： | 亓兴勤 何志红 赵洪銮 |
| |
| 作者单位： | 山东大学,数学与系统科学学院,山东,济南,250100;山东大学,数学与系统科学学院,山东,济南,250100;山东大学,数学与系统科学学院,山东,济南,250100 |
| |
| 摘 要： | 提出了对换排序的赋权模型，定义一个长度为l的对换的费用是f(l)=lα,α＞0；分别给出了当0＜α＜1和1＜α＜2时，二元序列赋权对换排序问题的近似算法；证明了当α≥2时，起泡排序算法是此问题的精确算法.
|
| 关 键 词： | 二元序列 对换排序 近似算法 |
| 文章编号： | 1671-9352（2006）01-0082-04 |
| 收稿时间： | 2005-04-19 |
| 修稿时间： | 2005-04-19 |
Sorting binary strings with length weighted transpositions |
| |
| QI Xing-qin,HE Zhi-hong,ZHAO Hong-luan. Sorting binary strings with length weighted transpositions[J]. Journal of Shandong University, 2006, 41(1): 82-85 |
| |
| Authors: | QI Xing-qin HE Zhi-hong ZHAO Hong-luan |
| |
| Affiliation: | School of Math. and Systems Sci., Shandong Univ,, Jinan 250100, Shandong, China |
| |
| 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. |
| |
| Keywords: | binary strings transposition approximation algorithm |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
| 点击此处可从《山东大学学报(理学版)》浏览原始摘要信息 |
|
点击此处可从《山东大学学报(理学版)》下载全文 |
|
