![](https://www.jinchutou.com/images/s.gif)
八皇后问题详细的解法-ppt课件
24页1、1,八皇后问题,2,1八皇后问题背景 2盲目的枚举算法 3加约束的枚举算法 4回溯法及基本思想 5 回溯法应用 6八皇后问题的递归回溯算法 7八皇后问题的非递归回溯算法,3,【背景】 八皇后问题是一个以国际象棋为背景的问题: 如何能够在 88 的国际象棋棋盘上放置八个皇后,使得任何一个皇后都无法直接吃掉其他的皇后?为了达到此目的,任两个皇后都不能处于同一条横行、纵行或斜线上。,4,八皇后问题,要在8*8的国际象棋棋盘中放8个皇后,使任意两个皇后都不能互相吃掉。规则:皇后能吃掉同一行、同一列、同一对角线的任意棋子。求所有的解。 八皇后的两组解,5,【问题分析】,设八个皇后为xi,分别在第i行(i=1,2,3,4,8); 问题的解状态:可以用(1,x1),(2,x2),(8,x8)表示8个皇后的位置; 由于行号固定,可简单记为:(x1,x2,x3,x4,x5,x6,x7,x8); 问题的解空间:(x1,x2,x3,x4,x5,x6,x7,x8),1xi8(i=1,2,3,4,8),共88个状态; 约束条件:八个(1,x1),(2,x2) ,(3,x3),(4,x4) ,(5,x5), (6
2、,x6) , (7,x7), (8,x8)不在同一行、同一列和同一对角线上。,原问题即:在解空间中寻找符合约束条件的解状态。,按什么顺序去搜? 目标是没有漏网之鱼,尽量速度快。,6,枚举得有个顺序,否则轻则有漏的、重复的;重则无法循环表示。,2 【问题设计】盲目的枚举算法,a 盲目的枚举算法 通过8重循环模拟搜索空间中的88个状态; 按枚举思想,以DFS的方式,从第1个皇后在第1列开始搜索,枚举出所有的“解状态”: 从中找出满足约束条件的“答案状态”。,约束条件?,1.按什么顺序去查找所有的解 a.盲目的枚举算法 void main() int x100; for (x1=1;x1=10;x1+) for (x2=1;x2=10;x2+) for (x3=1;x3=10;x3+) for (x4=1;x4=10;x4+) for (x5=1;x5=10;x5+) for (x6=1;x6=10;x6+) for (x7=1;x7=10;x7+) for (x8=1;x8=10;x8+) if (check(x)=0) printf(x); ,该如何解决冲突的问题呢? 1.行;我们是按照
3、行枚举的,保证了一行一个皇后; 2.列:判断是否存在xi=xj 3.对角线:主对角线的i-j与从对角线的i+j存在特殊关系,如图:,9,盲目的枚举算法,约束条件? 不在同一列:xixj; 不在同一主对角线上:xi-i xj-j; 不在同一负对角线上:xi+i xj+j。,违规的情况可以整合改写为: abs(xi - xj)=abs( i-j ) or (xi = xj),10,盲目的枚举算法,queen1( ) int a9; for(a1=1;a1=8;a1+) for(a2=1;a2=8;a2+) for(a3=1;a3=8;a3+) for(a4=1;a4=8;a4+) for(a5=1;a5=8;a5+) for(a6=1;a6=8;a6+) for(a7=1;a7=8;a7+) for(a8=1;a8=8;a8+) if (check(a,8)=0) continue; else for(i=1;i=8;i+) print(ai); ,check1(a,n) int i,j; for(i=2;i=n;i+) for(j=1;j=i-1;j+) if (ai=aj) or (a
《八皇后问题详细的解法-ppt课件》由会员葱**分享,可在线阅读,更多相关《八皇后问题详细的解法-ppt课件》请在金锄头文库上搜索。
![电信分公司2023年精神文明创建工作计划](https://union.03img.goldhoe.com/2024-6/12/1f9c43da-3349-4ac6-abef-ce7f31183131/186eaa8665af49339579e9f0e0e6a622.gif)
电信分公司2023年精神文明创建工作计划
![军车辆维修技术方案](https://union.03img.goldhoe.com/2024-6/12/c6a00142-2e5c-4051-8244-add2bad3dfdc/776fcdf261584e4f8e1fdc95a627f91f.gif)
军车辆维修技术方案
![课程授权使用合作协议书(精选5篇)](https://union.03img.goldhoe.com/2024-6/12/431327c5-2903-4de4-a433-296adaba9c55/832cb159043c4c6e9996d6ae2c1cdcd2.gif)
课程授权使用合作协议书(精选5篇)
![投标企业服务承诺书范文](https://union.03img.goldhoe.com/2024-6/12/ffc0dbe6-afe9-4f4c-bec3-3c952d6d48e6/3a7b9ad5d0544f28b154156668d985cd.gif)
投标企业服务承诺书范文
![基于教学评一体化的教学实践研究](https://union.03img.goldhoe.com/2024-6/12/af344ab8-3082-4125-b1ec-73184d5a85c5/b1a8be199b564ed5b8b6a3926eb36bd3.gif)
基于教学评一体化的教学实践研究
![行人横穿马路的感想](https://union.03img.goldhoe.com/2024-6/12/960f3cbd-7949-4bba-b235-2ece6b2e1e81/005805672a77439fbc1878e6b30645ca.gif)
行人横穿马路的感想
![2022年教师师德师风个人剖析材料三篇](https://union.03img.goldhoe.com/2024-6/12/146d59c6-68a6-4def-868f-9c09caaad503/e7d64acc0beb48cfb181223ec65b3433.gif)
2022年教师师德师风个人剖析材料三篇
![二年级上学期差转优个案分析](https://union.03img.goldhoe.com/2024-6/12/5016b07d-71c9-4b24-8295-d7ca83f25706/9608f81ca927402daedc805c6e381cae.gif)
二年级上学期差转优个案分析
![空气能设备采购合同](https://union.03img.goldhoe.com/2024-6/12/9c86a247-0326-4b0f-829c-46310d5ad147/6e5eb08308d9464d85b241fdc1c4acc9.gif)
空气能设备采购合同
![创业就业指导中心规章制度](https://union.03img.goldhoe.com/2024-6/12/7e94f730-ab41-40aa-9531-02132de509f1/1051f0d77a5a40908c29f80cd4d4e5ca.gif)
创业就业指导中心规章制度
![2023版学前教育专业人才需求调研报告及人培方案(普招)](https://union.03img.goldhoe.com/2024-6/12/cba693a3-8e20-48e7-b441-2a6abf7e4fad/550641d9744d4876bb0bf06686e4ab3b.gif)
2023版学前教育专业人才需求调研报告及人培方案(普招)
![保育员实训考场规章制度](https://union.03img.goldhoe.com/2024-6/12/08b67457-ef18-4079-9111-0de6abc9da3c/0ef366db43e94c94b62fece605e764ab.gif)
保育员实训考场规章制度
![机械设备租赁合同(通用版)](https://union.03img.goldhoe.com/2024-6/12/5ea68010-c0cb-4739-85c6-9191e0ff1f84/89e7682d135c4fcdbb362827f29b30a5.gif)
机械设备租赁合同(通用版)
![我最想养的小动物作文10篇范例](https://union.03img.goldhoe.com/2024-6/12/98490210-c3b5-44eb-a5d0-782e92950c93/7d5e9f4a96024922a5469d2149659b80.gif)
我最想养的小动物作文10篇范例
![学兔兔下载](https://union.03img.goldhoe.com/2024-6/12/6d82a6ba-f70f-48ae-8c8a-436594135226/0846452f0e1a4de8938dc34ad83729f1.gif)
学兔兔下载
![监考规章制度](https://union.03img.goldhoe.com/2024-6/12/2aceb88d-df8c-4bc9-b230-96478bf4dbc6/f2507843e4274b2fac4d6ee145344c87.gif)
监考规章制度
![美术教研记录含表格](https://union.03img.goldhoe.com/2024-6/12/60662cbd-c9b3-438e-b962-4a573049ee8d/f9ec633baf1e4d80921f066d6dca68b6.gif)
美术教研记录含表格
![人人讲安全个个会应急主题安全生产月征文范文6篇](https://union.03img.goldhoe.com/2024-6/12/7101a8c4-6046-4ac0-851e-2fac3ade3fd3/a9ebcbdc932c46898380d655f50fb11a.gif)
人人讲安全个个会应急主题安全生产月征文范文6篇
![三年级语文暑假作业布置](https://union.03img.goldhoe.com/2024-6/12/fc461f83-229f-4694-b90d-c913bf3337d1/23bbe11c2a6841978b5e2974efc5ac2a.gif)
三年级语文暑假作业布置
![北师大版小学六年级下册数学《面的旋转》教案(精选7篇)](https://union.03img.goldhoe.com/2024-6/12/606c6c9c-69d1-4e80-9ae9-e401c2915f91/105663f319714a35af090640c065beca.gif)
北师大版小学六年级下册数学《面的旋转》教案(精选7篇)
![电大最新版《公司概论》第二章公司的特征、功能和类型](/Images/s.gif)
2024-06-17 30页
![电大最新版《公司概论》第三章](/Images/s.gif)
2024-06-17 44页
![电大最新《城市管理学》课件第三章现代城市管理基础理论](/Images/s.gif)
2024-06-17 32页
![电大最新《城市管理学》课件第5章城市经济管理](/Images/s.gif)
2024-06-17 41页
![电大最新《城市管理学》课件第四章城市发展战略管理](/Images/s.gif)
2024-06-17 23页
![电大最新《城市管理学》课件第一章导论](/Images/s.gif)
2024-06-17 43页
![人民大2024汽车钣金实训教程(第二版) 课件实训八钣金零件的放样与下料](/Images/s.gif)
2024-06-13 10页
![人民大2024汽车钣金实训教程(第二版) 课件实训九钣金零件手工成型](/Images/s.gif)
2024-06-13 11页
![人民大2024汽车钣金实训教程(第二版) 课件实训十七车门玻璃 (可升降)的更换与调整](/Images/s.gif)
2024-06-13 11页
![人民大2024汽车钣金实训教程(第二版) 课件实训十六车身塑料件的维修](/Images/s.gif)
2024-06-13 9页