随机排列最优成组剖分的算法

本文研究随机排列的最优成组剖分问题。这一问题源于铁路列车的最优调度计划方法的设计问题。寻找切实可行的有效算法是问题的焦点。1978年这一问题被列入文献的公开问题之一。1986年许国志、陈庆华和刘继勇提出猜测:此乃NP-完全问题,即多项式时间的算法可能不会存在,除非NP=P。 本文引入一种强同构剪枝策略,以标号树形上的隐式枚举法为工具,得到了上述问题精确最优解的一个算法。其计算时间复杂度为O(n³2^n-2),其中n为随机排列中相异数字的个数。算法在给定n的条件下,

An Algorithm for Minimal Number-Grouped Partitions of Random Permutations

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.