PDF《(19)的解决 *》

Cn, 则有 S( n) =Fn.此时, 合并插入方法也是最 优的. 文章所要研究的就是集合 N2 中15 和19 两个 元素的 S( n) 的证明问题.

2 相关的工作 在表

1 中, 第一个需要证明的 S( n) 是S( 12) .

1965 年, Wells 使用穷举法证明 S( 12) >

29, 即S( 12) = 30, 从而证明了当 n 为12 时, 合并插入排序方法是 最优的[3] .假设 Rc 是经过 c 次比较得到的偏序的集 合, r∈Rc, uj 和uk 是r中两个不相关的元素, r1=r+ ujuk, r2=r+ukuj. Wells 证明了如果 r1 和r2 都能经过 Cn- c-

1 次比较完成排序,则r能经过 Cn- c 次比较完成 排序;

如果所有不相关的元素对( uj, uk) 都不能生成这 样的 r1 和r2,则r不能经过 Cn- c 次比较完成排序. Wells 算法首先测试 r1 和r2 中的任一个,若不能经 Cn- c-

1 次完成排序, 则另一个不必再考虑. 如果 RCn = !, 则可以断定 S( n) >

Cn.用Wells 算法计算 S( 12) 时, 得到 R24=R25=…=R29=!, 因此有 S( 12) =F12=30. 因 为在每次比较以后, Wells 算法只向 Rc 中加入了一 个新的偏序 r1 或r2,所以另一个能否在 Cn- c-

1 次比 较后完成排序是不确定的.此时, 如果 RCn ≠!, Wells 算法不能断定 S( n) 与Cn 是否相等, 需要通过其它方 法来判断. 在计算 S( 13) 、 S( 14) 时, Wells 算法就遇到 了这一问题. 这以后的几十年中,最少比较排序问题的研究 几乎没有什么显著进展.直到

2002 年, Peczarski 计 算证明了 S( 13) =34[4] .2004 年他又并进一步计算证 明了 S( 14) =38 和S( 22) =71[5] .Peczarski 算法是在 Wells 算法的基础上, 通过增加一个阶段测试, 解决 了RCn ≠!, S( n) 是否等于 Cn 的判定问题. 但是, 在计 算S( 15) 和S( 16) 的时候, Peczarski 算法遇到了问 题.它的计算量非常巨大, 以至于现有计算机条件根 本无法完成.在n较大时, Peczarski 算法只能解决一 表1Fn 和Cn 的关系比较 Table

1 The relationship between Fn and Cn n

2 3

4 5

6 7

8 9

10 11

12 13 Cn

1 3

5 7

10 13

16 19

22 26

29 33 Fn

1 3

5 7

10 13

16 19

22 26

30 34 n

14 15

16 17

18 19

20 21

22 23

24 Cn

37 41

45 49

53 57

62 66

70 75

80 Fn

38 42

46 50

54 58

62 66

71 76

81 306 些特殊形式, 例如 S( 22) . 最少比较排序问题的核心是 Rc 的计算问题, 作 者在 Wells 和Peczarski 工作的基础上,给出了一个 新的 Rc 计算算法, 成功地证明了 S( 15) =42 和S( 19) = 58.据作者所知, 这一证明结果是世界上首次发表.

3 文章算法 文章给出了一个用于解决最少比较排序问题的 算法.该算法的基本步骤可以分为两大部分: 第一, 偏序的计算, 其核心是线性扩展计数的计算, 这一部 分仍然使用 Wells 算法,作者对其进行了一些改进;

第二, Rc 的计算,这里给出了一个新算法―― ―PS ( Posets Sorting) 算法取代 Peczarski 算法. 3.1 线性扩展计数 线性扩展计数的计算是计算 S( n) 的过程中最重 要的步骤之一.在用 Wells 算法计算 S( 13) 的过程 中,计算线性扩展计数的时间占程序总运行时间的 70%以上. 定义

1 线性扩展 设r为集合 U 上的偏序, rL 是U上的一个全序. 对于 U 中任意的元素 x, y, 如果( x, y) ∈r, 有( x, y) ∈rL,那么称 rL 是r的一个线性扩展. 求偏序的线性扩展数问题称为线性扩展计数 ( Counting Linear Extensions) 问题.Brightwell 和Win- kler 证明了线性扩展计数是 NP 完全问题[6] .Kahn 和Saks 证明了总存在一次比较把一个偏序的线性扩展 分为两组, 数量比例在 3/8 和8/3 之间, 但是他们没 有给出找出这样比较的方法[7] .Peczaski 证明了若偏 序r能在 c 次比较以后完成排序, 则r的线性扩展数 e( r) ≤2c ;