打字猴:1.70050743e+09
1700507430
1700507431 表11-2 N皇后求解时间表
1700507432
1700507433   盘面宽度     穷举次数     解个数     时间(秒)     1     1     1     003     2     4     0     006     3     27     0     008     4     256     0     003     5     3125     10     017     6     46656     4     007     7     823543     40     0.018     8     16777216     92     0.023     9     387420489     352     0.077     10     10000000000     724     0.316     11     285311670611     2680     1.717     12     8916100448256     14200     10.185     13     302875106592253     73712     63.273     14     11112006825558016     365596     438.562   这种试探次数的增加,在N皇后问题场景中随着盘面宽度n的增加而迅速增加(如图11-5所示)。显然,这个时间复杂度是O(nn),几乎是在二维空间解中效率最差的一种情况了。
1700507434
1700507435
1700507436
1700507437
1700507438 图11-5 盘面宽度-穷举次数
1700507439
1700507440 测试的时间目测也是按照O(nn)来增加的(如图11-6所示)。为了验证我们的观点,下面用“叠加法”来估算单次试探所需要的时间。由于单次试探的时间太短,所以任何一次测量都会产生非常大的误差。我们只看盘面宽度为8以前的各次测试所花费的时间就可以了。
1700507441
1700507442
1700507443
1700507444
1700507445 图11-6 盘面宽度-时间(秒)
1700507446
1700507447 这两组数据几乎看不出任何联系,波动太大,所以不建议参与统计(如图11-7所示)。
1700507448
1700507449
1700507450
1700507451
1700507452 图11-7 穷举次数与花费的时间(秒)
1700507453
1700507454 盘面宽度和单次试探时间的关系像是一条渐近线,随着盘面宽度的增加,单次试探时间无限趋近于0(如表11-3和图11-8所示)。实际上,这个试探时间无论如何是不可能为0的。
1700507455
1700507456
1700507457
1700507458
1700507459 图11-8 盘面宽度-单次试探时间
1700507460
1700507461 表11-3 N皇后求解盘面宽度为N与N-1时的单次试探时间比
1700507462
1700507463   盘面宽     b单次试探时间(秒)     盘面宽度为N与N-1时的单次试探时间比     9     1.9875E-10     0.144977364     10     3.16E-11     0.158993344     11     6.01798E-12     0.190442413     12     1.14232E-12     0.189817095     13     2.08908E-13     0.182881075     14     3.94674E-14     0.188922486   这就表明,N每增加1,平均每次试探的时间就会变为之前的0.18倍左右(如图11-9所示)。这样我们可以猜测:当N=15时,单次的平均时间可能还会继续以这个比例下降。
1700507464
1700507465
1700507466
1700507467
1700507468 图11-9 盘面宽度为N与N – 1时的单次试探时间比
1700507469
1700507470 N=15的情况如下。
1700507471
1700507472 [root@ann science]# time python eight.py 15total test:437893890380859375; total solution:2279184    real 52m46.628suser 52m46.265ssys 0m0.094s
1700507473
1700507474 计算结果如表11-4所示。可以看出,平均单次试探时间下降为前一次的0.18倍左右。
1700507475
1700507476 表11-4 N皇后问题求解时间(N=15)
1700507477
1700507478
1700507479
[ 上一页 ]  [ :1.70050743e+09 ]  [ 下一页 ]