- 1、本文档共4页,可阅读全部内容。
- 2、原创力文档(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
- 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载。
- 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“版权申诉”(推荐),也可以打举报电话:400-050-0827(电话支持时间:9:00-18:30)。
算法的分类与8皇后问题
精确算法(全局最优)
穷举搜索、动态规划、回溯法、分支定界法等。
这类算法适合需要最优解但是问题规模比较小的情形。
随机算法
LasVegas算法、MonteCarlo算法等。对于各种问题,都能给出比较满意的解。
近似算法
具有多项式时间复杂度,不能求出最优解,但是可以估计近似解与最优解的误差。
启发式算法(局部最优)
贪心算法、局部搜索、遗传算法、模拟退火算法、神经网络算法、蚁群算法等。
适合规模很大又非常难处理,不一定需要最优解的问题。
具体采用什么样的算法来解决实际问题,完全取决于实际问题的需要以及设计者对算法的理解和创新的能力。
8皇后问题
在国际象棋的棋盘上放置8个皇后,使得它们互相不攻击。
经典的解法是回溯法,但效率较低,编程较困难。现采用随机算法,效率要提高一倍多,但算法有可能失败,成功的近似概率为0.13。
Step1算法描述
Step1
Step2置k=1,在第一行随机选择一个位置放置一个皇后,k++;
Step2
Step3计算k行所有可行的位置,即在这些位置放置一个皇后不会与前面已经放置的皇后相互攻击;
Step3
如果找不到可行的位置,则返回失败,程序结束;
否则从可行的位置中随机选择一个位置放置一个皇后,k++;
Step4如果k8,则返回成功并输出8皇后放置的结果,程序结束;否则转Step2;
Step4
Mathematica程序如下:
n=8;success=1;
k=1;x=Table[0,{n}];ok=Table[0,{n}];
x[[1]]=Random[Integer,{1,8}];k++;While[k=n,
count=0;
For[i=1,i?n,i++,x[[k]]=i;Placek=1;For[j=1,j?k-1,j++,If[Abs[k-j]?Abs[x[[j]]-x[[k]]]||x[[j]]?x[[k]],Placek=0];];
If[Placek?1,count++;ok[[count]]=i;];];
Print[ok=,ok,count];If[count?0,success=0;Break[];];i=ok[[Random[Integer,{1,count}]]];x[[k]]=i;k++;
Print[x=,x];
]
If[success?1,x,False]
思考: 本问题的数学模型?
数学模型
目标 X?{x,x
1 2
?x?x ,
? i j
,...x, }
8
i,j? 1,2,..i.?,j8,
约束 ?x
? i
?x ?i?j, i,j? 1,2,..i.?,j8,
j
??x
?
i
?{1,2,...,8i}?, 1,2,...,8
Lingo程序如下:
model:
sets:
S/1..8/:x;
SS(S,S);
endsets
@for(SS(i,j)|i#LT#j:@abs(x(i)-x(j))1);@for(SS(i,j)|i#LT#j:@abs(@abs(x(i)-x(j))-@abs(i-j))1);@for(S:@Bnd(1,x,8));
@for(S:@Gin(x));end
运行结果:
!Linearizationcomponentsadded:Constraints: 336
Variables: 336
Integers: 84
Feasiblesolutionfoundatiteration: 63327
Variable Value
X(
1) 2.000000
X(
2) 5.000000
X(
3) 7.000000
X(
4) 4.000000
X(
5) 1.000000
X(
6) 8.000000
X(
7) 6.000000
X(
8) 3.000000
您可能关注的文档
最近下载
- 申能(集团)有限公司行测笔试题库2022.pdf
- 第18课《我的白鸽》课件+2024—2025学年统编版语文七年级上册.pptx VIP
- 圣经与中国历史年对照表.doc
- Unit 4 Looking good,feeling good Reading 课件-高中英语牛津译林版(2020)必修第一册.pptx
- Traditional Chinese Festivals 中国传统节日微课教学设计.pdf
- 《第二章 直线和圆的方程》单元检测试卷与答案解析(共四套).docx
- (人教版)数学二年级上册计算题“天天练”习题卡,含100份题组.doc
- 第18课 我的白鸽 课件(共42张PPT) 2024-2025学年统编版语文七年级上册(2024).pptx VIP
- 医院管理交流课件_国家口腔医学质控中心工作报告.pptx
- 《中秋节》ppt课件(最新整理版).pptx VIP
文档评论(0)