| 丁克诠.随机排列最优成组剖分的算法(英文)[J].数学研究及应用,1990,10(4):501~508 |
| 随机排列最优成组剖分的算法(英文) |
| An Algorithm for Minimal Number-Grouped Partitions of Random Permutations |
| 投稿时间：1988-06-24 |
| DOI：10.3770/j.issn:1000-341X.1990.04.006 |
| 中文关键词: |
| 英文关键词: |
| 基金项目: |
|
| 摘要点击次数: 1849 |
| 全文下载次数: 908 |
| 中文摘要: |
| 本文研究随机排列的最优成组剖分问题。这一问题源于铁路列车的最优调度计划方法的设计问题。寻找切实可行的有效算法是问题的焦点。1978年这一问题被列入文献的公开问题之一。1986年许国志、陈庆华和刘继勇提出猜测:此乃NP-完全问题,即多项式时间的算法可能不会存在,除非NP=P。 本文引入一种强同构剪枝策略,以标号树形上的隐式枚举法为工具,得到了上述问题精确最优解的一个算法。其计算时间复杂度为O(n32n-2),其中n为随机排列中相异数字的个数。算法在给定n的条件下, |
| 英文摘要: |
| In this paper, by means of a kind of strongly isomorphic cutting-branch technique, an algorithm for the problem of finding the minimal number-grouped partitions of random permutations is given, and the open problem in [ 1] is solved. |
| 查看全文 查看/发表评论 下载PDF阅读器 |
|
|
|
