打字猴:1.70050741e+09
1700507410
1700507411 这种经典算法与数据结构的例子网上有很多,其中queens(8)这一部分是可以修改的,“8”代表的是8×8的棋盘,放置8个皇后。如果改成queens(16),就是在一个“改造”过的16×16的棋盘上求解一个十六皇后问题了。
1700507412
1700507413 为了展示这种穷举法在八皇后问题扩展上的“缺陷”,需要对刚刚的程序做一下简单的改造,把它改造成一个能够处理“N皇后问题”的程序。
1700507414
1700507415 程序的前部改为:
1700507416
1700507417 import sysnumber=int(sys.argv[1])
1700507418
1700507419 程序的后部改为:
1700507420
1700507421 if __name__==“__main__”:    i=0    for solution in queens(number):        i+=1    print ‘total test:’ + str(pow(number,number))+ ‘; total solution:’ + str(i)+ ‘\n’
1700507422
1700507423 这样就可以打印出所有的尝试次数和有效解的个数,并且,只在终端输出个数,而不输出具体解出的盘面。
1700507424
1700507425 接下来,就可以用命令行从1开始逐步尝试。
1700507426
1700507427 [root@ann science]# time python eight.py 1total test:1; total solution:1    real 0m0.011suser 0m0.003ssys 0m0.008s[root@ann science]# time python eight.py 2total test:4; total solution:0    real 0m0.010suser 0m0.006ssys 0m0.004s[root@ann science]# time python eight.py 3    total test:27; total solution:0real 0m0.011suser 0m0.008ssys 0m0.005s[root@ann science]# time python eight.py 4total test:256; total solution:2    real 0m0.009suser 0m0.003ssys 0m0.006s[root@ann science]# time python eight.py 5total test:3125; total solution:10    real 0m0.031suser 0m0.017ssys 0m0.014s[root@ann science]# time python eight.py 6total test:46656; total solution:4    real 0m0.011suser 0m0.007ssys 0m0.004s[root@ann science]# time python eight.py 7total test:823543; total solution:40    real 0m0.053suser 0m0.018ssys 0m0.035s[root@ann science]# time python eight.py 8total test:16777216; total solution:92    real 0m0.030suser 0m0.023ssys 0m0.007s[root@ann science]# time python eight.py 9total test:387420489; total solution:352    real 0m0.081suser 0m0.077ssys 0m0.004s[root@ann science]# time python eight.py 10total test:10000000000; total solution:724    real 0m0.320suser 0m0.316ssys 0m0.004s[root@ann science]# time python eight.py 11total test:285311670611; total solution:2680    real 0m1.723suser 0m1.717ssys 0m0.006s[root@ann science]# time python eight.py 12total test:8916100448256; total solution:14200    real 0m10.202suser 0m10.185ssys 0m0.016s[root@ann science]# time python eight.py 13total test:302875106592253; total solution:73712    real 1m3.286suser 1m3.273ssys 0m0.009s[root@ann science]# time python eight.py 14total test:11112006825558016; total solution:365596    real 7m18.573suser 7m18.562ssys 0m0.017s
1700507428
1700507429 再往下测试的话时间就非常长了。在这里我只测试到14个皇后的情况(如表11-2和图11-5所示)。这种单线程的计算效率几乎完全依赖单CPU核心的主频。
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 盘面宽度-单次试探时间
[ 上一页 ]  [ :1.70050741e+09 ]  [ 下一页 ]