人工智能VC++八皇后报告.doc

目录（一）八皇后算法与编程声明2（二）八皇后问题的描述分析3一、八皇后问题描述3二、八皇后问题的研究与发展3三、八皇后问题的解的分析4（三）递归回溯法6一、回溯算法6二、递归算法7三、实现递归回溯的主程序8四、采用递归回溯算法的编程步骤9五、递归回溯算法总结16（四）爬山法17一、爬山法17二、爬山法解决八皇后问题17三、采用爬山法算法的编程步骤20四、运行时间与步长分析26五、爬山法算法总结26（五）最小冲突的局部搜索法27一、最小冲突的局部搜索法简介27二、最小冲突的局部搜索法求解八皇后问题27三、采用最小冲突的局部搜索算法的编程步骤28四、运行时间与步长分析29五、最小冲突的局部搜索算法总结29（六）八皇后其余算法实现30一、模拟退火算法30二、遗传算法31（七）总 结33（一）八皇后算法与编程声明实现八皇后问题的人工智能算法有很多种，编程实现的方式也有很多种。常用的方法有回溯法、CSP(约束满足问题)最小冲突的局部搜索法、爬山法、遗传算法等。其中回溯法是解决八皇后问题最经典、最有效，也是最容易理解的算法。本人在本次报告使用了以下三种算法编程解决八皇后的问题：递归回溯法、爬山法和最小冲突的局部搜索算法，还有模拟退火算法，遗传算法等。在本报告的后面将分为三个部分分别介绍递归回溯法、爬山法和最小冲突的局部搜索算法的算法分析、算法意义及三种算法的优缺点和适用范围。并介绍使用Microsoft Visual C+软件编程的具体步骤和算法的主函数分析及实现的功能。本次实验编程环境为Microsoft Visual C+软件，建立在基于MFC平台上的运行程序。界面生动美观，实现效果清晰可见。本实验的八皇后算法、程序的界面和祝算法主函数主要参考以下资料。1. 人工智能一种现代方法（第二版）2. VC+深入详解（修订版）3. 中国知网关于八皇后问题分析及本报告所使用的三种算法有关的论文12篇，在此不一一列出赘述。4. 其余资料均来源于互联网，包括百度百科、百度知道、程序员开发网等。下面分别介绍递归回溯法、爬山法和最小冲突的局部搜索算法及编程实现，并简要介绍模拟退火算法和遗传算法。（二）八皇后问题的描述分析一、八皇后问题描述八皇后问题是一个古老而著名的以国际象棋为背景的问题：如何能够在 88 的国际象棋棋盘上放置八个皇后，使得任何一个皇后都无法直接吃掉其他的皇后？为了达到此目的，任两个皇后都不能处于同一条横行、纵行或斜线上。八皇后问题可以推广为更一般的n皇后摆放问题：这时棋盘的大小变为nn，而皇后个数也变成n。当且仅当n=1或n4时问题有解。二、八皇后问题的研究与发展八皇后问题最早是由国际西洋棋棋手马克斯贝瑟尔于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）在问题的规模极小时必须用直接给出解答而不再进行递归调用，因而每次递归调用都是有条件的(以规模未达到直接解答的大小为条件)，无条件递归调用将会成为死循环而不能正常结束。八皇后递归算法流程图如下：三、实现递归回溯的主程序void CEightQueenDlg:Process(int m_col)for(int m_row=0;m_row8;m_row+)if(rowm_row=0 & diag1m_col-m_row+7=0 & diag2m_col+m_row=0) /如果皇后所在的行、主从对角线均未被占领；/对角线上的格对应得下标，要么和为常数，要么差为常数（主）GridMapm_rowm_col=1; /将其占领格子置1rowm_row=1; /将其占领行置1diag1m_col-m_row+7=1; /将其占领主从对角线置1diag2m_col+m_row=1;if(m_col7)Process(m_col+1); else /如果大于或者等于7，则说明排列完毕一次。得到一个解m_count+; /得到一个解计数一次。最后得到解的个数for (int i=0;i8;i+)for (int j=0;jSetWindowText(m_explain);四、采用递归回溯算法的编程步骤1. 首先打开Microsoft Visual C+，建立一个MFC AppWizard(exe)的应用程序，名字为Ba1。然后选择基于对话框的应用程序（Dialog based），点击完成。2. 在对话框上添加所需要的控件，如下图所示，并修改ID。如下图所示：输出显示的解的个数和单个解对应的静态文本框的ID分别为IDC_ANSWERS和IDC_SINGLE，并且右键点击ClassWizard，选择Member Variables选项卡，为它们分别添加CString的成员变量m_explain和m_explain1，为后面程序关联结果做准备。同时可以按自己喜好修改控件的字体，此处我选择的是华文行楷。3. 因为受孙鑫VC+的影响，下面我决定使用画刷为八皇后绘制棋盘。首先添加绘制棋盘所需要的头文件。CBrush m_redbrush,m_greybrush;然后在OnPaint函数else后面添加下面这段代码。（同时注释CDialog:OnPaint();）。CPaintDC dc(this); / device context for painting/ TODO: Add your message handler code hereCRect rect(0,0,400,400);/(x,y,Width,Height);CPen pen2(PS_SOLID,1,RGB(10,0,10);dc.SelectObject(&pen2);for (int i=0;i9;i+)dc.MoveTo(rect.left,rect.top+rect.Height()*(i)/8); /画出横线dc.LineTo(rect.right,rect.top+rect.Height()*(i)/8);for (i=0;i9;i+) /画出竖线dc.MoveTo(rect.left+rect.Width()*(i)/8,rect.top);dc.LineTo(rect.left+rect.Width()*(i)/8,rect.bottom);for (i=0;i7;i=i+2) /用灰色的画刷画出灰色的方块for (int j=1;j8;j=j+2)CRect rect(j*50,i*50,j*50+50,i*50+50);dc.FillRect(&rect,&m_greybrush);for (i=1;i8;i=i+2) /用灰色的画刷画出灰色的方块for (int j=0;j7;j=j+2)CRect rect(j*50,i*50,j*50+50,i*50+50);dc.FillRect(&rect,&m_greybrush);此时已经画出了8X8的基本框架棋盘，如下图但是为了美观，我决定将图中纯白色的方框初始化为灰色的方框，是效果更加美观。 4. 此时已经需要定义二维数组还表示方格的位置，所以此处我定义一个8X8的二维数组GridMap88,定义三个一维数组，row8,diag115,diag215,同时在定义一个三维数组explain10088来表示解空间，它们全部定义为整型int。定义一个UINT星的m_count来计解的个数。它们全部定义为整型int。5. 然后将定义的变量初始化m_count = 0;在对话框的主函数中初始化各个方格，首先初始化灰色画刷，然后采用4个for循环将各个格子进行初始化，程序如下：m_greybrush.CreateSolidBrush(RGB(150,150,150);for (int i=0;i8;i+) /初始化各个格子；各个格子初始化为没有被占有for (int j=0;j8;j+)GridMapij=0;for (i=0;i8;i+) /初始化各个格子；/用来表示占领或未被占领的行rowi=0;for (i=0;i15;i+) /初始化各个格子；/用来表示占领或未被占领的主对角线diag1i=0;for (i=0;i15;i+) /初始化各个格子； /用来表示占领或未被占领的从对角线diag2i=0; 运行结果如下图所示：这样我就将八皇后的棋盘画完了。6. 为了实现八皇后的运算，我们现在添加一个函数，此处采用递归回溯算法，记八皇后的算法过程，我们命名此函数为Process。为对话框添加一个成员函数。在ClassView选项卡中的CBa1Dlg上右键选择Add Member Function，类型为void，名字为Process（int m_col）,选择公有，点击OK。此时Process函数便生成了。7. 为Process函数添加响应的回溯算法程序，程序如下：void CBa1Dlg:Process(int m_col)for(int m_row=0;m_row8;m_row+)if(rowm_row=0 & diag1m_col-m_row+7=0 & diag2m_col+m_row=0) /如果皇后所在的行、主从对角线均未被占领；/对角线上的格对应得下标，要么和为常数，要么差为常数（主）GridMapm_rowm_col=1; /将其占领格子置1rowm_row=1; /将其占领行置1diag1m_col-m_row+7=1; /将其占领主从对角线置1diag2m_col+m_row=1;if(m_col7)Process(m_col+1); else /如果大于或者等于7，则说明排列完毕一次。得到一个解m_count+; /得到一个解计数一次。最后得到解的个数for (int i=0;i8;i+)for (int j=0;jSetWindowText(m_explain);此时，已经完成了八皇后的算法程序。8. 然后我们需要为棋盘上面的皇后做一个皇后的皇冠，因为我们的棋盘是50X50的，所以我截取了一个50X50的位图，如图所示：，然后将其复制到VC程序中的res文件夹中，并点击Insert，选择Resource，选择Bitmap，点击Import，导入成功。此时，会有一个警告，直接选择确定即可。9. 下面我们需要关联按钮的消息响应，即为“运行”和“结果”分别添加消息响应，即选择Resource选项卡中的对话框，双击“运行”和“结果”，然后自动转到她们的消息响应函数中。然后在“运行”的消息响应函数中添加函数Process（0）即可，因为此处只需要计算出八皇后解的个数。10. 按钮“结果”实现的功能是一次循环显示92个解。所以需要再添加一个成员函数Draw()。在ClassView选项卡中的CBa1Dlg上右键选择Add Member Function，类型为void，名字为Draw(int x, int y),选择公有，点击OK。然后就生成了成员函数Draw。在里面添加如下代码：CClientDC dc(this);CDC dcCompatible;dcCompatible.CreateCompatibleDC(&dc); /创建一个与设备上下文兼容的DC，用以缓冲，来消除传统重绘图形时候的窗口抖动CBitmap bitmap;bitmap.LoadBitmap(IDB_BITMAP1); /加载位图CRect rect(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;然后在“结果”按钮的函数中添加如下代码：void CBa1Dlg:OnButton2() / TODO: Add your control notification handler code hereInvalidate(); /重绘窗口this-OnPaint();for(int i=0;i8;i+)for(int j=0;jSetWindowText(m_explain1);if (num=92) /循环显示解num=0;运行结果如图所示：12. 为使结果突出显示，将结果显示的数字改为红色。在对话框上面添加一个Windows消息处理响应。即右键点击Add Windows Message Handler.，选择WM_CTLCOLOR，增加并编辑。然后在其中添加如下代码：HBRUSH CBa1Dlg:OnCtlColor(CDC* pDC, CWnd* pWnd, UINT nCtlColor) HBRUSH hbr = CDialog:OnCtlColor(pDC, pWnd, nCtlColor);/ TODO: Change any attributes of the DC hereif (pWnd-GetDlgCtrlID()=IDC_ANWSERS | pWnd-GetDlgCtrlID()=IDC_SINGLE)pDC-SetTextColor(RGB(255,0,0);pDC-SetBkMode(TRANSPARENT);/ TODO: Return a different brush if the default is not desiredreturn hbr;运行程序，结果如图所示：每点击一次“结果”按钮，就会显示出一种八皇后的摆放方式，点击到93次时，循环显示92个解。因为是采用递归回溯的方式，所以结果没有重复，是从最开始的方格开始计算，直到得到所有可能的解。以上是在Microsoft Visual C+编译环境下，基于MFC并使用递归回溯的方法实现八皇后成功摆放的编程步骤，结果已经成功运行。运算的速度非常快，基于现在电脑的配置，如果没有加入定时器元素，无法看出哪种算法更快速有效，但是可以知道求出所有结果仅在不到1秒之内。但是递归回溯的方法是解决八皇后问题，甚至N皇后问题最有效且最经典的算法，也是最容易理解的算法。所以本报告详细叙述了采用递归回溯的方法实现八皇后成功摆放的程序编写步骤。五、递归回溯算法总结递归回溯算法是解决八皇后问题的典型算法。回溯法可以在极短的时间内找到所有解。并能够存储所有的解，并循环显示，这是其它算法不能实现的。在此方法中，程序占用的临时空间并不是很多，它并没有存储每个节点的状态，而只是存储了找到的解于GridMap数组中，而row,diag1,diag2数组只是用于临时存放当前节点状态，explain数组用于存放所有解。这些存储的数组占用的内存都很小，可以说该算法的空间复杂度并不高。从运行时间上来看，这种算法能在极短的时间内找到所有解，因此该方法的时间复杂度并不是很高。回溯法在求取单解或者是最优解的问题上显得有些笨、浪费时间与步骤；但其在求取所有解的时候，往往该方法是我们的最佳选择方法，所以，对于不同的问题，最简单、最通俗的方法不一定是最笨的，有时往往是最有效的。所以对于我们想要实现的具体问题，我们可以依据不同算法的思想和功能选择合适的算法。（四） 爬山法一、爬山法爬山法 (Hill- climbing)搜索的算法，它是一个向值增加的方向持续移动的简单循环过程也就是，登高。是一种最简单的启发式搜索算法, 它将最陡上升方向作为搜索方向, 因此能够以最快的速度爬到山顶。它将会到达一个“峰顶”时终止，相邻状态中没有比它更高的值。这种算法不维护搜索树，因此当前节点的数据结构只需记录当前的状态和它的目标函数值。爬山法不会前瞻与当前状态不直接相邻的那些状态的值，就像健忘的人攀登珠穆朗玛峰一样。其搜索过程概况是，扩展当前节点，并估价它的子节点；将最优子节点作为下一步扩展节点，以此类推，直到爬到“山顶”为止。尽管爬山法搜索速度快，但容易陷入局部最优。解决方法通常有两种，一种是根据某种启发式信息，跳出局部最优点，继续爬山过程；另一种是增多爬山者的个数，确保至少有一个可以爬到全局最优点。显然，爬山者越多且起始点越分散，到达最高峰的可能性就越大。爬山法原理：设爬山者最初位于P点，目标是爬上峰顶。为此，爬山者可有4种走法，即向东、向南、向西、向北。爬山法要求在每走一步之前，先计算分别向4个方向走一步后到达的新位置与原位置高度之差，即启发信息；然后根据这一信息决定向哪个方向走。一般选高度差最大的方向作为即将走步的方向。每走一步都要有经计算得到的启发信息的引导。当到达某点时，若4个方向的高度差计算结果都导致高度下降，则认为该点就是峰顶，搜索结束。由于爬山法每一步都是向梯度最陡的方向前进，而不是盲目攀登，因而可找到一条能很快到达峰顶的路径。爬山法搜索策略归纳如下：步骤1：等间隔设置爬山者起始点，间隔距离必须小于主峰宽度，保证至少有一个爬山者位于主峰面上；步骤2：将所有爬山者按照起始位置的高低（相关度大小）排序，从高至低依次爬山；步骤3：设置终止参数，当局部高点满足条件（比如相关度大于0.8），结束搜索，否则启动下一个爬山者。二、爬山法解决八皇后问题局部搜索算法通常使用完全状态形式化，即每个状态都在棋盘上放八个皇后，每列一个。后继函数返回的是移动一个皇后到和它同一列的另一个方格中的所有可能状态（因此每个状态有8X7=56个后继）。启发式耗散函数h是可以彼此攻击的皇后对的数量，不管中间是否有障碍。该函数的全局最小值是0，仅在找到完美解时才能得到这个值。如果这样的后继多于一个的话，爬山法算法通常在最佳后继的集合中随机选择一个进行扩展。此处选择的启发耗散函数h为：在棋盘64个位置中，某一放置皇后位置与其他行的皇后的冲突的个数的最大的那个位置的冲突个数。可知，目标状态同样为h=0。当找到这个h最大值时，我们也找到了这个位置，对该位置所在行其他位置进行评估，找到h最小的位置，于是把该皇后放到那个h最小的位置上去，如果发现有多个最小位置，我们随机选择一个。然后开始下次循环，直至找到h=0时为最优解。在这里，我选择的初始状态为每行随机选个位置放置皇后，采用随机重新开始爬山法进行搜索，以此来避免死循环的发生。爬山法算法我们将皇后摆法的判断和算法的实现过程分开编程，用2个函数来实现。首先是判断皇后的摆放函数check()：int CBa2Dlg:check(int idx)int index = idx;int row = index/8;int col = index%8;int j;int h=0;/检查列int i;for(i=col; i=0&j=0; i-,j-)if(qii*8+j=1)h+;for(i=row,j=col; i8&j=0&j=0&i8; i+,j-)if(qii*8+j=1)h+;return h;爬山法算法主程序如下：void CBa2Dlg:process()int i;doloop:for( i=0;i64;i+) qii=as0i;/为求h做准备int h64;/用来存放每个点的h值int f=0; max=0;for(i=0;i64;i+) int row; row=i/8;/当前所在行 int j; for( j=0;j8;j+) qirow*8+j=0;/该行清零 hi=check(i);/存放该位置的h值for(j=0;j8;j+) qirow*8+j=as0row*8+j;/恢复该行for(i=0;imax&as0i=1)max=hi,count=i;/找出h的最大值max if(max=0) show(1); int row;row=count/8;/h最大位置所在行/寻找这一行h最小的位置 min=6;for(i=0;i8;i+)if(hrow*8+i=1) int r=rand()%2; if(r=1)min=hrow*8+i,xiao=row*8+i,f=1; if(step50)/步长超过50判为无效从新布局OnCreate();totalstep+=step;step=0;if(f=1)for(i=0;i0);三、采用爬山法算法的编程步骤在递归回溯法中已经非常详细的叙述了编程的步骤，所以这里不再意义赘述，只说明简单的编程步骤。按模块化的方式分析，步骤如下：1. 首先在对话框上面画出所需要的控件，并定义所需要的空间的成员变量。2. OnPaint()函数后面添加代码，代码和回溯法相同，画出棋盘。3. 初始化所有位置及变量，并定义画刷。即在OnInitDialog()后面添加如下代码：count = 0;asnum = 0;for(int i=0; i64; i+)qii = 0;m_greybrush.CreateSolidBrush(RGB(150,150,150);4. 基本准备工作做完后，添加需要的函数。首先添加皇后位置的判断函数，check()，代码如下：int CBa2Dlg:check(int idx)int index = idx;int row = index/8;int col = index%8;int j;int h=0;/检查行/*for(int i=row*8; irow*8+8; i+)if(qii=1)h+;*/检查列int i;for(i=col; i=0&j=0; i-,j-)if(qii*8+j=1)h+;for(i=row,j=col; i8&j=0&j=0&i8; i+,j-)if(qii*8+j=1)h+;return h;5. 然后添加爬山法算法主程序，代码如下：void CBa2Dlg:process()int i;doloop:for( i=0;i64;i+) qii=as0i;/为求h做准备int h64;/用来存放每个点的h值int f=0; max=0;for(i=0;i64;i+) int row; row=i/8;/当前所在行 int j; for( j=0;j8;j+) qirow*8+j=0;/该行清零 hi=check(i);/存放该位置的h值for(j=0;j8;j+) qirow*8+j=as0row*8+j;/恢复该行for(i=0;imax&as0i=1)max=hi,count=i;/找出h的最大值max if(max=0) show(1); int row;row=count/8;/h最大位置所在行/寻找这一行h最小的位置 min=6;for(i=0;i8;i+)if(hrow*8+i=1) int r=rand()%2; if(r=1)min=hrow*8+i,xiao=row*8+i,f=1; if(step50)/步长超过50判为无效从新布局OnCreate();totalstep+=step;step=0;if(f=1)for(i=0;i0);6. 添加一个Draw()函数，实现皇后的摆放。代码如下：void CBa2Dlg:Draw(int x, int y)x *= 50;y *= 50;CClientDC dc(this);CDC dcCompatible;dcCompatible.CreateCompatibleDC(&dc); /创建一个与设备上下文兼容的DC，用以缓冲，来消除传统重绘图形时候的窗口抖动CBitmap bitmap;bitmap.LoadBitmap(IDB_BITMAP1); /加载位图CRect rect(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();7. 添加一个show()函数，功能是按算法结果摆出皇后位置。代码如下：void CBa2Dlg:show(int asnum)inti(0);cls();for ( i = 0; i 64; i+)if ( asasnum-1i=1)Draw( i/8, i%8);8. 添加一个cls()函数，用来清空棋盘，实现窗口重绘。代码如下：void CBa2Dlg:cls()Invalidate();OnPaint();9. 为“随机生成”按钮添加响应函数，代码如下：void CBa2Dlg:OnCreate() / TODO: Add your control notification handler code hereint i;for( i=0;i64;i+) as0i=0; for(i=0;i8;i+) int m; m=rand()%8; as0m+i*8=1;show(1);10. 为“排列皇后”按钮添加响应函数，代码如下：void CBa2Dlg:OnArrange() / TODO: Add your control notification handler code hereint start=clock(); process();int end=clock(); m_failnum=totalstep/50; UpdateData(FALSE); m_time=end-start; UpdateData(FALSE); m_step=totalstep; UpdateData(FALSE);step=0;totalstep=0;11. 为“清除棋盘”按钮添加响应函数，代码如下：void CBa2Dlg:OnClear() / TODO: Add your control notification handler code herefor(int i=0; i64; i+)qii = 0;cls();m_step=0; UpdateData(FALSE);m_time=0; UpdateData(FALSE);m_failnum=0; UpdateData(FALSE); asnum=0;12. 点击编辑并运行，结果如下图所示：点击“随机生成”，点击“排列皇后”，结果运行良好，可以快速搜索出结果。四、运行时间与步长分析此处将爬山法运行10次并记录时间、失败次数和步长数据。结果如下：平均时间（ms）313216471616315784731.9失败次数71381564111311811.4搜索步长357663408765306204361511581918561.4五、爬山法算法总结在爬山法中，我们没有求出全体解，因为爬山法属于随机性算法，按照给出的情况选择最合适的解法，当然在爬山的过程中很可能选择山顶作为结果。在计算过程中，只需记住当前的状态，把