人工智能VC++八皇后报告.docx
《人工智能VC++八皇后报告.docx》由会员分享，可在线阅读，更多相关《人工智能VC++八皇后报告.docx（45页珍藏版）》请在冰点文库上搜索。
人工智能VC++八皇后报告
（一）八皇后算法与编程声明
实现八皇后问题的人工智能算法有很多种，编程实现的方式也有很多种。
常用的方法有回溯法、CSP（约束满足问题）最小冲突的局部搜索法、爬山法、遗传算法等。
其中回溯法是解决八皇后问题最经典、最有效，也是最容易理解的算法。
本人在本次报告使用了以下三种算法编程解决八皇后的问题：
递归回溯法、爬山法和最小冲突的局部搜索算法，还有模拟退火算法，遗传算法等。
在本报告的后面将分为三个部分分别介绍递归回溯法、爬山法和最小冲突的局部搜索算法的算法分析、算法意义及三种算法的优缺点和适用范围。
并介绍使用MicrosoftVisualC++软件编程的具体步骤和算法的主函数分析及实现的功能
。
本次实验编程环境为MicrosoftVisualC++软件，建立在基于MFC平台上的运行程序。
界面生动美观，实现效果清晰可见。
本实验的八皇后算法、程序的界面和祝算法主函数主要参考以下资料。
1.人工智能——一种现代方法（第二版）
2.VC++深入详解（修订版）
3.中国知网关于八皇后问题分析及本报告所使用的三种算法有关的论文12篇，在此不一一列出赘述。
4.其余资料均来源于互联网，包括XX百科、XX知道、程序员开发网等。
下面分别介绍递归回溯法、爬山法和最小冲突的局部搜索算法及编程实现，并简要介绍模拟退火算法和遗传算法。
（二）八皇后问题的描述分析
一、八皇后问题描述
八皇后问题是一个古老而著名的以国际象棋为背景的问题：
如何能够在8×8的国际象棋棋盘上放置八个皇后，使得任何一个皇后都无法直接吃掉其他的皇后？
为了达到此目的，任两个皇后都不能处于同一条横行、纵行或斜线上。
八皇后问题可以推广为更一般的n皇后摆放问题：
这时棋盘的大小变为n×n，而皇后个数也变成n。
当且仅当n=1或n≥4时问题有解。
二、八皇后问题的研究与发展
八皇后问题最早是由国际西洋棋棋手马克斯·贝瑟尔于1848年提出。
之后陆续有数学家对其进行研究，其中包括高斯和康托，并且将其推广为更一般的n皇后摆放问题。
十九世纪著名的数学家高斯1850年提出：
在8X8格的国际象棋上摆放八个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法。
高斯认为有76种方案。
1854年在柏林的象棋杂志上不同的作者发表了40种不同的解，后来有人用图论的方法解出92种结果。
计算机发明后，有多种方法可以解决此问题。
八皇后问题的第一个解是在1850年由弗朗兹·诺克给出的。
诺克也是首先将问题推广到更一般的n皇后摆放问题的人之一。
1874年，S.冈德尔提出了一个通过行列式来求解的方法，这个方法后来又被J.W.L.格莱舍加以改进。
艾兹格·迪杰斯特拉在1972年用这个问题为例来说明他所谓结构性编程的能力。
八皇后问题在1990年代初期的著名电子游戏第七访客和NDS平台的著名的电子游戏雷顿教授与不可思议的小镇中都有出现。
如下图是一个八皇后成功按要求摆放的例子。
三、八皇后问题的解的分析
在一个标准的8X8的棋盘中，八皇后共有92种结果，早在19世纪就有人用图论的方法解出了92个解。
92个解当中有12个解是独立的（相互间没有对称关系的解是独立解）。
在92个解中，很多解在棋盘上有对称关系，每一个棋子都有8个对称位置，如果一个解和另外一个解所有的棋子都呈同一种对称，那么这两个解之间就是对称关系。
虽然一个解可以有8个对称位置，但是有些解经过对称操作后和没有操作前是一样的。
12个独立解如下所示：
（三）递归回溯法
一、回溯算法
1.回溯算法简介
回溯算法是深度优先搜索的一种变形。
在回溯搜索中，从问题的某一种状态（初始状态）出发，搜索从这种状态出发所能达到的所有“状态”，当一条路走到“尽头”的时候（不能再前进），再后退一步或若干步，从另一种可能“状态”出发，继续搜索，直到所有的“路径”（状态）都试探过。
这种不断“前进”、不断“回溯”寻找解的方法，就称作“回溯法”。
回溯算法也叫试探法，它是一种系统地搜索问题的解的方法。
回溯算法的基本思想是：
从一条路往前走，能进则进，不能进则退回来，换一条路再试。
回溯法是一个既带有系统性又带有跳跃性的搜索算法。
它在包含问题的所有解的解空间树中，按照深度优先的策略，从根结点出发搜索解空间树。
算法搜索至解空间树的任一结点时，总是先判断该结点是否肯定不包含问题的解。
如果肯定不包含，则跳过对以该结点为根的子树的系统搜索，逐层向其祖先结点回溯。
否则，进入该子树，继续按深度优先的策略进行搜索。
回溯法在用来求问题的所有解时，要回溯到根，且根结点的所有子树都已被搜索遍才结束。
而回溯法在用来求问题的任一解时，只要搜索到问题的一个解就可以结束。
这种以深度优先的方式系统地搜索问题的解的算法称为回溯法，它适用于解一些组合数较大的问题。
在现实中，有很多问题往往需要我们把其所有可能穷举出来，然后从中找出满足某种要求的可能或最优的情况，从而得到整个问题的解。
回溯算法就是解决这种问题的“通用算法”，有“万能算法”之称。
N皇后问题在N增大时就是这样一个解空间很大的问题，所以比较适合用这种方法求解。
这也是N皇后问题的传统解法，很经典。
2.回溯算法的一般步骤
（1）定义一个解空间，它包含问题的解。
（2）利用适于搜索的方法组织解空间。
（3）利用深度优先法搜索解空间。
（4）利用限界函数避免移动到不可能产生解的子空间。
问题的解空间通常是在搜索问题的解的过程中动态产生的，这是回溯算法的一个重要特性。
3.回溯算法的高级伪码描述
这里用一个N*N的矩阵来存储棋盘：
1）算法开始,清空棋盘，当前行设为第一行，当前列设为第一列
2）在当前行，当前列的位置上判断是否满足条件（即保证经过这一点的行,列与斜线上都没有两个皇后），若不满足，跳到第4步
3）在当前位置上满足条件的情形：
在当前位置放一个皇后，若当前行是最后一行，记录一个解；
若当前行不是最后一行，当前行设为下一行,当前列设为当前行的第一个待测位置；
若当前行是最后一行，当前列不是最后一列，当前列设为下一列；
若当前行是最后一行，当前列是最后一列，回溯，即清空当前行及以下各行的棋盘，然后，当前行设为上一行，当前列设为当前行的下一个待测位置；
以上返回到第2步
4）在当前位置上不满足条件的情形：
若当前列不是最后一列，当前列设为下一列，返回到第2步;
若当前列是最后一列了，回溯，即，若当前行已经是第一行了，算法退出，否则，清空当前行及以下各行的棋盘，然后，当前行设为上一行，当前列设为当前行的下一个待测位置，返回到第2步;
算法的基本原理是上面这个样子，但不同的是用的数据结构不同，检查某个位置是否满足条件的方法也不同。
为了提高效率，有各种优化策略，如多线程，多分配内存表示棋盘等。
二、递归算法
1.递归算法简介
递归算法是把问题转化为规模缩小了的同类问题的子问题。
然后递归调用函数（或过程）来表示问题的解。
递归算法是一种直接或者间接地调用自身的算法。
在计算机编写程序中，递归算法对解决一大类问题是十分有效的，它往往使算法的描述简洁而且易于理解。
2.递归算法解决问题的特点：
（1）递归就是在过程或函数里调用自身。
（2）在使用递归策略时，必须有一个明确的递归结束条件，称为递归出口。
（3）递归算法解题通常显得很简洁，但递归算法解题的运行效率较低。
所以一般不提倡用递归算法设计程序。
（4）在递归调用的过程当中系统为每一层的返回点、局部量等开辟了栈来存储。
递归次数过多容易造成栈溢出等。
所以一般不提倡用递归算法设计程序。
3.递归算法的要求
递归算法所体现的“重复”一般有三个要求：
（1）每次调用在规模上都有所缩小（通常是减半）；
（2）相邻两次重复之间有紧密的联系，前一次要为后一次做准备（通常前一次的输出就作为后一次的输入）；
（3）在问题的规模极小时必须用直接给出解答而不再进行递归调用，因而每次递归调用都是有条件的（以规模未达到直接解答的大小为条件），无条件递归调用将会成为死循环而不能正常结束。
八皇后递归算法流程图如下：
三、实现递归回溯的主程序
voidCEightQueenDlg:
:
Process（intm_col）
{
for（intm_row=0;m_row<8;m_row++）
{
if（row[m_row]==0&&diag1[m_col-m_row+7]==0&&diag2[m_col+m_row]==0）
//如果皇后所在的行、主从对角线均未被占领；
//对角线上的格对应得下标，要么和为常数，要么差为常数（主）
{
GridMap[m_row][m_col]=1;//将其占领格子置1
row[m_row]=1;//将其占领行置1
diag1[m_col-m_row+7]=1;//将其占领主从对角线置1
diag2[m_col+m_row]=1;
if（m_col<7）
Process（m_col+1）;
else
//如果大于或者等于7，则说明排列完毕一次。
得到一个解
{
m_count++;//得到一个解计数一次。
最后得到解的个数
for（inti=0;i<8;i++）
{
for（intj=0;j<8;j++）
{
explain[m_count-1][i][j]=GridMap[i][j];
//把每个解存入一个三维数组，记录下一个解。
}
}
}
row[m_row]=0;
//将先前的放置棋子位置重新置0，以便继续求解。
diag1[m_col-m_row+7]=0;
diag2[m_col+m_row]=0;
GridMap[m_row][m_col]=0;
}
}
m_explain.Format（"%d",m_count）;
GetDlgItem（IDC_ANSWERS）->SetWindowText（m_explain）;
}
四、采用递归回溯算法的编程步骤
1.首先打开MicrosoftVisualC++，建立一个MFCAppWizard（exe）的应用程序，名字为Ba1。
然后选择基于对话框的应用程序（Dialogbased），点击完成。
2.在对话框上添加所需要的控件，如下图所示，并修改ID。
如下图所示：
输出显示的解的个数和单个解对应的静态文本框的ID分别为IDC_ANSWERS和IDC_SINGLE，并且右键点击ClassWizard，选择MemberVariables选项卡，为它们分别添加CString的成员变量m_explain和m_explain1，为后面程序关联结果做准备。
同时可以按自己喜好修改控件的字体，此处我选择的是华文行楷。
3.因为受孙鑫VC++的影响，下面我决定使用画刷为八皇后绘制棋盘。
首先添加绘制棋盘所需要的头文件。
CBrushm_redbrush,m_greybrush;然后在OnPaint函数else后面添加下面这段代码。
（同时注释CDialog:
:
OnPaint（）;）。
CPaintDCdc（this）;//devicecontextforpainting
//TODO:
Addyourmessagehandlercodehere
CRectrect（0,0,400,400）;//（x,y,Width,Height）;
CPenpen2（PS_SOLID,1,RGB（10,0,10））;
dc.SelectObject（&pen2）;
for（inti=0;i<9;i++）
{
dc.MoveTo（rect.left,rect.top+rect.Height（）*（i）/8）;//画出横线
dc.LineTo（rect.right,rect.top+rect.Height（）*（i）/8）;
}
for（i=0;i<9;i++）
{//画出竖线
dc.MoveTo（rect.left+rect.Width（）*（i）/8,rect.top）;
dc.LineTo（rect.left+rect.Width（）*（i）/8,rect.bottom）;
}
for（i=0;i<7;i=i+2）//用灰色的画刷画出灰色的方块
{
for（intj=1;j<8;j=j+2）
{
CRectrect（j*50,i*50,j*50+50,i*50+50）;
dc.FillRect（&rect,&m_greybrush）;
}
}
for（i=1;i<8;i=i+2）
{//用灰色的画刷画出灰色的方块
for（intj=0;j<7;j=j+2）
{
CRectrect（j*50,i*50,j*50+50,i*50+50）;
dc.FillRect（&rect,&m_greybrush）;
}
}
此时已经画出了8X8的基本框架棋盘，如下图
但是为了美观，我决定将图中纯白色的方框初始化为灰色的方框，是效果更加美观。
4.此时已经需要定义二维数组还表示方格的位置，所以此处我定义一个8X8的二维数组GridMap[8][8],定义三个一维数组，row[8],diag1[15],diag2[15],同时在定义一个三维数组explain[100][8][8]来表示解空间，它们全部定义为整型int。
定义一个UINT星的m_count来计解的个数。
它们全部定义为整型int。
5.然后将定义的变量初始化
m_count=0;
在对话框的主函数中初始化各个方格，首先初始化灰色画刷，然后采用4个for循环将各个格子进行初始化，程序如下：
m_greybrush.CreateSolidBrush（RGB（150,150,150））;
for（inti=0;i<8;i++）//初始化各个格子；各个格子初始化为没有被占有
{
for（intj=0;j<8;j++）
{
GridMap[i][j]=0;
}
}
for（i=0;i<8;i++）
//初始化各个格子；//用来表示占领或未被占领的行
{
row[i]=0;
}
for（i=0;i<15;i++）
//初始化各个格子；//用来表示占领或未被占领的主对角线
{
diag1[i]=0;
}
for（i=0;i<15;i++）
//初始化各个格子；//用来表示占领或未被占领的从对角线
{
diag2[i]=0;
}
运行结果如下图所示：
这样我就将八皇后的棋盘画完了。
6.为了实现八皇后的运算，我们现在添加一个函数，此处采用递归回溯算法，记八皇后的算法过程，我们命名此函数为Process。
为对话框添加一个成员函数。
在ClassView选项卡中的CBa1Dlg上右键选择AddMemberFunction，类型为void，名字为Process（intm_col）,选择公有，点击OK。
此时Process函数便生成了。
7.为Process函数添加响应的回溯算法程序，程序如下：
voidCBa1Dlg:
:
Process（intm_col）
{
for（intm_row=0;m_row<8;m_row++）
{
if（row[m_row]==0&&diag1[m_col-m_row+7]==0&&diag2[m_col+m_row]==0）//如果皇后所在的行、主从对角线均未被占领；
//对角线上的格对应得下标，要么和为常数，要么差为常数（主）
{
GridMap[m_row][m_col]=1;//将其占领格子置1
row[m_row]=1;//将其占领行置1
diag1[m_col-m_row+7]=1;//将其占领主从对角线置1
diag2[m_col+m_row]=1;
if（m_col<7）
Process（m_col+1）;
else//如果大于或者等于7，则说明排列完毕一次。
得到一个解
{
m_count++;//得到一个解计数一次。
最后得到解的个数
for（inti=0;i<8;i++）
{
for（intj=0;j<8;j++）
{
explain[m_count-1][i][j]=GridMap[i][j];
//把每个解存入一个三维数组，记录下一个解。
}
}
}
row[m_row]=0;//将先前的放置棋子位置重新置0，以便继续求解。
diag1[m_col-m_row+7]=0;
diag2[m_col+m_row]=0;
GridMap[m_row][m_col]=0;
}
}
m_explain.Format（"%d",m_count）;
GetDlgItem（IDC_ANWSERS）->SetWindowText（m_explain）;
}
此时，已经完成了八皇后的算法程序。
8.然后我们需要为棋盘上面的皇后做一个皇后的皇冠，因为我们的棋盘是50X50的，所以我截取了一个50X50的位图，如图所示：
，然后将其复制到VC程序中的res文件夹中，并点击Insert，选择Resource，选择Bitmap，点击Import，导入成功。
此时，会有一个警告，直接选择确定即可。
9.下面我们需要关联按钮的消息响应，即为“运行”和“结果”分别添加消息响应，即选择Resource选项卡中的对话框，双击“运行”和“结果”，然后自动转到她们的消息响应函数中。
然后在“运行”的消息响应函数中添加函数Process（0）即可，因为此处只需要计算出八皇后解的个数。
10.按钮“结果”实现的功能是一次循环显示92个解。
所以需要再添加一个成员函数Draw（）。
在ClassView选项卡中的CBa1Dlg上右键选择AddMemberFunction，类型为void，名字为Draw（intx,inty）,选择公有，点击OK。
然后就生成了成员函数Draw。
在里面添加如下代码：
CClientDCdc（this）;
CDCdcCompatible;
dcCompatible.CreateCompatibleDC（&dc）;
//创建一个与设备上下文兼容的DC，用以缓冲，来消除传统重绘图形时候的窗口抖动
CBitmapbitmap;
bitmap.LoadBitmap（IDB_BITMAP1）;//加载位图
CRectrect（x,y,50+x,50+y）;//创建方块区域
dcCompatible.SelectObject（&bitmap）;
dc.SetBkColor（RGB（150,150,150））;
dc.BitBlt（x+1,y+1,rect.Width（）,rect.Height（）,&dcCompatible,0,0,SRCCOPY）;
dcCompatible.DeleteDC（）;
即实现位图的加载，并添加到相应的方块区域中。
11.让按钮“结果”实现循环显示所有解。
首先定义一个整型int的num，来表示第num个解。
然后在主函数中初始化num，即num=0;然后在“结果”按钮的函数中添加如下代码：
voidCBa1Dlg:
:
OnButton2（）
{
//TODO:
Addyourcontrolnotificationhandlercodehere
Invalidate（）;//重绘窗口
this->OnPaint（）;
for（inti=0;i<8;i++）
{
for（intj=0;j<8;j++）//显示第NUM个解
{
if（explain[num][i][j]==1）
Draw（i*50,j*50）;
}
}
m_explain1.Format（"%d",++num）;
GetDlgItem（IDC_SINGLE）->SetWindowText（m_explain1）;
if（num==92）//循环显示解
{
num=0;
}
}
运行结果如图所示：
12.为使结果突出显示，将结果显示的数字改为红色。
在对话框上面添加一个Windows消息处理响应。
即右键点击AddWindowsMessageHandler..，选择WM_CTLCOLOR，增加并编辑。
然后在其中添加如下代码：
HBRUSHCBa1Dlg:
:
OnCtlColor（CDC*pDC,CWnd*pWnd,UINTnCtlColor）
{
HBRUSHhbr=CDialog:
:
OnCtlColor（pDC,pWnd,nCtlColor）;
//TODO:
ChangeanyattributesoftheDChere
if（pWnd->GetDlgCtrlID（）==IDC_ANWSERS||
pWnd->GetDlgCtrlID（）==IDC_SINGLE）
{
pDC->SetTextColor（RGB（255,0,0））;
pDC->SetBkMode（TRANSPARENT）;
}
//TODO:
Returnadifferentbrushifthedefaultisnotdesired
returnhbr;
}
运行程序，结果如图所示：
每点击一次“结果”按钮，就会显示出一种八皇后的摆放方式，点击到93次时，循环显示92个解。
因为是采用递归回溯的方式，所以结果没有重复，是从最开始的方格开始计算，直到得到所有可能的解。
以上是在MicrosoftVisualC++编译环境下，基于MFC并使用递归回溯的方法实现八皇后成功摆放的编程步骤，结果已经成功运行。
运算的速度非常快，基于现在电脑的配置，如果没有加入定时器元素，无法看出哪种算法更快速有效，但是可以知道求出所有结果仅在不到1秒之内。
但是递归回溯的方法是解决八皇后问题，甚至N皇后问题最有效且最经典的算法，也是最容易理解的算法。
所以本报告详细叙述了采用递归回溯的方法实现八皇后成功摆放的程序编写步骤。
五、递归回溯算法总结
递归回溯算法是解决八皇后问题的典型算法。
回溯法可以在极短的时间内找到所有解。
并能够存储所有的解，并循环显示，这是其它算法不能实现的。
在此方法中，程序占用的临时空间并不是很多，它并没有存储每个节点的状态，而只是存储了找到的解于GridMap[][]数组中，而row[],diag1[],diag2[]数组只是用于临时存放当前节点状态，explain[][][]数组用于存放所有解。
这些存储的数组占用的内存都很小，可以说该算法的空间复杂
升级会员 