- 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
您可能关注的文档
- 苏教版新版二年级上册数学期末试卷1.docx
- 苏教版新一年级下数学期末模拟卷.docx
- 苏教版新译林三年级英语下册短语专练.docx
- 苏教版一年级第八单元练习看图列示.docx
- 苏教版一年级第十单元重难点复习试卷.docx
- 苏教版一年级认位置练习题.docx
- 苏教版一年级上册数学典型错题.docx
- 苏教版一年级上册数学教案《认识加法》.docx
- 苏教版一年级上册数学教学计划.docx
- 苏教版一年级上册数学精练题.docx
- 浙江省临海市白云高级中学2025届高三历史3月月考试题.doc
- 云南拾谷县第一中学2024_2025学年高二物理上学期10月月考试题.doc
- 2025版高考生物总复习第13讲基因的分离定律教案苏教版.doc
- 湖北省黄石实验高中2024_2025学年高一历史下学期期末考试模拟卷.doc
- 通史版2025版高考历史大一轮复习专题七近代化的曲折发展__中日甲午战争至五四运动前4第4讲从维新思想到新文化运动课后达标检测含解析新人教版.doc
- 2024年高考数学考试大纲解读专题04导数及其应用含解析文.doc
- 河南省许汝平九校联盟2024_2025学年高一语文上学期期末考试试题扫描版无答案.doc
- 江西省吉安市吉水县第二中学2024_2025学年高一历史上学期第二次月考试题.doc
- 北京市平谷区2025届高三政治一模考试试题含解析.doc
- 2025届中考物理第四讲物态变化专项复习测试无答案新人教版.docx
最近下载
- 武汉理工大学《高等数学》2022-2023学年第一学期期末试卷及答案.docx
- 《企业财务会计》全套PPT课件.pptx
- 社会体育建设方案-专业教学资源库备选项目材料.pdf VIP
- 美的品牌案例分析.pptx VIP
- 美的案例分析.pptx VIP
- 小学生秋季学期第1-20周国旗下讲话稿(新).pdf
- 边做边学——Dreamweaver CS6网页设计案例教程(第3版)(共12单元)01.ppt VIP
- 武汉理工大学2023-2024学年第1学期《高等数学(上)》期末考试试卷(A卷)附参考答案.pdf
- 清洁生产与循环经济( 第二版) 教学课件 作者 奚旦立徐淑红高春梅 主编 第4章 清洁生产.ppt
- 美的品牌案例分析.pptx VIP
文档评论(0)