刘佳樽_算法设计与分析_第5-6章

《刘佳樽_算法设计与分析_第5-6章》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、—皇后问题n10,00050,000100,000500,0001,000,0003,000,0006,000,00010,000,00030,000,00060,000,000m1111111111g)9.00104.422180739690728807430400288.2639.09.416.729078365000020072855069308955419806000002.96.79480228.21.90507479000060000Ig0.92.012.64.24.865.836.4&7.8.t(n)5472556995290874844

2、721g1.184.035.28.59.7311.6712.131516n845128890.8.7.9408487431g1.786.517.812.14.617.519.202325n275768071735.0.6.46822261Ign455.666.476.777.7.4.699977847778978线性回归表达式lgt(n)=k*Ign+b:y=2.0348x-7.3401二、图的m着色问题问题用到的颜色总数m（色数）搜索过的结点总数L程序运行时间T（单位：s）22个基站540740.1242个基站5530.23LX42&3&1&2&3&28

3、4&2&2&3&4&1&2&1&3&4&3&1&43&3&5&2&3&2&4&4&5&1&5&2&2&5a4去-总⑥可行解数量为，1抄索过得节点总藪为：43tine:0.023000seconds三、旅行商问题问题求解算法最短回路路径总长度（单位：m）搜索过的结点总数程序运行时间（单位：S）22个基站回溯20->5->11->22->18->6->4->8->19->10・>1->21->14->12->15->2->13->3->16->7->9->17->209032.567799936611.85分支限界20->5->11->22->18->6->4

4、->8->19->10->1->21->14->12->15->2->13->3->16->7->9->17->209032.56122678813.98站4->29->24->16->11->18->8->12->22->15->25->26->27->21・>28・>23・>19・>9>3・>5・>6・>7・>30・>1->2->14->10->17>4牛>29->24->16->11->18->8->12->22->15->25->26->27->21_・>28・>23・>19・>9>3・>5・>6・>7・>30・〉1->2->14->10->17>

5、4182981918112079.488221334512079.430tine：907.93Sseconds从起始城市岀发的最短旅行路径为t1->29-〉24・>16・>11->18・>8->12->22->20->15->25->26->27->21->28->23->19->9->3->5->6->7->30->13->4->2->14质少览总般程为，927扫险宼的玻索树结点总数为=1821946241回30溯个基819.319538.94分支限界源代码一.N皇后问题//N-皇后问题的快速局部搜索算法//参考:RokSosicandJunGu.APo

6、lynomialTimeAlgorithmfortheN-QueensProblem.SIGARTBulletin,1(3):7-11,1990.#inelude,,stdafx.hH#inelude#inelude#inelude#ineludelong*pSolution=NULL;//解longN=1000;//皇后个数intsqrt_N;〃用于产生范围在0~的随机数longNumCollisions;//当前解的冲突总数//正对角线，同一条对角线上i-pSolution[i]为

7、常数，下标范围-(N-l)~映射到0~(2N-2)[通过+(N-l)]long*pPosDiagonal;〃负对角线，同一条对角线上i+pSolution[i]为常数，下标范围0~(2N-2)long*pNegDiagonal;/*本函数交换两个单元*/inlinevoidSwap(long&x,long&y){longtemp;temp=y;y=x；x=temp;}/*本函数用于生成一个随机排列，作为初始解*/voidGeneratePermutation(){for(longi=0;i

8、longrand_index;for(longi=0;i