当前位置:文档之家› #人工智能课程设计报告-五子棋

#人工智能课程设计报告-五子棋

#人工智能课程设计报告-五子棋
#人工智能课程设计报告-五子棋

目录

1.五子棋简介- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - 3

2.需求分析- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - 3

3.主要名词说明- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - 3

4.主要算法- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - 4

5.程序运行界面展示- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - 7

6.不足说明- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - 8

7.心得体会- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - 8

1、五子棋简介

选择五子棋游戏作为本设计的课题,是因为该游戏的规则简单,所涉及的方向比较少。这样才能将问题的重点放在人工智能解决上,而非规则的解决,有更多的精力放在高效算法的优化。希望能通过本次系统的设计,整合所学的知识,实现从理论到实践上的升华。

五子棋是起源于中国古代的传统黑白棋种之一。现代五子棋日文称之为“连珠”,英译为“Renju”,英文称之为“Gobang”或“FIR”(Five in a Row的缩写),亦有“连五子”、“五子连”、“串珠”、“五目”、“五目碰”、“五格”等多种称谓。它不仅能增强思维能力,提高智力,而且富含哲理,有助于修身养性。五子棋既有现代休闲的明显特征“短、平、快”,又有古典哲学的高深学问“阴阳易理”;它既有简单易学的特性,为人民群众所喜闻乐见,又有深奥的技巧和高水平的国际性比赛;它的棋文化源渊流长,具有东方的神秘和西方的直观;既有“场”的概念,亦有“点”的连接。它是中西文化的交流点,是古今哲理的结晶。

五子棋的规则如下:

棋盘:采用15×15的棋盘。

下法:两人分别执黑白两色棋子,轮流在棋盘上选择一个无子的交叉点落子。

输赢判断:黑、白双方有一方的5个棋子在横、竖或斜方向上连接成一线即为该方赢。

2、需求分析

作为五子棋的设计需要考虑到的最基本的需求莫过于人机对战功能的实现,当然还有下棋过程中的悔棋功能以及判断游戏的胜负等方面的要求。当然最好是要考虑到界面的友好性,作为一个娱乐软件,还应该考虑到玩家在游戏时的舒适性,比如可以考虑加入一些背景音乐和音效。

3、主要名词说明

3.1 棋盘数据——m_data

这是一个15*15的二位数组,用来保存当前棋盘的落子数据。其中对于每个成员来说,0表示落黑子,1表示落白子,-1表示无子。

3.2 清空棋盘——Clear

在每一局游戏开始的时候都需要调用这个函数将棋盘清空,也就是棋盘的初始化工作。这个函数主要将m_data中每一个落子位都置为无子状态(-1)。

3.3 初始化操作——Init

对于人机对弈而言,初始化操作包括以下几个步骤:

(1)初始化所有的获胜组合。

(2)如果是计算机先走,则占据天元(棋盘正中央)的位置。

3.4 绘制棋子——Draw

这是很重要的一个函数,它根据参数给定的坐标和颜色绘制棋子。绘制的详细过程如下:(1)将给定的棋盘坐标换算为绘图的像素坐标。

(2)根据坐标绘制棋子位图。

(3)如果先前曾下过棋子,则利用R2_NOTXORPEN将上一个绘制棋子上的最后落子指示矩形擦除。(4)在刚绘制完成的棋子四周绘制最后落子指示矩形。

3.5 左键消息——OnLButtonUp

作为棋盘唯一响应的左键消息,也需要做不少的工作:

(1)如果点击时的鼠标坐标在合法坐标(0, 0)~(14, 14)之外,亦禁止落子。

(2)如果走的步数大于1步,则允许悔棋。

3.6 绘制棋盘——OnPaint

每当WM_PAINT消息触发时,都需要对棋盘进行重绘。OnPaint作为响应绘制消息的消息处理函数使用了双缓冲技术,减少了多次绘图可能导致的图像闪烁问题。这个函数主要完成了以下工作:

(1)装载棋盘位图并进行绘制。

(2)根据棋盘数据绘制棋子。

(3)绘制最后落子指示矩形。

3.7 胜负的判断——Win

这是游戏中一个极其重要的算法,用来判断当前棋盘的形势是哪一方获胜。其详细内容请参见“主要算法”一节。

3.8 悔棋操作——Back

因为是人机对弈,所以计算机是完全允许玩家悔棋的,但是出于对程序负荷的考虑,只允许玩家悔当前的两步棋(计算机一步,玩家一步)。

4、主要算法

4.1 判断胜负

五子棋的胜负,在于判断棋盘上是否有一个点,从这个点开始的横竖斜四个方向是否有连续的五个同色棋子出现,如图1:

图1

这个算法就是Win函数。从设计的思想上,需要它接受一个棋子的参数,然后返回一个值,这个值来指示是否胜利,代码如下:

int x, y;

for ( y = 0; y < 15; y++ ) // 判断横向

{for ( x = 0; x < 11; x++ )

{if ( color == m_data[x][y] &&color == m_data[x + 1][y] &&color == m_data[x + 2][y] &&color == m_data[x + 3][y] &&color == m_data[x + 4][y] )

{return TRUE;}}}

for ( y = 0; y < 11; y++ ) // 判断纵向

{for ( x = 0; x < 15; x++ )

{if ( color == m_data[x][y] &&color == m_data[x][y + 1] &&color == m_data[x][y + 2] &&color == m_data[x][y + 3] &&color == m_data[x][y + 4] )

{return TRUE;}}}

for ( y = 0; y < 11; y++ ) // 判断“\”方向

{for ( x = 0; x < 11; x++ )

{if ( color == m_data[x][y] &&color == m_data[x + 1][y + 1] &&color == m_data[x + 2][y + 2] &&color == m_data[x + 3][y + 3] &&color == m_data[x + 4][y + 4] )

{return TRUE;}}}

for ( y = 0; y < 11; y++ ) // 判断“/”方向

{for ( x = 4; x < 15; x++ )

{if ( color == m_data[x][y] &&color == m_data[x - 1][y + 1] &&color == m_data[x - 2][y + 2] &&color == m_data[x - 3][y + 3] &&color == m_data[x - 4][y + 4] )

{return TRUE;}}}

return FALSE; // 不满足胜利条件需要说明的一点是,由于搜索顺序是从左到右、自上而下,因此在每次循环的时候,都有一些坐标无需纳入考虑范围。例如对于横向判断而言,由于右边界所限,因而所有横坐标大于等于11的点,都构不成达到五子连的条件,所以横坐标的循环上界也就定为11,这样就提高了搜索的速度。

4.2 获胜组合

获胜组合是一个三维数组,它记录了所有获胜的情况。也就是说,参考于Win中的情况,对于每一个落子坐标,获胜的情况一共有15 * 11 * 2 + 11 * 11 * 2 = 572种,而对于每个坐标的获胜组合,应该设置一个[15][15][572]大小的三维数组。

在拥有了这些获胜组合之后,就可以参照每个坐标的572种组合给自己的局面和玩家的局面进行打分,也就是根据当前盘面中某一方所拥有的获胜组合多少进行权值的估算,给出最有利于自己的一步落子坐标。在每次游戏初始化(Init)的时候,需要将每个坐标下可能的获胜组合都置为true。

由于是双方对弈,所以游戏的双方都需要一份获胜组合,也就是:

bool m_Computer[15][15][572]; // 电脑获胜组合

bool m_Player[15][15][572]; // 玩家获胜组合

4.3 落子后处理

每当一方落子后,都需要作如下处理:

如果己方此坐标的获胜组合仍为true,且仍有可能在此获胜组合处添加棋子,则将此获胜组合添加棋子数加1;如果对方此坐标的获胜组合仍为true,则将对方此坐标的获胜组合置为false,并将对方此获胜组合添加棋子数置为-1。

以玩家落子为例,代码为:

for ( i = 0; i < 572; i++ )

{if ( m_Player[stepPut.x][stepPut.y][i] &&m_Win[0][i] != -1 ) // 修改状态变化m_Win[0][i]++;

if ( m_Computer[stepPut.x][stepPut.y][i] )

{m_Computer[stepPut.x][stepPut.y][i] = false;

m_Win[1][i] = -1;}}

4.4 查找棋盘空位

在计算机落子之前,需要查找棋盘的空位,所以需要一个SearchBlank成员函数完成此项工

作,此函数需要进行不重复的查找,也就是说,对已查找过的空位进行标记,并返回找到空位的坐标,其代码如下:

bool COneGame::SearchBlank( int &i, int &j, int nowTable[][15] )

{int x, y;

for ( x = 0; x < 15; x++ )

{for ( y = 0; y < 15; y++ )

{if ( nowTable[x][y] == -1 && nowTable[x][y] != 2 )

{i = x;

j = y;

return true;}}}

return false;}

4.5 落子打分

找到空位后,需要对这个点的落子进行打分,这个分数也就是这个坐标重要性的体现,代码如下:

int COneGame::GiveScore( const STEP& stepPut )

{int i, nScore = 0;

for ( i = 0; i < 572; i++ )

{if ( m_pTable->GetColor() == stepPut.color )

{if ( m_Player[stepPut.x][stepPut.y][i] ) // 玩家下

{switch ( m_Win[0][i] )

{case 1:

nScore -= 5;

break;

case 2:

nScore -= 50;

break;

case 3:

nScore -= 500;

break;

case 4:

nScore -= 5000;

break;

default:

break;}}}

else

{if ( m_Computer[stepPut.x][stepPut.y][i] ) // 计算机下

{switch ( m_Win[1][i] )

{case 1:

nScore += 5;

break;

case 2:

nScore += 50;

break;

case 3:

nScore += 100;

break;

case 4:

nScore += 10000;

break;

default:

break;}}}}

return nScore;

}

如代码所示,考虑到攻守两方面的需要,所以将玩家落子给的分数置为负值。

4.6 防守策略

落子的考虑不单单要从进攻考虑,还要从防守考虑。这一细节的实现其实就是让计算机从玩家棋盘布局分析战况,然后找出对玩家最有利的落子位置。整个过程如下:

for ( m = 0; m < 572; m++ )

{if ( m_Player[i][j][m] ) // 暂时更改玩家信息{temp1[n] = m;

m_Player[i][j][m] = false;

temp2[n] = m_Win[0][m];

m_Win[0][m] = -1;

n++;}}

ptempTable[i][j] = 0;

pi = i;

pj = j;

while ( SearchBlank( i, j, ptempTable ) )

{ptempTable[i][j] = 2; // 标记已被查找

step.color = m_pTable->GetColor();

step.x = i;

step.y = j;

ptemp = GiveScore( step );

if ( pscore > ptemp ) // 此时为玩家下子,运用极pscore = ptemp;} 小极大法时应选取最小值for ( m = 0; m < n; m++ )

{m_Player[pi][pj][temp1[m]] = true; // 恢复玩家信息

m_Win[0][temp1[m]] = temp2[m];}

4.7 选取最佳落子

在循环结束的时候,就可以根据攻、守两方面的打分综合地考虑落子位置了。代码如下:if ( ctemp + pscore > cscore )

{cscore = ctemp + pscore;

bestx = pi;

besty = pj;}

在这之后,重新改变一下棋盘的状态(4.3)即可。

5、程序运行界面展示

6、不足说明:

(1)由于计算机在落子时选取的是得分最高的一步落子,所以如果玩家在开局的时候不改变落子步骤,那么将会获得从头至尾相同的棋局。考虑可以在某些步骤上加入随机因素,使对弈过程更具趣味性。

(2)可能的话增加一些背景音乐功能;可以增加保存棋局,以便于调用观看。

(3)人机算法部分中的评估函数,也需要调整使得其更加的智能。算法有个缺点就是当棋盘上的棋子相当的时候,比如双方都存在活三,它会调用评估函数向前预测,算出双方的值相当。于是就不选择自己连四。可以说这是很大的败笔,不过可以写个函数进行修补。

(4)总体感觉系统可维护性很差,应该尽可能的使用常量代替具体数据。这样更利于后期的维护,避免牵一发而动全身。

7、心得体会

在刚开始编写这个程序的时候,我幼稚地认为其中最重要的是博弈算法。但是头几天编写程序的时候却发现程序越写越不容易维护,可见是我走错了方向。后来我向几位真正的高手讨教,他们告诉我:我们的先人早已为我们准备好了各种精良可用的现成算法,我们所要做的就是拿来主义;但是代码的组织(架构)才是真正的核心部分,因此我们必须在编写代码之前选择一种最为合适的方法来组织这些代码,否则我们将会失去很多的时间和金钱。

而在编程的过程中我也体会到了一点:学一门课程最重要的就是实践。通过这段时间的实践我发现自己进步了不少,也渐渐理解人工智能算法相对于其它算法的优点所在。虽然这个五子棋软件还存在着一些不足,但自己毕竟从中学到了不少的东西,得到了不少的东西。

在此对赵曼老师的精心指导表示忠心的感谢。谢谢!

人工智能课程设计报告--动物识别系统

计算机科学与技术学院 《人工智能》课程设计报告设计题目:动物识别系统 设计人员:学号: 学号: 学号: 学号: 学号: 学号: 指导教师: 2015年7月

目录 目录 (1) 摘要 (2) Abstract (2) 一、专家系统基本知识 (3) 1.1专家系统实际应用 (3) 1.2专家系统的开发 (3) 二、设计基本思路 (4) 2.1知识库 (4) ....................................................................................................... 错误!未定义书签。 2.1.2 知识库建立 (4) 2.1.3 知识库获取 (5) 2.2 数据库 (6) ....................................................................................................... 错误!未定义书签。 ....................................................................................................... 错误!未定义书签。 三、推理机构 (7) 3.1推理机介绍 (7) 3.1.1 推理机作用原理 (7) ....................................................................................................... 错误!未定义书签。 3.2 正向推理 (7) 3.2.1 正向推理基本思想 (7) 3.2.2 正向推理示意图 (8) 3.2.3 正向推理机所要具有功能 (8) 3.3反向推理 (8) ....................................................................................................... 错误!未定义书签。 3.3.2 反向推理示意图 (8) ....................................................................................................... 错误!未定义书签。 四、实例系统实现 (9)

C语言图形五子棋课程设计报告

北京师范大学C语言课程设计汇报 课题名称:游戏五子棋 指导老师:尹乾 课题组员:罗福莉赵帅帅何虹达院系:信息科学和技术 时间:20XX.3.15-20XX.4.20

摘要 五子棋是一个两人对弈纯策略型棋类游戏,应用C语言编写程序能够在计算机上实现二人对弈五子棋功效。二人对弈五子棋程序由欢迎界面显示、游戏界面生成、光标移动和落子、判定胜败、悔棋功效、提供音效等子程序组成;程序中应用了结构体、数组、全局变量、按键处理和图形编程等元素和语句。程序经过棋盘和棋子图像生成、二人移子和落子和判定胜败等功效实现,在计算机上实现了二人五子棋对弈。

目录 摘要-------------------------------------------------------------------------------------- 2 第1章:需求分析-------------------------------------------------------------------- 3 1.1五子棋背景-------------------------------------------------------------------- 3 1.2 五子棋需求分析和步骤设计 -------------------------------------------- 4 第2章:概要设计-------------------------------------------------------------------- 7 2.1 各类头文件和全局变量--------------------------------------------------- 7 2.2 画面显示模块---------------------------------------------------------------- 8 第3章:具体设计------------------------------------------------------------------ 11 3.1 玩家操作模块-------------------------------------------------------------- 11 3.2音效提供模块 -------------------------------------------------------------- 11 3.3 胜败判定模块-------------------------------------------------------------- 12 第4章:调试分析------------------------------------------------------------------ 13 4.1 图形模块 -------------------------------------------------------------------- 13 4.2 玩家操作模块-------------------------------------------------------------- 13 4.3 胜败判定模块-------------------------------------------------------------- 14 第5章:用户手册------------------------------------------------------------------ 14

c++五子棋课程设计报告

福建农林大学计算机与信息学院 课程设计报告 课程名称:面向对象程序设计课程设计 课程设计题目:五子棋 姓名: 系:计算机 专业:软件工程 年级: 学号: 指导教师: 职称: 年月日

福建农林大学计算机与信息学院计算机类课程设计报告结果评定

目录 1.设计目的 (4) 2.设计要求 (4) 3.设计方案 (4) 4.设计内容 (7) 4.1系统的主要结构和类结构 (7) 4.2 (2)五子棋类的结构 (7) 4.3⑶系统工作流程介绍.................................................... 7错误!未定义书签。⑷类的介绍. (8) 4.5 (5) 各个模块的介绍 (8) 4.6 (6)程序运行图示 (14) 5.总结 (16) 参考文献 (17)

(a)1.设计目的 (1)加深我对面向对象程序基本的理解和掌握。 (2)熟练掌握基本流程图的绘制。 (3)熟练visio的一些操作方法。 (4)能够在调试程序中快速发现并排除程序中的错误。 (5)提高面向对象程序语言解决实际中的问题的能力。 (b)2.设计要求 五子棋是玩家在游戏棋盘上逐个输入黑子或白子的坐标,因此游戏要求在DOS界面生成一个可供操作的棋盘。通过输入坐标完成对应落子情况,在输入过程中判断落子是否正确、是否有一方胜利等情况。编写代码可以在VC6.0下编译通过。游戏要能实现五子棋游戏的简单操作。程序中要体现面向对象思想。 (c)3.设计方案 (必须包含系统功能说明、用例图和类图) 一、用例图 落子 基于用户的用例图

步数用例图 系统用例图 1)输出棋盘界面菜单及图像2)开始进入控制3)黑白棋正确输入格式控制4)判断黑白输赢控制5)正确计数对羿步数及下一步所要走的棋盘界面

人工智能课程设计报告-罗马尼亚度假问题

人工智能课程设计报告-罗马尼亚度假 问题 1

2

3 2020年5月29日 课 程 :人工智能课程设计报告 班 级: 姓 名: 学 号: 指导教师:赵曼 11月

人工智能课程设计报告 课程背景 人工智能(Artificial Intelligence),英文缩写为AI。它是研究、开发用于模拟、延伸和扩展人的智能的理论、方法、技术及应用系统的一门新的技术科学。人工智能是计算机科学的一个分支,它企图了解智能的实质,并生产出一种新的能以人类智能相似的方式做出反应的智能机器,该领域的研究包括机器人、语言识别、图像识别、自然语言处理和专家系统等。人工智能从诞生以来,理论和技术日益成熟,应用领域也不断扩大,能够设想,未来人工智能带来的科技产品,将会是人类智慧的”容器”。 人工智能是对人的意识、思维的信息过程的模拟。人工智能不是人的智能,但能像人那样思考、也可能超过人的智能。 人工智能是一门极富挑战性的科学,从事这项工作的人必须懂得计算机知识,心理学和哲学。人工智能是包括十分广泛的科学,它由不同的领域组成,如机器学习,计算机视觉等等,总的说来,人工智能研究的一个主要目标是使机器能够胜任一些一般需要人类智能才能完成的复杂工作。但不同的时代、不同的人对这种”复杂工作”的理解是不同的。 人工智能是计算机学科的一个分支,二十世纪七十年代以来被称为世界三大尖端技术之一(空间技术、能源技术、人工智能)。也被认为是二十一世纪三大尖端技术(基因工程、纳米科学、人工智能)之一。这是因为近三十年来它获得了迅 速的发展,在很多学科领域都获得了广泛应用,并取得了丰硕的成果,人工智能已逐 - 1 - 2020年5月29日

C课程设计五子棋

/*这是我们c++课程设计五子棋,我用了许多循环语句,可能比较繁碎, 不过仔细分析的话,还是挺简单的。如果有什么不懂的地方可以加我q 1570169994 */ #include #include #include // 这些是一些必要的头文件 #include #include using namespace std; #define M 15 //此处定义棋盘大小为15*15,自己视情况而定 typedef struct Node { int a; //这里定义的结点在悔棋时要用到 int b; struct Node *next; }node; class Qipan { //定义一个棋盘类,这个类里有实现不同功能的函数 public: int a,b,t; //棋子的坐标我们用a,b表示,t表示接收的输入信息 int player; //player为1时,代表绿方下棋,2代表红方 int name[M][M]; //棋盘用一个15*15的二维数组表示 void reset(); //此函数实现重置功能,即将棋盘上的棋子清零 void chess(); //此函数实现下棋功能,是非常重要的 void win(); //此函数实现判断功能,即每当一方落子后,都要调用此函数 void explain(); //此函数是解释说明的函数 void output(int count[]); //此函数输出赢的一方 void gotoxy(int x,int y) { HANDLE hout; //这是实现光标移动的函数,具体可以百度一下 COORD coord; //x,y即为棋子的坐标,和a,b一样 coord.X = x; //此函数是将当前光标移动到x,y坐标处 coord.Y = y; hout = GetStdHandle(STD_OUTPUT_HANDLE); SetConsoleCursorPosition(hout,coord); } }; // main 函数 int main() { Qipan qipan; //定义一个棋盘对象 do { system("cls"); //清屏函数 cout<<"1.开始游戏 "<

五子棋课程设计报告

单 位 分院(系) 专 业 学 号 学生姓名 指导教师 完成日期 2011 年 05 月 日 摘 要 五子棋的历史:五子棋是一种两人对弈的纯策略型棋类游戏,是起源于中国古代 的传统黑白棋种之一.发展于日本,流行于欧美.容易上手,老少皆宜,而且趣味横生,引人入胜;不仅能增强思维能力,提高智力,而且富含哲理,有助于修身养性. 五子棋相传起源于四千多年前的尧帝时期,比围棋的历史还要悠久,可能早在“尧造围棋”之前,民间就已有五子棋游戏.有关早期五子棋的文史资料与围棋有相似之处,因为古代五子棋的棋具与围棋是完全相同的.在上古的神话传说中有“女娲造人,伏羲做棋”一说,《增山海经》中记载:“休舆之山有石焉,名曰帝台之棋,五色而文状鹑卵.”李善注引三国魏邯郸淳《艺经》中曰:“棋局,纵横各十七道,合二百八十九道,白黑棋子,各一百五十枚”.这段虽没明讲是何种棋类,但至少知道远古就以漂亮的石头为棋子.因而规则简单的五子棋也可能出自当时,并是用石子作棋子.亦有传说,五子棋最初流行于少数民族地区,以后渐渐演变成围棋并在炎黄子孙后代中遍及开来. 程序说明:本程序是一款棋类益智游戏程序,是用WIN-TC 编写在WINDOWS 系统下运行的娱乐游戏.本程序可以实现人人对战,操作采用键盘上的上下左右键控制棋子的上下左右移动,由空格键控制下棋,双方都可通过ESC 键终止游戏. 石家庄铁道大学课程设计 五子棋 课程设计题目

游戏开始后,红、白双方轮流下棋,程序会根据双方下棋的先后顺序自动显示不同颜色的棋子,提示当前下棋的棋手,任何一方由五子连成一线时,游戏结束,结束时会显示对战双方胜负情况. 关键词:五子棋游戏应用程序,C语言,图形函数 目录 第1章选题的意义2 意义2 设计思路 2 系统的基本要求3 第1章选题的意义 意义 通过游戏过程增加编程的兴趣,提高编程水平.编制该程序我对以下的知识点进行的巩固和掌握:1.数组元素为结构体的数组应用.2.全局变量应用.3.按键的处理.4.数组元素与蛇、食物的对应关系.5.图形方式等等.加深对所学知识的理解与掌握,增强自己对所学知识解决实际问题的能力,为以后的程序开发打下基础. 设计思路 棋盘设计为18×18格,初始状态光标在棋盘的中央,玩家1先走,轮流落子,当一方连成五子或下满棋盘时,游戏结束(连成五子的一方获胜,下满棋盘为和棋).当游戏一方胜利后显示胜利信息.从程序表面看,这是一个二维平面图,所以数据用二维数组来表示,数组两个下标可以表示棋盘上的位置,数组元素的值代表棋格上的状态,共有三种情况,分别是0代表空格,1代表白棋,2代表黑棋.这样程序的主要工作是接收棋手按键操作,棋手用Up、Down、Left、Right控制光标移动,空格键表示落子.一旦接收到空格键,说明棋手落子,先判断是否是有效位置,也就是说已经有棋子的位置不能重叠

课程设计-c语言设计-五子棋游戏 0528

课程设计-c语言设计-五子棋游戏

河南城建学院 测绘与城市空间信息系 测绘程序设计 题目: 五子棋游戏 班级: 0614112 人数: 3人 成员: 学号: 指导老师: 时间:2012年6月

目录 1课程设计报告-------------------2 1.1问题描述----------------------2 1.2 任务分工- - - - - - - - - - - - - - - 2 1.3需求分析---------------------------3 1.4概要设计-----------------------3 1.5详细设计-----------------------4 1.6调试分析---------------------5 2源程序---------------------6 3程序的说明文件-------------------12 4课设总结-----------------------13

1.课程设计报告 1.1问题描述 连珠(五子棋)是有两个人在一盘棋上进行对抗的竞技运动。在对局开始时,先由用户选择哪方先开局,先开局一方将一枚棋子落在一点上,然后由另一方在对方棋周围的交叉点上落子,如此轮流落子,直到某一方首先在棋盘的直线、横线或斜线上形成连续的五子则该方就算获胜。此时,算法结束。当有任何一方想退出时,都可在算法中实现。 1.2 五子棋的背景 传统五子棋的棋具与围棋相同,棋子分为黑白两色,棋盘为15×15,棋子放置于棋盘线交叉点上。两人对局,各执一色,轮流下一子,先将横、竖或斜线的5个或5个以上同色棋子连成不间断的一排者为胜。 因为传统五子棋在落子后不能移动或拿掉,所以也可以用纸和笔来进行游戏。 1.2 任务分工 组长:赵哲武 负责小组程序的输入和创新部分,分配任务,使工作衔接有序,以

人工智能课程设计

课程名称:人工智能及应用 设计题目:基于智能搜索的进路选排设计院系:计算机与通信工程系 班级:信号一班 姓名: 学号: 指导教师:胡可 西南交通大学峨眉校区 2013 年12 月13 日

课程设计任务书 专业铁道信号姓名代荣龙学号20108065 开题日期:2013 年09 月23 日完成日期:2013 年12 月13 日题目基于智能搜索的进路选排设计 一、设计的目的 通过对课程设计任务的完成,进一步理解智能搜索算法与计算机联锁软件设计的理论内容,并且巩固和深化所学课程的知识,同时培养综合运用所学课程知识,分析和解决实际问题的能力,逐步树立正确的设计思想及严谨认真的科学态度。 二、设计的内容及要求 要求每位同学能够根据对人工智能搜索算法以及计算机联锁的进路选排过程的知识,结合课程设计的内容,独立完成该课程设计。 设计内容: 1)自选信号布置图,建立站场型静态数据库,并绘制其模块链接图; 2)自选智能搜索算法,编写动态进路搜索选排程序; 3)用所编搜索程序对建立的数据库进行进路选排,并举例说明其过程。 三、指导教师评语 四、成绩 指导教师(签章) 年月日

一、设计题目 通过对课程设计任务的完成,进一步理解智能搜索算法与计算机联锁软件设计的理论内容,并且巩固和深化所学课程的知识,同时培养综合运用所学课程知识,分析和解决实际问题的能力,逐步树立正确的设计思想及严谨认真的科学态度。 可实现的功能: 能设置道岔、轨道、信号机以及道岔、轨道、信号机的状态; 满足正常情况下的接发列车演练; 站场状态的直观形象显示; 办理列车作业; 取消进路功能; 完备的进路选排、开放保持及解锁功能 仿真分析: 对计算机联锁人机界面的分析可知,人机界面是类似于6502电气集中联锁控制台,所以设计时参考6502的控制台进行设计。 为让操作员很快适应该系统,该系统延续了一些传统的操作方法: 选排进路任采用双按钮形式; 进路排好采用白色表示; 进路占用弹出对话框(线路占用、已办理同方向进路、已办理反方向发车); 进路解锁弹出对话框(进路已解锁); 道岔的状态(定位绿灯显示、反位黄灯显示); 信号机的状态(平时红灯、开放时绿灯); 调车信号机的状态(平时蓝色、开放时白色) 列车按钮绿色(设于线路中间); 调车按钮白色(设于线路一侧); 进路的取消任然用双按钮(始端按钮和终端按钮); 取消进路时点击总取消按钮后对应的上行或者下行总取消按钮表示灯亮红灯; 线路状态(平时为黑色、占用为白色); 当进路排好后改进路上的同方向的调车信号显示白灯; 该系统的进路搜索程序采用类似于进路表的形式,将始端按钮和终端按钮按下后,改程序自动检查敌对信号是否开放(若开放则提示“已建立反方向发车”)、沿途的列车信号机是否有开放(若开放则提示“已办理同方向进路”或“已办理反方向进路”)、复式交分道岔的一组道岔是否已占用(若占用则提示“线路已占用”)、股道是否空闲(若不空闲则提示“线路已占用”),进路建立之后将显示对应信号机的状态和道岔的状态。该操作界面采用Microsoft visual basic 6.0编写,能够很直观的反映调度员所需信息,同时采用人性化理念,用弹出式对话框来提示操作过程中的一些禁止信息来提醒调度员。 设计过程: (一)绘制站场图和站场型数据模块链接图

人工智能课程设计报告-n皇后问题解读

人工智能课程设计报告 课班姓学程:人工智能课程设计报告级 : 名: 号: 指导教师:赵曼 2015年11月

人工智能课程设计报告 人工智能课程设计报告 课程背景 人工智能(Artificial Intelligence),英文缩写为AI。它是研究、开发用于模拟、延伸和扩展人的智能的理论、方法、技术及应用系统的一门新的技术科学。人工智能是计算机科学的一个分支,它企图了解智能的实质,并生产出一种新的能以人类智能相似的方式做出反应的智能机器,该领域的研究包括机器人、语言识别、图像识别、自然语言处理和专家系统等。人工智能从诞生以来,理论和技术日益成熟,应用领域也不断扩大,可以设想,未来人工智能带来的科技产品,将会是人类智慧的“容器”。 人工智能是对人的意识、思维的信息过程的模拟。人工智能不是人的智能,但能像人那样思考、也可能超过人的智能。 人工智能是一门极富挑战性的科学,从事这项工作的人必须懂得计算机知识,心理学和哲学。人工智能是包括十分广泛的科学,它由不同的领域组成,如机器学习,计算机视觉等等,总的说来,人工智能研究的一个主要目标是使机器能够胜任一些通常需要人类智能才能完成的复杂工作。但不同的时代、不同的人对这种“复杂工作”的理解是不同的。 人工智能是计算机学科的一个分支,二十世纪七十年代以来被称为世界三大尖端技术之一(空间技术、能源技术、人工智能)。也被认为是二十一世纪三大尖端技术(基因工程、纳米科学、人工智能)之一。这是因为近三十年来它获得了迅速的发展,在很多学科领域都获得了广泛应用,并取得了丰硕的成果,人工智能已逐步成为一个独立的分支,无论在理论和实践上都已自成一个系统。 人工智能是研究使计算机来模拟人的某些思维过程和智能行为(如学习、推理、思考、规划等)的学科,主要包括计算机实现智能的原理、制造类似于人脑智能的计算机,使计算机能实现更高层次的应用。人工智能将涉及到计算机科学、心理学、哲学和语言学等学科。可以说几乎是自然科学和社会科学的所有学科,其范围已远远超出了计算机科学的范畴,人工智能与思维科学的关系是实践和理论的关系,人工智能是处于思维科学的技术应用层次,是它的一个应用分支。从思维观点看,人工智能不仅限于逻辑思维,要考虑形象思维、灵感思维才能促进人工智能的突破性的发展,数学常被认为是多种学科的基础科学,数学也进入语言、思维领域,人工智能学科也必须借用数学工具,数学不仅在标准逻辑、模糊数学等范围发挥作用,数学进入人工智能学科,它们将互相促进而更快地发展。

c语言程序设计五子棋

伊犁师范学院高级语言课程设计报告 学院:电子与信息工程学院 学生姓名: 学号: 专业届别: 指导教师: 完成时间:

五子棋游戏 1 设计目的及要求 目的: (1)学习综合运用C语言课程和其他相关课程的知识,提高分析解决实际问题的能力,进一步巩固、加深和拓宽所学的知识,进一步加强结构化程序设计的思想,加深对高级语言基本语言要素和控制结构的理解。 (2)全面系统的学习面向对象程序设计的基本概念、基本语法和编程方法,与同学合作设计整套程序,并且独立完成一定工作量的程序设计. (3)掌握程序设计中的常用算法和C语言的程序技巧,培养良好的程序设计风格。 (4)运用所学的知识了解五子棋游戏的制作结构,将所学的知识运用于实践中。 要求: (1)独自设计、编制、调试出一款五子棋游戏。 (2)要求该游戏具有趣味性和可操作性,能够正常运行。其中用到C语言中的各种语句、结构。(如其中需要注意全局变量和局部变量的申明,数组的使用等)(3)五子棋游戏要求能够进入欢迎界面,当有五颗相同颜色的棋子连续连成五颗,就胜出。 任务: 五子棋是一种传统的棋盘游戏,是我国古代传统的黑白棋种之一发展于日本,流行于欧洲任务内容就是设计一款老少皆宜、能够锻炼个人策略谋划能力棋。有助于孩子开发智力,或者闲暇时打发时间。原则: (1)系统性。系统作为统一整体而存在,因此,在设计中,要从系统的角度考虑。系统的代码要统一,传递语言要尽可能一致。 (2)可靠性。可靠性是指系统抵御外界干扰的能力及外界干扰时的恢复能力。

(3)规范性。游戏的运用以吸引玩家的乐趣为前提,一方面,系统设计应尽量避免不必要的复杂化,另一方面模块应尽量简洁,以缩短处理流程。 2 开发工具 C语言 3 应用平台 Windows xp 4 功能设计 游戏分析: 五子棋是两人之间的竞技游戏,该五子棋程序基本上实现了五子棋游戏的功能,有双方下棋之前的欢迎界面及下棋过程中的棋盘界面,还有最终会判断出输赢。同时,该游戏采用了二维坐标实现的,明了易懂,方便玩家在游戏过程中的基本操作,使游戏更加简便。细节方面,该程序有实时储存功能,随时记录。另外考虑到游戏挺简单的,就没有设置悔棋的相关模块。 游戏介绍: 该游戏是简单的双人五子棋,所实现的功能是能够显示欢迎界面,选择是否进行游戏,进入游戏界面以后,玩家开始下棋。玩家输入坐标则会在棋盘上显示棋子,(若是输入的坐标超出棋盘或者该位子已经有子则会提示玩家重新输入坐标位子),若输入则退出游戏。 4.1 算法设计 程序说明: 五子棋是一款经典的益智类游戏,通常是黑棋先行;五子棋专用盘为15*15方格,五个子的连接方向为横、竖、斜,当任一方的五个子在各方向上连成一线时,则该方获胜。 程序要求: 按照程序说明编写五子棋程序,要求可以进行双人之间的游戏。程序输出: 输出棋盘、棋子,并能够进行相应的操作。

人工智能课程设计(五子棋)解读

《人工智能导论》课程报告 课题名称:五子棋 姓名: X X 学号:114304xxxx 课题负责人名(学号): X X114304xxxx 同组成员名单(学号、角色): x x1143041325 XXX1143041036 指导教师:张建州 评阅成绩: 评阅意见: 提交报告时间:2014年 1 月 9 日

五子棋 计算机科学与技术专业 学生XXX 指导老师张建州 [摘要]人类之所以不断在进步,是因为我们人类一直不断的在思考,五子棋游戏程序的开发符合人类进步也是促进人类进步的一大动力之一。五子棋游戏程序让人们方便快捷的可以下五子棋,让人们在何时都能通过下棋来提高逻辑思维能力,同时也培养儿童的兴趣以及爱好,让孩子更加聪明。 同时,五子棋游戏程序的开发也使得五子棋这个游戏得到了广泛的推广,让世界各地的人们知道五子棋,玩上五子棋,这已经不是局限。五子棋游戏程序使得越来越多的人喜欢上了五子棋,热爱下五子棋,它是具有很好的带动性的。 关键词:五子棋进步思考

目录 《人工智能导论》课程报告 0 1 引言 (3) 1.1五子棋简介 (3) 1.2 五子棋游戏的发展与现状 (3) 2 研究问题描述 (4) 2.1 问题定义 (4) 2.2 可行性研究 (4) 2.3 需求分析 (5) 2.4 总体设计 (5) 2.5 详细设计 (6) 2.6编码和单元测试 (6) 3 人工智能技术 (6) 4 算法设计 (7) 4.1α-β剪枝算法 (7) 4.2极大极小树 (7) 4.3深度优先搜索(DFS) (8) 4.4静态估值函数 (9) 5 软件设计和实现 (9) 5.1 数据结构定义 (9) 5.2 程序流程图 (17) 6 性能测试 (18) 6.1 程序执行结果 (18) 7 总结 (21) 参考文献 (21)

人工智能课程设计

滑块问题求解系统 一、设计任务 用智能搜索算法中的盲目搜索和启发式搜索这两类基本方法设计八数码问题的求解系统。所谓八数码问题是指这样一种游戏:将分别标有数字1,2,3,…,8 的八块正方形数码牌任意地放在一块3×3 的数码盘上.放牌时要求不能重叠.于是,在3×3 的数码盘上出现了一个空格. 现在要求按照每次只能将与空格相邻的数码牌与空格交换的原则,将任意摆放的数码盘逐步摆成某种特殊的排列.如下图表示了一个具体的八数码问题求解. 二、设计环境及使用说明 设计环境主要采用VC++开发环境。 三、系统已实现的功能 用广度优先搜索算法和两种A*搜索算法实现八数码问题的求解系统。 四、算法思想及分析 1、广度优先搜索算法 算法思想: 这是一种盲目搜索算法。算法主要思想是从初始结点开始依次沿其上下左右四个方向扩展结点,并逐一检查这些后继结点是否为目标结点,若不等于目标结点则把该后继结点插入到数组末尾。然后取数组中未扩展的第一个结点重复以上操作,直到得到目标结点为止或在限定步数以内未得到解。 数据结构: 算法当中的结点用结构体实现, typedef struct{ int num[9]; //八个数码用一个一维数组来存储。 char expension; //记录是否可以扩展,Y代表可以扩展,N代表不可以。 char bandirect; //表示不可以执行的操作,'L'代表不能左移,'R'代表不能右 移,'U'代表不能上移,'D'代表不能下移,'C'代表可以任 意移动。 int father; //记录父节点的下标。 }Node; 扩展的结点存储在数组里: Node node[MAXSIZE]; //将搜索过的状态存储于该数组中。 算法当中遇到的问题和解决方法: 1)如何去表达八个数码的位置和每个结点状态的表示 用一维或二维数组去表示八个数码的位置关系,每个结点包含了一个一维数组 (用来表示八个数码的位置关系),可扩展标记(用来标识一个结点是否被扩 展过,避免重复扩展),限制移动方向的标记(避免一个结点在一个方向的重 复扩展),记录父节点的指针(父节点下标)。 2)如何以最简洁的方式表达一个结点在其四个方向的扩展 设定一个数组用以存储该结点在每个方位是否可扩展。操作一个结点时先根据

五子棋优秀教案1-5[1]

五子棋兴趣小组活动教案 第一课时认识五子棋(一) 学习目标: 1、认识五子棋棋盘,知道棋盘是有横竖各15条平行线交叉组成及棋盘上的4星1天元; 2、认识五子棋棋子,知道五子棋棋子是黑白225枚子,黑113枚子,白112枚子。 学会五子棋执棋方式。 3.了解五子棋的历史及比赛的计时制。 重点、难点: 认识五子棋棋盘,知道棋盘是有横竖各15条平行线交叉组成及棋盘上的4星1天元;认识五子棋棋子,知道五子棋棋子是黑白225枚子,黑113枚子,白112枚子;学会五子棋执棋方式。 一、谈话导入。 1、同学们,课前老师让你们收集并了解有关五子棋的资料,那谁愿意把自己收集到的知识讲给大家听? 2、学生汇报所收集的资料。 3、通过资料的收集,我们了解了许多五子棋的知识。 二、新课 1、五子棋的历史 五子棋是我们中国发明的,距离现在已经有四千多年的历史了 2、认识五子棋棋盘。出示图1

第二课时认识五子棋(二) (1)生观察棋盘,发现问题,提出质疑。 (2)通过其他学生的已有知识解决问题,师补充小结:棋盘由纵横各15条等距离、垂直交叉的平行线构成,形成225个交叉点。以对局开始时的黑方为准,棋盘上的纵行线从下向上用阿拉伯数字1—15 标记(注:QQ棋盘上的数字则从上向下标记),横行线从左到右用英文字母A--O标记,其中H8点为天元;D4、D12、L12、L4四点为星。 3、认识棋子。 (1)师演示,生直观:棋子由黑白两种颜色组成。师补充:共有225个棋子,与交叉点的个数相同;其中黑棋113个,白棋112个,不过平时下棋棋子少些也是可以的。 (2)正确的执棋方式。 师演示:是食指的指甲与中指的指肚儿夹住棋子。棋子落在 棋盘的交叉点上,落下后不能移动。 生执棋练习:先从自己的棋盒里拿棋,放到棋盘上的交叉点上。然后同桌之间比赛,看谁拿的快,放的准。 4.了解五子棋比赛计时制 (一)比赛时限 比赛时限可分每方30分钟到5小时不等,但一般要求一天内必须结束。有些比赛受条件限制,也可采用双方共用时限的方法,时限时间约是单方时限的双倍。双方共用时限到时后,可用限时走棋(几分钟之内走完若干手棋)或到时读秒的后续手段,直到该局结束。读秒时限,多采用1分钟制,凡一着棋用时不足1分钟,可不计时间,到1分钟则判负。 (二)迟到时限 比赛前,组织者都会规定迟到时限,一般为15分钟,每场比赛迟到时限一到,未到场的棋手均按弃权判负。

五子棋课程设计实验报告

西南交通大学 程序语言综合课程设计 五子棋游戏 课程《程序语言综合课程设计》 学院信息科学与技术学 专业软件工程 姓名 学号 20119050 日期 2016年月日

目录 第一章课程设计的目的和要求 (3) 1.1 课程设计的目的 (3) 1.2 课程设计的要求 (3) 1.3 课程设计的实验环境 (3) 第二章功能描述 (4) 第三章总体设计 (5) 3.1 功能模块设计 (5) 3.1.1 任务执行流程图 (5) 3.1.2 下棋函数流程图 (6) 3.2 数据结构设计 (7) 3.2.1 定义结构体 (7) 3.2.2 定义数组 (7) 3.2.3 全局变量 (7) 3.3 函数功能描述 (7) 第四章程序实现 (8) 4.1源码分析 (8) 4.2运行结果及界面介绍 (22) 第五章后记 (27)

第一章课程设计的目的和要求 1.1 课程设计的目的 1.加深对C语言数据类型,运算,语句结构及其程序设计的基本方法理解和掌握; 2.熟练掌握流程图的绘制、程序设计文档的书写; 3.通过编写一个完整的程序,一方面可以检查我们这学期的学习情况,为以后的学习打下坚实的基础; 4.熟悉C语言游戏编程,掌握五子棋游戏开发的基本原理,从而为以后的程序开发奠定基础。 1.2 课程设计的要求 1、编写程序代码,调试所写程序使其能够正确运行; 2、能进行基本的五子棋操作,有图形界面,能够用键盘操作; 3、能够实现悔棋、存档和读档等附加功能 1.3 课程设计的实验环境 该课程设计在设计与实验过程中需要在windows XP系统/windows 2000以上系统中进行,程序设计要求在visual C++6.0平台中进行,完成代码的编写、编译、调试、测试等工作。本游戏对计算机硬件和操作系统要求极低,所以在这里只是把自己的电脑硬件参数和系统参数列下: 硬件:Cpu:2.1GHZ,内存,2GB,硬盘:320GB,操作系统:windows xp 软件环境:安装VC++6.0

人工智能深度优先算法课程设计报告

人工智能课程报告 题目: 深 度 优 先 算 法 班级:XXXXXXXXXXX 学号:XXXXXXXXXXX 姓名:XXXXXXXXXXX

【摘要】结合生活中解决搜索问题所常用的思考方法与解题方法,从深度优先探讨了提高程序效率的适用技巧。 【关键词】1搜索顺序;2搜索对象;3搜索优化; 一、深度优先搜索的优化技巧 我们在做事情的时候,经常遇到这类问题——给出约束条件,求一种满足约束条件的方案,这类问题我们叫它“约束满足”问题。对于约束满足问题,我们通常可以从搜索的顺序和搜索的对象入手,进而提高程序的效率。 二、搜索的顺序及对象: 在解决约束满足问题的时候,问题给出的约束条件越强,对于搜索就越有利。之所以深度优先搜索的效率在很大程度上优于穷举,就是因为它在搜索过程中很好的利用了题目中的约束条件进行优化,达到提高程序效率的目的。 显然,在同样的一棵搜索树中,越在接近根接点的位置利用约束条件优化效果就越好。如何在搜索中最大化的利用题目的约束条件为我们提供剪枝的依据,是提高深度优先搜索效率的一个很重要的地方。而不同的搜索顺序和搜索对象就直接影响到我们对于题目约束条件的运用。 三、搜索特点 1.由于深度搜索过程中有保留已扩展节点,则不致于重复构造不必要的子树系统。 2.深度优先搜索并不是以最快的方式搜索到解,因为若目标节点在第i层的某处,必须等到该节点左边所有子树系统搜索完毕之后,才会访问到该节点,因此,搜索效率还取决于目标节点在解答树中的位置。

3.由于要存储所有已被扩展节点,所以需要的内存空间往往比较大。 4.深度优先搜索所求得的是仅仅是目前第一条从起点至目标节点的树枝路径,而不是所有通向目标节点的树枝节点的路径中最短的路径。 5.适用范围:适用于求解一条从初始节点至目标节点的可能路径的试题。若要存储所有解答路径,可以再建立其它空间,用来存储每个已求得的解。若要求得最优解,必须记下达到目前目标的路径和相应的路程值,并与前面已记录的值进行比较,保留其中最优解,等全部搜索完成后,把保留的最优解输出。 四、算法数据结构描述 深度优先搜索时,最关键的是结点扩展(OPEN)表的生成,它是一个栈,用于存放目前搜索到待扩展的结点,当结点到达深度界限或结点不能再扩展时,栈顶结点出栈,放入CLOSE表(存放已扩展节点),继续生成新的结点入栈OPEN 表,直到搜索到目标结点或OPEN栈空为止。 具体算法如下: ①把起始结点S放到非扩展结点OPEN表中(后进先出的堆栈),如果此结点为一目标结点,则得到一个解。 ②如果OPEN为一空表,则搜索失败退出。 ③取OPEN表最前面(栈顶)的结点,并把它放入CLOSED的扩展结点表中,并冠以顺序编号n。 ④如果结点n的深度等于最大深度,则转向2。 ⑤否则,扩展结点n,产生其全部子结点,把它们放入OPEN表的前头(入栈),并配上指向n的返回指针;如果没有后裔,则转向2。 ⑥如果后继结点中有任一个为目标结点,则求得一个解,成功退出;否则,转向2。

MFC课程设计报告-一个简单的五子棋游戏

设计一个简单的五子棋游戏 一、设计目标与内容 1.了解Windows编程的基础知识,掌握MFC应用程序的基本知 识; 2.基本掌握面向对象程序设计的基本思路和方法; 3.掌握用VC++开发应用程序的的一般步骤和方法; 4.能够利用所学的基本知识, 设计一个简单的五子棋游戏,具 有以下功能:①数据结构的设计;五子棋棋盘的绘制。②两人下棋时,两人下棋算法的设计。③两人下棋时,判断任一方获胜的算法的设计。 二、设计要求 1.用VC++进行编码,实现应用程序的功能。注重编码质量, 代码要有适当的注释; 提交设计报告一份(课程设计任务书、目录、主要的数据结构、设计的基本思路、设计的步骤及主要代码、心得体会、参考文献)。总体设计 运行时效果如下:

图3-1 这个程序只能进行两个人之间的对弈,不能进行人机对弈,由于时间和个人能力的原因所以人机对弈的算法就没有写出。同时程序中也存在着很多漏洞,但基本的功能都已经实现,还有待继续改进。 详细设计 新建工程game_wzq

选择单文档应用程序,在Step 4 of 6中先中Windows Sockets 复选框。如下图: 图3-2 资源编辑 黑白位图Bitmap以表示棋盘上面的棋子: IDB_BLACK DB_WHITE 黑白鼠标Cursor以替换当前鼠标: IDC_CURSOR1 黑棋子

IDC_CURSOR2 白棋子 黑白图标Icon以显示在状态栏供以提示 IDI_BLACK IDI_WHITE 菜单以供操作: 开始: ID_START 保存: ID_SAVE 打开: ID_OPEN 如下图所示: 图3-3 变量函数 首先,为了实现状态栏的应用,我们必须更改它的变量:

A-算法人工智能课程设计

人工智能(A*算法) 一、 A*算法概述 A*算法是到目前为止最快的一种计算最短路径的算法,但它一种‘较优’算法,即它一般只能找到较优解,而非最优解,但由于其高效性,使其在实时系统、人工智能等方面应用极其广泛。 A*算法结合了启发式方法(这种方法通过充分利用图给出的信息来动态地作出决定而使搜索次数大大降低)和形式化方法(这种方法不利用图给出的信息,而仅通过数学的形式分析,如Dijkstra算法)。它通过一个估价函数(Heuristic Function)f(h)来估计图中的当前点p到终点的距离(带权值),并由此决定它的搜索方向,当这条路径失败时,它会尝试其它路径。 因而我们可以发现,A*算法成功与否的关键在于估价函数的正确选择,从理论上说,一个完全正确的估价函数是可以非常迅速地得到问题的正确解答,但一般完全正确的估价函数是得不到的,因而A*算法不能保证它每次都得到正确解答。一个不理想的估价函数可能会使它工作得很慢,甚至会给出错误的解答。 为了提高解答的正确性,我们可以适当地降低估价函数的值,从而使之进行更多的搜索,但这是以降低它的速度为代价的,因而我们可以根据实际对解答的速度和正确性的要求而设计出不同的方案,使之更具弹性。 二、 A*算法分析 众所周知,对图的表示可以采用数组或链表,而且这些表示法也各也优缺点,数组可以方便地实现对其中某个元素的存取,但插入和删除操作却很困难,而链表则利于插入和删除,但对某个特定元素的定位却需借助于搜索。而A*算法则需要快速插入和删除所求得的最优值以及可以对当前结点以下结点的操作,因而数组或链表都显得太通用了,用来实现A*算法会使速度有所降低。要实现这些,可以通过二分树、跳转表等数据结构来实现,我采用的是简单而高效的带优先权的堆栈,经实验表明,一个1000个结点的图,插入而且移动一个排序的链表平均需500次比较和2次移动;未排序的链表平均需1000次比较和2次移动;而堆仅需10次比较和10次移动。需要指出的是,当结点数n大于10,000时,堆将不再是正确的选择,但这足已满足我们一般的要求。

人工智能课程报告封面

物理与电子工程学院 《人工智能》 课程设计报告 课题名称 专业 班级 学生姓名 学号 指导教师崔明月 成绩 2014年6月18日

题目 摘要: 关键词: 1.引言 正文 结论 参考文献:(文献10篇以上,参考下面的文献列写格式) [1]徐国华,谭民.移动机器人的发展现状及其趋势[J]. 机器人技术与应用, 2001(3):7~14. [2]H.F Durrant Whyte. Where am I? A tutorial on mobile vehicle localization. Industrial Robot, 1994, 21(2):11~16. [3]彭文刚,彭宝林,柳胜.移动机器人导航系统的研究现状与发展趋势[J]. 机电信 息, 2009(36):69~70. [4]高峰, 黄玉美, 林义忠等.自主移动机器人的模糊导航[J]. 西安理工大学 报,2005,21(4):337~341. 一、报告内容: 就下面的一方面或几方面的内容写一篇报告综述,包括目的、意义,基本概念、定义,主要的控制方法以及结果分析等,最后给出小节及自己的学习心得,要有图表,严禁抄袭,如若发现本课程按零分计! 1.模糊控制系统设计 2.神经网络控制系统 3.遗传算法在系统辨识、控制中的应用 4.模糊控制综述 5.神经网络控制综述 注:题目自拟,也可以自选题目。

二、格式与字体要求: 正文开头的每段开头空2个字符,正文小四号字,22磅行距。大小标题加黑,标题后空一行,一级标题三号字,二级标题四号字,三级标题小四号字(不按格式要求做扣分处理)。 封面见前面示例,单面打印。

相关主题
文本预览
相关文档 最新文档