摘要
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.
本文研究随机排列的最优成组剖分问题。这一问题源于铁路列车的最优调度计划方法的设计问题。寻找切实可行的有效算法是问题的焦点。1978年这一问题被列入文献的公开问题之一。1986年许国志、陈庆华和刘继勇提出猜测:此乃NP-完全问题,即多项式时间的算法可能不会存在,除非NP=P。 本文引入一种强同构剪枝策略,以标号树形上的隐式枚举法为工具,得到了上述问题精确最优解的一个算法。其计算时间复杂度为O(n^32^(n-2)),其中n为随机排列中相异数字的个数。算法在给定n的条件下,关于随机排列的长度是二次稳定的。因此,由铁路工程实际需要来看,该算法是切实可行的。至此,文献的公开问题得解。特别地,本文将此类问题归入两步优化结构模式,使问题的几何特征有明显的表露。这一策略在相关的领域中有着良好的应用前景。
