| 最小费用排序问题 |
| |
| 引用本文： | 金友良,张同全.最小费用排序问题[J].云南民族大学学报(自然科学版),2007,16(3):222-224. |
| |
| 作者姓名： | 金友良 张同全 |
| |
| 作者单位： | 1. 浙江省丽水职业技术学院,浙江丽水,323000
2. 云南民族大学数学与计算机科学学院,云南昆明,650091;云南大学物理科学技术学院非线性中心,云南昆明,650091 |
| |
| 基金项目： | 云南省教育厅科学研究基金项目(06J011A) |
| |
| 摘 要： | 两类最小费用排序问题—费用函数满足三角不等式的最小费用排序问题和费用函数不满足三角不等式的最小费用排序问题.利用排序问题的O(nln(n))算法、图论和网络流理论分别给出了这两类问题的离线的最优多项式算法,并分别给出了这2个算法的最优性和计算复杂性分析.
|
| 关 键 词： | 排序 三角不等式 网络流 计算复杂性 |
| 文章编号： | 1672-8513（2007）03-0222-03 |
| 收稿时间： | 2006-04-02 |
| 修稿时间： | 2006-04-02 |
Minimum Cost Sorting Problem |
| |
| Jin Youliang,Zhang Tongquan.Minimum Cost Sorting Problem[J].Journal of Yunnan Nationalities University:Natural Sciences Edition,2007,16(3):222-224. |
| |
| Authors: | Jin Youliang Zhang Tongquan |
| |
| Institution: | 1, Lishui Vocational and Technical College, Lishui 323000, China; 2. Department of Mathematics and Computer Science, Yunnan Nationality University, Kunming 650031, China; 3. Center for Nonliner Complex Systems, College of Physical Science and Technique, Yunnan University, Kunming 650091. China |
| |
| Abstract: | In this paper,we consider two new types of sorting problems-Minimum cost sorting problem with cost function satisfies triangle inequality and minimum cost sorting problem without cost function does not satisfy triangle inequality.We give two optimal and polynomial off-line algorithms for them by using O(nln(n)) algorithm of sorting problem,and analyze their correctness and computational complexity. |
| |
| Keywords: | sorting problem triangle inequality network flow computational complexity |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
|
