Page for MCS problem

MCS(minimum comparison sorting)问题

在比较模型上，任何排序算法最坏情况的比较次数是Log2(n!)，在n比较小的情况是这样的：
n12345678910111213141516171819202122
C(n)0 1 3 5 7 10 13 16 19 22 26 29 33 37 41 45 49 53 57 62 66 70

在[1]中，作者提出了一个叫做merge insertion的算法，这个算法几乎能够达到上述的这个下界，而且有些时候甚至能够达到这个下界。下面这个表就是他们的算法所能够达到的比较次数。其中红色的部分表示的是merge insertiong算法不能够达到最优的那些情况。
n12345678910111213141516171819202122
F(n)0 1 3 5 710 13 16 19 22 26 30 34 38 42 46 50 54 58 62 66 71

因此，一个问题就浮现了出来，那就是在这些红色的地方，merge insertion是不是最优的（因为C(n)只是指明了一个下界，并不表明最有算法就一定要达到这个界），如果证明了merge insertion在这些情况下不是最优的，那么能够找到更好的算法么？至少在这些特殊的n值上比merge insertion好。

方法

在[2]中，Wells想出了一个办法，然后在计算机程序的帮助下他算出了对 n = 12，实际上merge insertion算法是最优的，也就是S(n)（n个元素排序的最小比较次数）= F(n) = 30 > C(n).

Wells算法中有两个最消耗时间的步骤，第一个是求一个poset的线性扩展的数目，这个问题主要通过[2]的Chapter 7.2.2中给出的若干公式求得。另外一个是图的同构问题，具体地说就是判断两个poset是不是同构的，这里的poset是一个有向无环图。

在图的同构问题上，现在已经有了若干的算法，其中的一个是ullman [5] 的图同构算法，这个算法正是在[3]中使用的算法，也是我们下面的若干实验采用的办法。在这个问题上还有一些其他算法，比如VF [4]，nauty [6], [7]算法。[8]中对上面的这些算法进行了比较。

在Wells的算法中，对每个比较的两个可能的结果中，我们选择一个作为后面继续判断的poset，在这里，我们通过比较其线性扩展的个数来决定选取哪一个。Wells算法中认为，线性扩展越多的那个结果难度越大，因此更有可能在后面的过程中提前夭折，所以要选取着一个。

我们的基本想法，测试其他的策略，而不是简单的根据线性扩展的个数来进行选择。

实验结果(时间越早越靠后)

一些测试过的策略，都不理想，看来直接用e()策略很难改进

  1. 若干步骤遍历所有可能的分支选择
  2. 若干步骤使用所有分支
  3. LA1,LA2,LA3,MSF,MADF,MMDF,M1,M2,M3

n = 13 实验结果*

method 123456789101112131415161718192021222324252627282930313233
Marcin Peczarski 1 2 4 8 18 31 63 171 464 1261 3432 9087 22777 53308 110533 199145 304542 391277 418412 374911 276858 171595 91010 41735 17129 6532 2344 836 266 81 30 6 1
my src(273m) 1 2 4 8 18 33 68 178 476 1278 3449 9051 22644 53083 110409 199125 305145 393404 420731 376971 278970 173443 92282 42502 17609 6657 2416 868 289 88 33 6 1
LA1,M2(1.1) 1 2 4 8 18 33 70 186 489 1310 3560 9421 23507 54464 111588 200132 308764 406132 453532 432889 350755 243724 145449 75115 33928 13321 4647 1488 419 125 42 7 1

* 算法进行了改进，代码得到了优化，运行速度提升1/3。

n = 12 实验结果

method 1234567891011121314151617181920212223242526272829
Marcin Peczarski 1 1 2 3 4 8 15 36 71 116 183 260 340 316 258 165 95 40 25 17 11 3 0 0 0 0 0 00
my src(14.5s) 1 1 2 3 4 8 14 35 69 110 176 254 337 319 262 161 90 35 25 20 10 4 2 1 0 0 0 0 0
LA1,MSF(46.7s) 1 1 2 3 4 8 14 35 69 108 171 248 315 337 327 260 164 92 45 23 10 2 0 0 0 0 0 0 0
LA1,MADF(51.36s) 1 1 2 3 4 8 14 35 71 112 180 268 388 422 371 261 157 81 40 23 12 4 1 0 0 0 0 0 0
LA1,MMDF(40.91s) 1 1 2 3 4 8 14 35 69 111 175 255 336 313 230 127 69 29 24 18 8 1 0 0 0 0 0 0 0
LA1,M1(1.1)(43.39s) 1 1 2 3 4 8 14 35 69 112 174 255 320 300 233 161 131 106 96 81 65 47 32 13 6 0 0 0 0
LA1,M1(1.3)(37.46s) 1 1 2 3 4 8 14 35 69 112 174 257 320 285 204 116 57 25 15 6 2 2 1 0 0 0 0 0 0
LA2,M1(1.3)(141.52s) 1 1 2 3 4 8 14 35 69 112 174 257 313 274 196 115 60 32 17 6 2 2 1 0 0 0 0 0 0
LA1,M2(1.1)(42.14s) 1 1 2 3 4 8 14 35 69 109 167 242 295 283 239 177 129 108 92 76 64 45 28 11 4 1 1 1 1
LA2,M2(1.1)(145.02s) 1 1 2 3 4 8 14 35 69 109 167 245 293 277 214 141 83 42 24 9 6 4 2 0 0 0 0 0 0
LA2,M2(1.3)(140.38s) 1 1 2 3 4 8 14 35 69 109 167 245 290 271 200 122 71 32 22 15 10 8 5 1 0 0 0 0 0
LA3,M2(1.3)(894.28s) 1 1 2 3 4 8 14 35 69 109 167 245 290 269 198 121 69 31 22 15 10 8 5 1 0 0 0 0 0

n = 11 实验结果

method 123456789101112131415161718192021222324252627282930313233
Marcin Peczarski 1 2 5 11 26 58 147 409 1176 3369 8732 19490 36350 54082 62637 55612 38279 20545 8921 3232 1044 301 92 28 5 1 0 0 0 0 0 0 0
my src(1036.44s) 1 2 5 11 26 60 158 440 1259 3545 9068 20047 37165 54849 63323 56019 38328 20538 8921 3275 1068 304 97 29 5 1 0 0 0 0 0 0 0
LA1,M2(1.3)(>1h) 1 2 5 11 26 59 157 441 1260 3534 9101 20110 37390 54947 63356 56451 39506 21765 9693 3680 1206 366 114 32 6 1 0 0 0 0 0 0 0
LA1,M1(1.3)(>1h) 1 2 5 11 26 59 157 438 1254 3527 9025 20089 37417 54870 62897 55447 37890 20459 8938 3346 1129 351 113 34 6 1 0 0 0 0 0 0 0
LA1,M1(1.5)(>1h) 1 2 5 11 26 60 158 441 1260 3555 9114 20228 37445 54633 62309 54547 36992 19730 8593 3210 1077 331 102 29 5 1 0 0 0 0 0 0 0
LA1,M1(1.8)(>1h) 1 2 5 11 26 60 158 441 1261 3558 9122 20250 37531 54739 62463 54607 36884 19542 8452 3102 1030 306 96 30 6 1 0 0 0 0 0 0 0
LA1,MADF(>1h) 1 2 5 11 27 63 167 477 1372 3937 10363 23656 45641 70103 85687 82073 61019 35059 15826 5835 1804 504 121 29 6 1 0 0 0 0 0 0 0
LA1,MMDF(>1h) 1 2 5 11 26 60 158 440 1260 3556 9118 20279 37652 54996 62819 54975 37138 19716 8490 3106 1024 295 93 29 5 1 0 0 0 0 0 0 0

LA1: look ahead 1 step
MSF: minimum size first
MADF: maximum average difficulty first
MMDF: maximum minimum difficulty first
M1(a): 如果size相差达到a倍，那就用MSF，否则用MMDF
M2(a): 如果size相差达到a倍，那就用MSF，否则用MADF

红色代表该列最小
蓝色代表比该列的第一行的元素小

Marcin Peczarski指的是[3]中的结果。

参考文献

  1. L. Ford and S. Johnson, A Tournament Problem, American Mathematical Monthly, 66 (1959), 387–389.
  2. M. Wells, Elements of Combinatorial Computing, Pergamon Press, Oxford, 1971.
  3. Marcin Peczarski, New Results in Minimum-Comparison Sorting, Algorithmica (2004) 40: 133–145.
  4. L. P. Cordella, P. Foggia, C. Sansone, M. Vento, "An Efficient Algorithm for the Inexact Matching of ARG Using a Contextual Transformational Model", in Proceedings of the 13th ICPR, IEEE Computer Society Press, vol. III, pp. 180-184 (1996), http://msdlocal.ebi.ac.uk/docs/vf/
  5. J. R. Ullman, "An Algorithm for Subgraph Isomorphism", Journal of the Association for Computing Machinery, 23, pp. 31-42 (1976)
  6. Practical Graph Isomorphism, Congressus Numerantium, 30 (1981) 45-87. http://cs.anu.edu.au/~bdm/nauty/
  7. D. G. Corneil, C. C. Gotlieb, An Efficient Algorithm for Graph Isomorphism, Journal of the ACM (JACM) , Volume 17 , Issue 1 (January 1970),Pages: 51 - 64.
  8. P. Foggia, C. Sansone, and M. Vento. A performance comparison of five algorithms for graph isomorphism. In Proceedings of the 3rd IAPR-TC15 Workshop on Graph-based Representationsin Pattern Recognition, Ischia (Italy), May 2001.
最后更新，2006-06-15
点击这里源码下载，如有疑问，请联系我: shisheng AT mail.ustc.edu.cn