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 ]
[
下一页 ]