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

我在此端你在彼岸范文报告范文

精选回答

人工智能课程设计报告-罗马尼亚度假问题本文简介：人工智能课程设计报告课程:人工智能课程设计报告班级:姓名:学号:指导教师:赵曼2015年11月人工智能课程设计报告课程背景人工智能（ArtificialIntelligence），英文缩写为AI。它是研究、开发用于模拟、延伸和扩展人的智能的理论、方法、技术及应用系统的一门新的技术科学。人工智能是计算

人工智能课程设计报告-罗马尼亚度假问题本文内容：

人工智能课程设计报告

课

程:人工智能课程设计报告

班

级:

姓

名:

学

号:

指导教师:赵曼

2015年11月

人工智能课程设计报告

课程背景

人工智能（Artificial

Intelligence），英文缩写为AI。它是研究、开发用于模拟、延伸和扩展人的智能的理论、方法、技术及应用系统的一门新的技术科学。

人工智能是计算机科学的一个分支，它企图了解智能的实质，并生产出一种新的能以人类智能相似的方式做出反应的智能机器，该领域的研究包括机器人、语言识别、图像识别、自然语言处理和专家系统等。人工智能从诞生以来，理论和技术日益成熟，应用领域也不断扩大，可以设想，未来人工智能带来的科技产品，将会是人类智慧的“容器”。

人工智能是对人的意识、思维的信息过程的模拟。人工智能不是人的智能，但能像人那样思考、也可能超过人的智能。

人工智能是一门极富挑战性的科学，从事这项工作的人必须懂得计算机知识，心理学和哲学。人工智能是包括十分广泛的科学，它由不同的领域组成，如机器学习，计算机视觉等等，总的说来，人工智能研究的一个主要目标是使机器能够胜任一些通常需要人类智能才能完成的复杂工作。但不同的时代、不同的人对这种“复杂工作”的理解是不同的。

人工智能是计算机学科的一个分支，二十世纪七十年代以来被称为世界三大尖端技术之一（空间技术、能源技术、人工智能）。也被认为是二十一世纪三大尖端技术（基因工程、纳米科学、人工智能）之一。这是因为近三十年来它获得了迅速的发展，在很多学科领域都获得了广泛应用，并取得了丰硕的成果，人工智能已逐步成为一个独立的分支，无论在理论和实践上都已自成一个系统。

人工智能是研究使计算机来模拟人的某些思维过程和智能行为（如学习、推理、思考、规划等）的学科，主要包括计算机实现智能的原理、制造类似于人脑智能的计算机，使计算机能实现更高层次的应用。人工智能将涉及到计算机科学、心理学、哲学和语言学等学科。可以说几乎是自然科学和社会科学的所有学科，其范围已远远超出了计算机科学的范畴，人工智能与思维科学的关系是实践和理论的关系，人工智能是处于思维科学的技术应用层次，是它的一个应用分支。从思维观点看，人工智能不仅限于逻辑思维，要考虑形象思维、灵感思维才能促进人工智能的突破性的发展，数学常被认为是多种学科的基础科学，数学也进入语言、思维领域，人工智能学科也必须借用数学工具，数学不仅在标准逻辑、模糊数学等范围发挥作用，数学进入人工智能学科，它们将互相促进而更快地发展。

题目一：罗马利亚度假问题

一.

问题描述

分别用代价一致的宽度优先、有限制的深度优先（预设搜索层次）、贪婪算法和A*算法求解“罗马利亚度假问题”。即找到从初始地点

Arad到

目的地点

Bucharest

的一条路径。

要求：

分别用文件存储地图和启发函数表，用生成节点数比较几种算法在问题求解时的效率，并列表给出结果。

数据如下：

1、地图

2、启发函数值

Arad

366

Mehadia

241

Bucharest

Neamt

234

Craiova

160

Oradea

380

Doberta

242

Pitesti

100

Eforie

161

Rimmicu_Vikea

193

Fagaras

176

Sibiu

253

Glurgiu

Timisoara

329

Hirsova

151

Urziceni

Iasi

226

Vaslui

199

Lugoj

244

Zerind

374

3、地图数据表

1000

140

1000

118

1000

101

1000

211

1000

120

138

1000

146

1000

151

1000

120

1000

101

1000

138

1000

146

1000

211

1000

140

1000

151

1000

118

1000

111

1000

111

1000

二.设计分析

1.算法分析

宽度优先搜索算法

广度优先搜索使用队列（queue）来实现

1、把根节点放到队列的末尾。

2、每次从队列的头部取出一个元素，查看这个元素所有的下一级元素，把它们放到队列的末尾。并把这个元素记为它下一级元素的前驱。

3、找到所要找的元素时结束程序。

4、如果遍历整个图还没有找到，结束程序。

2)深度优先搜索算法

深度优先搜索用栈（stack）来实现，整个过程可以想象成一个倒立的树形：

1、把根节点压入栈中。

2、每次从栈中弹出一个元素，搜索所有在它下一级的元素，把这些元素压入栈中。并把这个元素记为它下一级元素的前驱。

3、找到所要找的元素时结束程序。

4、如果遍历整个树还没有找到，结束程序。

3)贪婪算法

1.建立数学模型来描述问题

⒉把求解的问题分成若干个子问题。

⒊对每一子问题求解，得到子问题的局部最优解。

⒋把子问题的解局部最优解合成原来解问题的一个解。

实现该算法的过程：

从问题的某一初始解出发；

while

能朝给定总目标前进一步

求出可行解的一个解元素；

由所有解元素组合成问题的一个可行解。

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)实际值,搜索的点数少，搜索范围小，效率高，但不能保证得到最优解。

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(intd);

int

QueueOrderAppend(int

x,Graph

//A*算法使用

int

Queue_A_OrderAppend(int

x,Graph

private:

int

queue[MaxSize];

int

rear;

int

front;

int

count;

};

3)栈结构

深度优先算法使用；

栈结构的抽象类型实现：

class

Stack

{

public:

Stack();

~Stack();

bool

StackNotFull();

bool

StakNotEmpty();

void

StackPop(Graph

void

StackPush(int

x,Graph

void

PrintStack(Graph

int

GetWeight();

private:

int

a[100];

int

top1;

int

weight;

};

三.算法设计

宽度优先搜索算法

//宽度优先算法

void

Romania_Trip::BroadFirstSearch(Graph

SeqCQuene

queue;

visited[v]

1;//访问节点

count++;

end)return;

queue.QueueAppend(

v);//入队列

while

(queue.QueueNotEmpty())//队列非空

{

queue.QueueDelete(//取队列节点

graph.GetFirstVertex(

u);

while

-1)

//有子节点的话

{

(!visited[w])//如果子节点未被访问，则访问子节点

{

Visit(w,u);

visited[w]

count++;

end)//找到结果

{

Print(graph,b,end,v);

return;

}

queue.QueueAppend(w);//节点压入队列

}

graph.GetNextVertex(u,w);

}

2)深度优先搜索算法

//深度优先算法

bool

isOK

false;

int

level

const

int

Level

8;//预设的搜索层次

void

Romania_Trip::DepthFirstSearch(Graph

(isOK

true)return;

(level+1

Level)return;//大于搜索层次时不再深入

level++;

visited[v]

1;//访问该节点

count++;

stack.StackPush(v,graph);

end

stack.GetWeight()

MaxWeight)

{

-1;

end*/

cout

#include

“Stack.h“#define

MaxSize

/*#ifndef

MY_DEBUG

#define

MY_DEBUG

#endif/*/

class

SeqQueue

{

public:

SeqQueue();

~SeqQueue();

void

QueueInitiate();

int

QueueNotEmpty();

int

QueueAppend(int

x);

int

QueueDelete(intd);

int

QueueOrderAppend(int

x,Graph

//A*算法使用

int

Queue_A_OrderAppend(int

x,Graph

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

void

BroadFirstSearch(Graph

void

DepthFirstSearch(Graph

void

Greedy_Algorithms(Graph

void

AStar_Algorithms(Graph

void

ReSet();

int

GetCount();

int

GetMaxWeight();

int

GetEnd();

way*

GetB();

private:

wayb;

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

void

StackPush(int

x,Graph

void

PrintStack(Graph

int

GetWeight();

private:

int

a[100];

int

top1;

int

weight;

};

//Graph.cpp

#include“Graph.h“#include

#include

using

namespace

std;

Graph::Graph()

{

numofedges

}

Graph::~Graph()

{

}

void

Graph::ReadVertex()

{

int

i=0,v;

char

ch[20];

fstream

infile(“启发式数值.txt“,ios::in);

while

(infile

#endif

V[i].value

V[i].cost

strcpy(V[i].cityname,ch);

i++;

}

void

Graph::ReadEdge()

{

int

valu,i;

fstream

infile(“地图数据表.txt“,ios::in);

while

(infile

valu)

{

edge[i

20][i

20]

valu;

#ifdef

MY_DEBUG

0)cout

20)

{

return

-1;

}

for

(int

col

col0

}

for

(int

col=

col0

front

count

}

SeqQueue::~SeqQueue()

{

}

int

SeqQueue::QueueNotEmpty()

{

(count

0)return

else

return

}

int

SeqQueue::QueueAppend(

int

{

(count>0

rear

(rear

MaxSize;

count++;

return

}

else

{

(G.V[x].value

G.V[queue[position]].value)

{

position++;

}

int

for

front;

rear

(rear

MaxSize;

count++;

return

}

else

{

//队头插入

(G.V[x].value

G.V[x].cost

G.V[queue[position%MaxSize]].value

G.V[queue[position%MaxSize]].cost)

{

position++;

}

int

for

front;

#include

using

namespace

std;

Romania_Trip::Romania_Trip()

{

new

way[100];

end

count

MaxWeight

10000;

for

(size_t

CityName;

string

name

graph.V[end].cityname;

CityName.push_back(name);

while

(1){

for

(int

j0;

i--)

{

cout

“;

}

cout

Level)return;//大于搜索层次时不再深入

level++;

visited[v]

1;//访问该节点

count++;

stack.StackPush(v,graph);

end

stack.GetWeight()

MaxWeight)

{

-1;

end*/

cout

“---路径长度为：“<<

stack.GetWeight()

endl

“---访问节点数为：“<<

count

endl

<<“---搜索层次：“<

isOK

true;

}

else

{

graph.GetFirstVertex(v);//取当前节点的第一个子节点

}

while

-1)

{

(!visited[w])

DepthFirstSearch(graph,w,stack);//递归访问

graph.GetNextVertex(v,w);//取当前节点的下一个子节点

}

visited[v]

0;//返回时置该节点为未访问

stack.StackPop(

graph);//将该节点弹出栈，并根据graph

中weight

的值更改当前栈值

level--;

}

//贪婪算法

void

Romania_Trip::Greedy_Algorithms(Graph

SeqCQuene

queue;//队列存储图节点在图中的索引值,优先队列，value小的在队头

visited[v]

end){

return;

}

queue.QueueOrderAppend(

v,graph);//图节点按优先顺序入队列

count++;

//访问节点数+1

while

(queue.QueueNotEmpty())//宽度优先，循环

{

queue.QueueDelete(

//删除队列头元素并返回删除的数值

//cout

“u=

“<<

““;

graph.GetFirstVertex(u);

while

-1)

{

(!visited[w])

{

Visit(w,u);//访问w节点，将way

的指向更新

end)

{

//cout

“w==end“;

count++;

return;

}

queue.QueueOrderAppend(

w,graph);

//图节点按优先顺序入队列

count++;

}

graph.GetNextVertex(u,w);

}

//A*算法

void

Romania_Trip::AStar_Algorithms(Graph

&graph,int

尘埃飞雀 2022-06-26 20:47:15

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

相关推荐

精选推荐更多>

精选问答