人工智能课程设计报告罗马尼亚度假问题样本.doc

课 程:人工智能课程设计报告
班 级：
姓 名：
学 号：
指引教师:赵曼

11月

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

题目一：罗马利亚度假问题
一. 问题描述
分别用代价一致宽度优先、有限制深度优先（预设搜索层次）、贪婪算法和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
<<"---搜索层次："<<level<<endl;
isOK = true;
}
}
else
{
w = graph.GetFirstVertex(v);//取当前节点第一种子节点
}
while (w != -1)
{
if (!visited[w])
DepthFirstSearch(graph，w，stack);//递归访问
w = graph.GetNextVertex(v，w);//取当前节点下一种子节点

}
visited[v] = 0;//返回时置该节点为未访问
stack.StackPop( graph);//将该节点弹出栈，并依照graph 中weight 值更改当前栈值
level--;
}
3)贪婪算法
//贪婪算法
void Romania_Trip::Greedy_Algorithms(Graph &graph，int v)
{
int u，w;
SeqCQuene queue;//队列存储图节点在图中索引值,优先队列，value小在队头
visited[v] = 1;
if (v == end){ return；}
queue.QueueOrderAppend( v，graph);//图节点按优先顺序入队列
count++； //访问节点数+1
while (queue.QueueNotEmpty())//宽度优先，循环
{
queue.QueueDelete( &u);//删除队列头元素并返回删除数值
//cout << "u= " << u << " ";

w = graph.GetFirstVertex(u);
while (w != -1)
{
if (!visited[w])
{
Visit(w，u);//访问w节点，将way b 指向更新
if (w == end)
{
//cout << "w==end";
count++；
return；
}
queue.QueueOrderAppend( w，graph)；//图节点按优先顺序入队列
count++;
}
w = graph.GetNextVertex(u，w);
}
}
}4)A*算法
//A*算法
void Romania_Trip::AStar_Algorithms(Graph &graph，int v)
{
//i = 0；count = 0;
int u，w;
SeqCQuene queue;
if (v == end) return;//到达终点

queue.Queue_A_OrderAppend(v，graph)；
count++;
while (queue.QueueNotEmpty())
{
queue.QueueDelete( &u);
if (u == end)
{
cout << "---途径长度为：" << graph.GetVerCost(u) + graph.GetVerValue(u) << endl
<< "---访问节点数为：" << count << endl;
return;
}
w = graph.GetFirstVertex( u);
while (w != -1)
{
int cost=graph.GetVerCost(u) + graph.GetEdge(w,u);
graph.SetVerCost(w，cost);//设立当前节点移动到目的节点预估费用
queue.Queue_A_OrderAppend( w，graph);//按预估费用优先入队列
count++;
w = graph.GetNextVertex(u，w);
}
}
}

四.运营成果及分析

分析：

节点数
途径长度
耗时ms
Optimality：
Completeness：
BFS
11
450
16
No
YES
DFS
12
605
31
No
NO
Greedy
8
450
16
NO
NO
A*算法
16
418
0
YES
YES

通过比较，Greedy搜索生成结点数目至少，为8个，效率最高；A*算法生成结点数目最多，为30个，效率最低。DFS（普通）、BFS和Greedy搜索找到都不一定最优解， A*算法具备完备性且始终找到是最优解。宽度优先虽然是完备（如果分支因子有限话），在任何状况下宽度优先都能找到一种解，但是，它找到第一种解并非最优，此外，最坏状况是，当目的结点是第d层最后一种被扩展结点时，它将耗费大量时间。宽度优先时间复杂度：（b为分支因子，d为深度）；空间复杂度为所存储节点个数。DFS不是完备（除非查找空间是有限），同步，它也不能找到最优解。深度优先时间复杂度：；空间复杂度：（b为分支因子，m为深度，仅有一枝需要存储）；。贪婪算法不是完备。同步，它找到解也不一定是最优解。其时间复杂度：（b代表分支数，m为深度）；空间复杂度为）。因此只有A*算法和DFS（回溯+剪枝）是完备，且可以找到最优解；其时间复杂度：扩展节点数目；空间复杂度：所有生成结点。综合来看，BFS和贪婪算法效率较高，但解并非最优，而A*算法效率稍逊色，但解为最优；DFS（回溯+剪枝）搜索虽能找到最优解但效率最低。

源代码
//Graph.h
#pragma once

using namespace std;
#define MaxV 20
/*#ifndef MY_DEBUG
#define MY_DEBUG
#endif*/
typedef struct
{
char cityname[20];//都市名
int value;//权值
int cost;//A*算法中从当前节点移动到目的节点预估费用
}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);
private:

};

//Queue.h
#pragma once
#include<iostream>
#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<iostream>
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<iostream>
#include<stdlib.h>
#include<fstream>
#include<string>
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<<edge[i/20][i%20]<<"\t";
#endif
i++;
}
}

//取与第V个节点第一种邻接点
int Graph::GetFirstVertex(int v)
{
if (v<0 || v >= 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<iostream>
#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<position；i++)
{
queue[(i - 1 + MaxSize) % MaxSize] = queue[i%MaxSize];
}
queue[(i - 1 + MaxSize) % MaxSize] = x;
front = (front - 1 + MaxSize) % MaxSize;
count++;
return 1;
}
}
}

return 0;
}

//A*
int SeqQueue::Queue_A