首页 淘文阁 - 分享文档赚钱的网站 > 教育专区 > 教案示例 > 人工智能课程计划设计报告罗马尼亚度假问答.doc

人工智能课程计划设计报告罗马尼亚度假问答.doc

收藏

编号：2573656    类型：共享资源    大小：345.52KB    格式：DOC    上传时间：2020-04-21
10
金币
举报
举报 版权申诉
版权申诉 word格式文档无特别注明外均可编辑修改；预览文档经过压缩，下载后原文更清晰！ 立即下载
关 键 词：
人工智能 课程 计划 规划 设计 报告 讲演 呈文 罗马尼亚 度假 问答
资源描述：
\\ 课 程:人工智能课程设计报告 班 级: 姓 名: 学 号: 指导教师:赵曼 2015年11月 人工智能课程设计报告 课程背景 人工智能（Artificial Intelligence），英文缩写为AI。它是研究、开发用于模拟、延伸和扩展人的智能的理论、方法、技术及应用系统的一门新的技术科学。 人工智能是计算机科学的一个分支，它企图了解智能的实质，并生产出一种新的能以人类智能相似的方式做出反应的智能机器，该领域的研究包括机器人、语言识别、图像识别、自然语言处理和专家系统等。人工智能从诞生以来，理论和技术日益成熟，应用领域也不断扩大，可以设想，未来人工智能带来的科技产品，将会是人类智慧的“容器”。 人工智能是对人的意识、思维的信息过程的模拟。人工智能不是人的智能，但能像人那样思考、也可能超过人的智能。 人工智能是一门极富挑战性的科学，从事这项工作的人必须懂得计算机知识，心理学和哲学。人工智能是包括十分广泛的科学，它由不同的领域组成，如机器学习，计算机视觉等等，总的说来，人工智能研究的一个主要目标是使机器能够胜任一些通常需要人类智能才能完成的复杂工作。但不同的时代、不同的人对这种“复杂工作”的理解是不同的。 人工智能是计算机学科的一个分支，二十世纪七十年代以来被称为世界三大尖端技术之一（空间技术、能源技术、人工智能）。也被认为是二十一世纪三大尖端技术（基因工程、纳米科学、人工智能）之一。这是因为近三十年来它获得了迅速的发展，在很多学科领域都获得了广泛应用，并取得了丰硕的成果，人工智能已逐步成为一个独立的分支，无论在理论和实践上都已自成一个系统。 人工智能是研究使计算机来模拟人的某些思维过程和智能行为（如学习、推理、思考、规划等）的学科，主要包括计算机实现智能的原理、制造类似于人脑智能的计算机，使计算机能实现更高层次的应用。人工智能将涉及到计算机科学、心理学、哲学和语言学等学科。可以说几乎是自然科学和社会科学的所有学科，其范围已远远超出了计算机科学的范畴，人工智能与思维科学的关系是实践和理论的关系，人工智能是处于思维科学的技术应用层次，是它的一个应用分支。从思维观点看，人工智能不仅限于逻辑思维，要考虑形象思维、灵感思维才能促进人工智能的突破性的发展，数学常被认为是多种学科的基础科学，数学也进入语言、思维领域，人工智能学科也必须借用数学工具，数学不仅在标准逻辑、模糊数学等范围发挥作用，数学进入人工智能学科，它们将互相促进而更快地发展。 题目一：罗马利亚度假问题 一. 问题描述 分别用代价一致的宽度优先、有限制的深度优先（预设搜索层次）、贪婪算法和A*算法求解“罗马利亚度假问题”。即找到从初始地点 Arad到 目的地点 Bucharest 的一条路径。 要求： 分别用文件存储地图和启发函数表，用生成节点数比较几种算法在问题求解时的效率，并列表给出结果。 数据如下： 1、地图 2、启发函数值 Arad 366 Mehadia 241 Bucharest 0 Neamt 234 Craiova 160 Oradea 380 Doberta 242 Pitesti 100 Eforie 161 Rimmicu_Vikea 193 Fagaras 176 Sibiu 253 Glurgiu 77 Timisoara 329 Hirsova 151 Urziceni 80 Iasi 226 Vaslui 199 Lugoj 244 Zerind 374 3、地图数据表 0 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 140 1000 118 1000 1000 1000 1000 1000 75 1000 0 1000 1000 1000 1000 75 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 70 1000 1000 1000 0 1000 1000 1000 1000 101 1000 1000 211 1000 90 1000 1000 85 1000 1000 1000 1000 1000 1000 1000 0 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 87 1000 1000 1000 1000 1000 1000 1000 0 1000 120 138 1000 146 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 0 1000 1000 1000 1000 1000 151 1000 1000 1000 1000 1000 1000 1000 71 1000 75 1000 1000 120 1000 0 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 101 1000 138 1000 1000 0 1000 97 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 0 1000 1000 1000 1000 1000 86 1000 1000 1000 1000 1000 1000 1000 1000 1000 146 1000 1000 97 1000 0 1000 80 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 211 1000 1000 1000 1000 1000 1000 1000 0 99 1000 1000 1000 1000 1000 1000 1000 1000 140 1000 1000 1000 1000 151 1000 1000 1000 80 99 0 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 90 1000 1000 1000 1000 1000 1000 1000 1000 1000 0 1000 1000 1000 1000 1000 1000 1000 118 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 0 1000 1000 1000 1000 111 1000 1000 1000 1000 1000 1000 1000 1000 1000 86 1000 1000 1000 1000 1000 0 98 1000 1000 1000 1000 1000 1000 85 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 98 0 1000 1000 1000 1000 1000 1000 1000 87 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 0 92 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 92 0 1000 1000 1000 70 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 111 1000 1000 1000 1000 0 1000 75 1000 1000 1000 1000 71 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 0 二.设计分析 1.算法分析 1) 宽度优先搜索算法 广度优先搜索使用队列（queue）来实现 1、把根节点放到队列的末尾。 2、每次从队列的头部取出一个元素，查看这个元素所有的下一级元素，把它们放到队列的末尾。并把这个元素记为它下一级元素的前驱。 3、找到所要找的元素时结束程序。 4、如果遍历整个图还没有找到，结束程序。 2)深度优先搜索算法 深度优先搜索用栈（stack）来实现，整个过程可以想象成一个倒立的树形： 1、把根节点压入栈中。 2、每次从栈中弹出一个元素，搜索所有在它下一级的元素，把这些元素压入栈中。并把这个元素记为它下一级元素的前驱。 3、找到所要找的元素时结束程序。 4、如果遍历整个树还没有找到，结束程序。 3)贪婪算法 1.建立数学模型来描述问题 ⒉把求解的问题分成若干个子问题。 ⒊对每一子问题求解，得到子问题的局部最优解。 ⒋把子问题的解局部最优解合成原来解问题的一个解。 实现该算法的过程： 从问题的某一初始解出发； while 能朝给定总目标前进一步 do 求出可行解的一个解元素； 由所有解元素组合成问题的一个可行解。 4)A*算法 A*[1] （A-Star)算法是一种静态路网中求解最短路最有效的直接搜索方法。 公式表示为： f(n)=g(n)+h(n), 其中 f(n) 是从初始点经由节点n到目标点的估价函数， g(n) 是在状态空间中从初始节点到n节点的实际代价， h(n) 是从n到目标节点最佳路径的估计代价。 保证找到最短路径（最优解的）条件，关键在于估价函数f(n)的选取： 估价值h(n)<= n到目标节点的距离实际值，这种情况下，搜索的点数多，搜索范围大，效率低。但能得到最优解。并且如果h(n)=d(n)，即距离估计h(n)等于最短距离，那么搜索将严格沿着最短路径进行， 此时的搜索效率是最高的。 如果 估价值>实际值,搜索的点数少，搜索范围小，效率高，但不能保证得到最优解。 2.数据结构 1)图结构： 实现存储“罗马尼亚度假问题”的图空间； 抽象图结构的实现： typedef struct //图节点类型 { char cityname[20]; int value; int cost; }Ver; class Graph //图结构 { public: Graph(); ~Graph(); Ver V[MaxV]; int edge[MaxV][MaxV]; int numofedges; //注意这个变量的引用位置 //读取地图节点信息 void ReadVertex(); //读取地图边关系信息 void ReadEdge(); //取与第V个节点的第一个邻接点 int GetFirstVertex(int v); //找到第V1个节点的V2之后的下一个邻接节点 int GetNextVertex(int v1, int v2); int GetVerValue(int index);//获取V[index] 的ver 的value值 int GetVerCost(int index);//获取V[index] 的ver 的cost 值 int GetEdge(int row, int col);//获取edge[row][col] 的值 void SetVerCost(int index,int cost); }; 2)队列结构 宽度优先算法以及A*算法 使用到。 抽象队列结构实现： class SeqQueue { public: SeqQueue(); ~SeqQueue(); void QueueInitiate(); int QueueNotEmpty(); int QueueAppend(int x); int QueueDelete(int *d); int QueueOrderAppend(int x, Graph &G); //A*算法使用 int Queue_A_OrderAppend(int x, Graph &G); private: int queue[MaxSize]; int rear; int front; int count; }; 3)栈结构 深度优先算法使用； 栈结构的抽象类型实现： class Stack { public: Stack(); ~Stack(); bool StackNotFull(); bool StakNotEmpty(); void StackPop(Graph &G); void StackPush(int x, Graph &G); void PrintStack(Graph &G); int GetWeight(); private: int a[100]; int top1; int weight; }; 三.算法设计 1) 宽度优先搜索算法 //宽度优先算法 void Romania_Trip::BroadFirstSearch(Graph &graph, int v) { int u, w; i = 0; SeqCQuene queue; visited[v] = 1;//访问节点 count++; if (v == end)return; queue.QueueAppend( v);//入队列 while (queue.QueueNotEmpty())//队列非空 { queue.QueueDelete(&u);//取队列节点 w = graph.GetFirstVertex( u); while (w != -1) //有子节点的话 { if (!visited[w])//如果子节点未被访问，则访问子节点 { Visit(w, u); visited[w] = 1; count++; if (w == end)//找到结果 { Print(graph, b, end, v); return; } queue.QueueAppend(w);//节点压入队列 } w = graph.GetNextVertex(u, w); } } } 2)深度优先搜索算法 //深度优先算法 bool isOK = false; int level = 0; const int Level = 8;//预设的搜索层次 void Romania_Trip::DepthFirstSearch(Graph &graph, int v, Stack &stack) { int w; i = 0; if (isOK == true)return; if (level+1 > Level)return;//大于搜索层次时不再深入 level++; visited[v] = 1;//访问该节点 count++; stack.StackPush(v, graph); if (v == end || stack.GetWeight() >= MaxWeight) { w = -1; if (v == end&&stack.GetWeight() <= MaxWeight) { cout << "---深度优先遍历路径为："; stack.PrintStack(graph); /*if (MaxWeight>stack.GetWeight()) MaxWeight = stack.GetWeight();*/ cout << "---路径长度为：" << stack.GetWeight() << endl << "---访问节点数为：" << count << endl <<"---搜索层次："< #include "Stack.h" #define MaxSize 30 /*#ifndef MY_DEBUG #define MY_DEBUG #endif/*/ class SeqQueue { public: SeqQueue(); ~SeqQueue(); void QueueInitiate(); int QueueNotEmpty(); int QueueAppend(int x); int QueueDelete(int *d); int QueueOrderAppend(int x, Graph &G); //A*算法使用 int Queue_A_OrderAppend(int x, Graph &G); private: int queue[MaxSize]; int rear; int front; int count; }; typedef SeqQueue SeqCQuene; //Romania_Trip.h #pragma once #include "Queue.h" typedef struct { int father; int me; }way; class Romania_Trip { public: Romania_Trip(); ~Romania_Trip(); void Visit(int v, int u); void Print(Graph &graph, way *b, int end, int start); void BroadFirstSearch(Graph &graph, int v); void DepthFirstSearch(Graph &graph, int v,Stack &stack); void Greedy_Algorithms(Graph &graph, int v); void AStar_Algorithms(Graph &graph, int v); void ReSet(); int GetCount(); int GetMaxWeight(); int GetEnd(); way* GetB(); private: way *b; int i; int end; int count; int visitedCity[20]; int MaxWeight; int visited[20]; }; //Stack.h #pragma once #include"Graph.h" #include using namespace std; /*#ifndef MY_DEBUG #define MY_DEBUG #endif*/ class Stack { public: Stack(); ~Stack(); bool StackNotFull(); bool StakNotEmpty(); void StackPop(Graph &G); void StackPush(int x, Graph &G); void PrintStack(Graph &G); int GetWeight(); private: int a[100]; int top1; int weight; }; //Graph.cpp #include"Graph.h" #include #include #include #include using namespace std; Graph::Graph() { numofedges = 0; } Graph::~Graph() { } void Graph::ReadVertex() { int i=0, v; char ch[20]; fstream infile("启发式数值.txt", ios::in); while (infile >> ch && infile >> v) { #ifdef MY_DEBUG printf("%s\t%d\n", ch, v); #endif V[i].value = v; V[i].cost = 0; strcpy(V[i].cityname, ch); i++; } } void Graph::ReadEdge() { int valu, i; fstream infile("地图数据表.txt", ios::in); i = 0; while (infile >> valu) { edge[i / 20][i % 20] = valu; #ifdef MY_DEBUG if (i % 20 == 0)cout << endl; cout<= 20) { return -1; } for (int col = 0; col<20; col++) if (edge[v][col]>0 && edge[v][col]<1000) return col; return -1; } //找到第V1个节点的V2之后的下一个邻接节点 int Graph::GetNextVertex(int v1, int v2) { if (v1<0 || v1 >= 20 || v2<0 || v2 >= 20) { return -1; } for (int col= v2 + 1; col<20; col++) if (edge[v1][col]>0 && edge[v1][col]<1000) return col; return -1; } int Graph::GetVerValue(int index)//获取V[index] 的ver 的values值 { return V[index].value; } int Graph::GetVerCost(int index)//获取V[index] 的ver 的cost 值 { return V[index].cost; } int Graph::GetEdge(int row, int col)//获取edge[row][col] 的值 { return edge[row][col]; } void Graph::SetVerCost(int index, int cost){ V[index].cost = cost; } //Queue.cpp #include"Queue.h" #include #include "Stack.h" SeqQueue::SeqQueue() { rear = 0; front = 0; count = 0; } SeqQueue::~SeqQueue() { } int SeqQueue::QueueNotEmpty() { if (count != 0)return 1; else return 0; } int SeqQueue::QueueAppend( int x) { if (count>0 && rear == front) { cout << "队列已满" << endl; return 0; } else { queue[rear] = x; rear = (rear + 1) % MaxSize; count++; return 1; } } int SeqQueue::QueueDelete( int *d) { if (count == 0) { cout << "队列已空" << endl; return 0; } else { *d = queue[front]; front = (front + 1) % MaxSize; count--; return 1; } } int SeqQueue::QueueOrderAppend( int x, Graph &G) { if (count>0 && rear == front) { cout << "队列已满" << endl; return 0; } else { if (count == 0 || G.V[x].value >= G.V[queue[rear - 1]].value)//队尾插入 { queue[rear] = x; rear = (rear + 1) % MaxSize; count++; return 1; } else { if (G.V[x].value <= G.V[ queue[front] ].value)//队头插入 { queue[front - 1] = x; front = (front - 1 + MaxSize) % MaxSize; count++; return 1; } else //排序找位置插入 { int position = front; while (G.V[x].value>G.V[queue[position]].value) { position++; } int i; for (i = front; i
展开阅读全文
提示  淘文阁 - 分享文档赚钱的网站所有资源均是用户自行上传分享，仅供网友学习交流，未经上传用户书面授权，请勿作他用。
关于本文
本文标题：人工智能课程计划设计报告罗马尼亚度假问答.doc
链接地址：https://www.taowenge.com/p-2573656.html
关于淘文阁 - 版权申诉 - 用户使用规则 - 积分规则 - 联系我们

本站为文档C TO C交易模式，本站只提供存储空间、用户上传的文档直接被用户下载，本站只是中间服务平台，本站所有文档下载所得的收益归上传人(含作者)所有。本站仅对用户上传内容的表现方式做保护处理，对上载内容本身不做任何修改或编辑。若文档所含内容侵犯了您的版权或隐私，请立即通知淘文阁网，我们立即给予删除！客服QQ：136780468 微信：18945177775 电话：18904686070

工信部备案号：黑ICP备15003705号 © 2020-2023 www.taowenge.com 淘文阁 

收起
在线客服
意见反馈
返回顶部
展开
QQ交谈
返回顶部