人工智能课程报告--分别用宽度优先、深度优先、贪婪算法和A_算法求解“罗马利亚度假问题” 本文关键词：算法，优先，罗马，求解，人工智能
人工智能课程报告--分别用宽度优先、深度优先、贪婪算法和A_算法求解“罗马利亚度假问题” 本文简介：人工智能课程报告课程:人工智能实验报告班级:191121班学号:20121004362学生姓名:李华勇指导教师:赵曼2014年11月目录一、罗马利亚度假问题31.问题描述32.数据结构42.1广度优先算法42.2深度优先算法42.3贪婪算法42.4A*算法43.算法思想53.1广度优先搜索算法53.
人工智能课程报告--分别用宽度优先、深度优先、贪婪算法和A_算法求解“罗马利亚度假问题” 本文内容：
人工智能课程报告
课
程:
人工智能实验报告
班
级:
191121班
学
号:
20121004362
学生姓名:
李
华
勇
指导教师:
赵
曼
2014年11月
目录
一、罗马利亚度假问题3
1.
问题描述3
2.
数据结构4
2.1
广度优先算法4
2.2
深度优先算法4
2.3
贪婪算法4
2.4
A*算法4
3.
算法思想5
3.1
广度优先搜索算法5
3.2
深度优先搜索算法5
3.3
贪婪算法6
3.4
A*算法6
4.
运行结果7
5.
比较讨论8
6.
主要代码8
二、N皇后问题13
1.问题描述13
2.数据结构13
2.1
回溯法（递归）13
2.2
GA算法13
2.3
CSP的最小冲突法13
3.算法思想14
3.1
回溯法（递归）14
3.2
CSP的最小冲突法14
3.3
GA算法15
4.运行结果16
5.比较讨论17
6.主要代码18
一、罗马利亚度假问题
题目：
分别用宽度优先、深度优先、贪婪算法和A*算法求解“罗马利亚度假问题”。
要求：
分别用文件存储地图和启发函数表，用生成节点数比较几种算法在问题求解时的效率，并列表给出结果。
1.
问题描述
从文件中读取图和启发函数，分别用广度优先、深度优先、贪婪算法、A*算法得到从起始点Arad到目标点Bucharest的一条路径，即为罗马尼亚问题的一个解。在求解的过程中记录生成扩展节点的个数（用于比较几种算法的优劣），用堆栈记录DepthFSearch和BroadFSearch的路径。
2.
数据结构
分别使用了图结构，顺序队列，顺序表以及堆栈。对于每一个图中的结点，定义了一个结构体HeuristicG，结构体中包含结点的名称以及对应的启发函数值。
typedef
struct{
char
G[20];
int
value;
}HeuristicG;
typedef
struct
//图结构：
typedef
struct
//链表
{
{
SeqList
Vertices;
string
list[20];
int
edge[20][20];
int
size;
int
numedge;
}SeqList;
}AdjMGraph;
typedef
struct
//队列
typedef
struct
//栈
{int
queue[20];
{
int
rear;
int
stack[20];
int
front;
int
top;
int
count;
}SeqStack;
}SeqCQueue;
2.1
广度优先算法
使用了数据结构中的图、队列和堆栈。
2.2
深度优先算法
使用了数据结构中的图和堆栈。
2.3
贪婪算法
使用了数据结构中的图。
2.4
A*算法
使用了数据结构中的图。
3.
算法思想
3.1
广度优先搜索算法
void
BF_Search(AdjMGraph
G,HeuristicG
data[],int
v0,int
vg,intExpand,int
count,int
visited[],int
BFS_path[])
v0---起始节点
vg---目标节点
Expand---返回扩展结点数
count---返回路径结点数
BFS_path[]---存储路径信息
G、data[]---用来读取图的各种信息
visited[]---用来存储节点是否已经被访问的信息
广度优先搜索是分层搜索的过程，广度优先搜索算法思想是用一个队列来保存访问过的顶点的顺序，以便按顺序访问这些顶点的邻接顶点，并把这些邻接顶点依次入栈。在函数中我还创建了两个栈，SeqStack
SaveQ，LineSave，SaveQ将出队列的节点全部进栈，LineSave用于保存路径。广度优先搜索算法如下：
1）
访问顶点v0并标记v0已被访问，把v0输出到屏幕。
2）
顶点v0入队列。
3）
若队列非空，则继续执行，否则算法结束。
4）
出队列取得队头顶点u，并把u入SaveQ栈。
5）
查找顶点u的第一个邻接顶点w。
6）
如果w
=
vg，即找到目标节点，算法结束。
7）
若顶点u的邻接顶点w不存在，则转到步骤3），否则循环执行：
（a）若顶点w尚未被访问，则访问顶点w并标记w为已访问；
（b）顶点w入队列，Expand++；
（c）查找顶点u的w邻接顶点后的下一个邻接顶点w，转到步骤7）。
广度优先搜索起始节点到目标节点的路径的算法是：
1）
把顶点vg以及vg的父节点u入栈。
2）
把SaveQ栈顶元素出栈到u，当SaveQ非空是执行以下步骤：
（a）把SaveQ栈顶元素出栈到u
。
（b）取LineSave栈顶元素给y。
（c）如果u和y没有相同的父亲，没被访问过，并且之间有边则保存路
径，把u压入LineSave栈。
3.2
深度优先搜索算法
void
DF_Search(AdjMGraph
G,SeqStack
S,HeuristicG
data[],int
Expand,int
v0,int
vg,int
visited[])
v0---起始节点
vg---目标节点
Expand---返回扩展结点数
SeqStack
S---用堆栈存储路径信息
visited[]---存储路径是否被访问的信息
G、data[]---用来读取图的各种信息
深度优先搜索的算法思想是用栈来保存已经访问过的节点，递归找该节点的第一个邻接顶点并把把顶点入栈，直到找不到顶点的邻接顶点为止，然后回溯，找该顶点父顶点的下一个邻接顶点。
使用深度优先搜索算法，每次都在访问完当前顶点后首先访问当前顶点的第一个邻接顶点。深度优先搜索算法如下：
1)
访问顶点v并标记顶点v为以访问，把v0压入栈S，并在屏幕上输出v。
2)
如果v0！=
-1，查找顶点v的第一个邻接顶点w
3)
若顶点v的邻接顶点w存在且为被访问，则继续执行，否则算法结束。
4)
若果w
=
vg，即找到目标节点，算法结束。
5)
弹出S栈顶元素。
6)
查找顶点v的w邻接顶点的下一个邻接顶点w，转到步骤3）。
3.3
贪婪算法
void
Greedy_Search(AdjMGraph
G,HeuristicG
data[],int
v0,int
vg,intExpand,int
visited[])
v0---起始节点
vg---目标节点
Expand---返回扩展结点数
G、data[]---用来读取图的各种信息
贪心算法思想是找到当前顶点的所有邻接顶点中h（x）值最小的邻接顶点，并把该顶点设置为下一个起始节点，递归直到找到目标节点。算法如下：
1）
访问v0，并将v0设为以访问，把v0输出到屏幕。
2）
如果v0
=
vg，即找到目标节点，算法结束。
3）
找到v0的所有邻接顶点，并比较邻接顶点的h（x）值，把h（x）最小
的邻接顶点w，把w设置为起始顶点v0，转到步骤1）。
3.4
A*算法
void
A_Search(AdjMGraph
G,HeuristicG
data[],int
v0,int
vg,int
distance,intExpand,int
visited[])
v0---起始节点
vg---目标节点
distance---用来保存已经过路径值
Expand---返回扩展结点数
G、data[]---用来读取图的各种信息
A*算法思想是找到起始节点v0的所有邻接顶点，比较所有邻接顶点的fx值（fx
=
到v0已经经过路径值+v0到邻接顶点w的边的路径值distance+邻接顶点w的hx值），找到fx最小的邻接顶点w作为下一个起始顶点v0，同时更新距离diatance
=
diatance
+
v0到w边的路径值，直到找到目标节点。算法如下：
1）访问v0，并将v0设为以访问，把v0输出到屏幕。
2）如果v0
=
vg，即找到目标节点，算法结束。
3）找到v0的所有邻接顶点w，并比较所有邻接顶点的fx值，
fx=ditance+v0到w的距离+w的启发函数值，找到fx最小的邻接顶点w
令v0
=
w，更新distance
=
distance
+
edge[v0][w]，转到步骤1）。
4.
运行结果
深度优先搜索
宽度优先搜索
A*算法
贪婪算法
扩展节点数
12
11
5
4
路径节点数
5
4
5
4
5.
比较讨论
从运行结果中可以看出，在搜索的过程中：
DFS算法扩展结点数为12
BFS算法扩展结点数为11
A*算法扩展结点数为5
贪婪算法扩展结点数为4
所以在求解该问题时，贪婪算法的效率最高，其次是A*算法，然后是BFS算法，最后是DFS算法。但是贪婪算法和A*算法生成的节点数依赖于启发函数的值，因此虽然对于本题来说贪婪算法和A*算法的效率很高，但是不能说在所有搜索问题中贪婪算法和A*算法的效率都是最高的。
6.
主要代码
1）深度优先搜索
//
v0---起始节点
vg---目标节点
//
//
Expand---返回扩展结点数
//
//
SeqStack
S---用堆栈存储路径信息
//
//
visited[]---存储路径访问信息
//
//
G、data[]---用来读取图的各种信
//
void
DF_Search(AdjMGraph
G,SeqStack
S,HeuristicG
data[],int
Expand,int
v0,int
vg,int
visited[])
{
int
t,w;
//用于寻找目标节点
static
int
flag
=
0;
static
int
DFS_flag
=
0;
//标志位---找到目标节点后退出递归
StackPush(S,v0);
//首先将起始节点入栈
flag++;
printf(“%s-->
“,data[v0].G);
visited[v0]=1;
if(v0
!=
-1)
w=GetFirstVex(G,v0,visited);
//获取第一个临接点
while(!DFS_flagExpand
=
flag;
break;
}
if(!
visited[w]
if(DFS_flag)
break;
StackPop(S,w
=
GetNextVex(G,v0,w,visited);
}
}
2）宽度优先搜索
//
v0---起始节点
vg---目标节点
//
//
Expand---返回扩展结点数
//
//
count---返回路径结点数
//
//
BFS_path[]---存储路径信息
//
//
G、data[]---用来读取图的各种信息
//
void
BF_Search(AdjMGraph
G,HeuristicG
data[],int
v0,int
vg,intExpand,int
count,int
visited[],int
BFS_path[])
{
int
u,w,y,SumExpand=1,i=0;
SeqCQueue
Q;
SeqStack
SaveQ,LineSave;
//SaveQ将出队列的节点全部进栈,LineSave用于保存路径
StackInitiate(
StackInitiate(
printf(“%s-->
“,data[v0].G);
visited[v0]=1;
QueueInitiate(
QueueAppend(
//首先将起始节点入队列
while(QueenNotEmpty(Q))
{
QueueDelete(
StackPush(
//将每一个出队列的结点进行保存
w
=
GetFirstVex(G,u,visited);
if(w
==
vg)
{
SumExpand++;Expand
=
SumExpand;
break;
}
while(w
!=
-1)
{
if(
!visited[w])
{
printf(“%s-->
“,data[w].G);
visited[w]
=
1;
QueueAppend(
SumExpand++;
}
w
=
GetNextVex(G,u,w,visited);
}
}
StackPush(//此时w为目标节点
StackPush(
//此时u为w的父节点
StackPop(
while(StackNotEmpty(SaveQ))
{
StackPop(
StackTop(LineSave,if
(
Edge(G,u,y)==1
}
while(StackNotEmpty(LineSave))
{
StackPop(
BFS_path[i++]=u;
count
=
i;
}
}
3）A*
搜索
//
v0---起始节点
vg---目标节点
//
//
distance---用来保存已经过路径值
//
//
Expand---返回扩展结点数
//
//
G、data[]---用来读取图的各种信息
//
void
A_Search(AdjMGraph
G,HeuristicG
data[],int
v0,int
vg,int
distance,intExpand,int
visited[])
{
int
i,u,temp=10000;
static
int
path_num
=
0;
static
int
A_Search_flag
=
0;
//标志位---找到目标节点后退出递归
static
int
fx
=
0;
if(v0
==
2)
printf(“%s“,data[v0].G);
else
printf(“%s-->“,data[v0].G);
visited[v0]
=
1;
path_num++;
if(v0
==
vg)
{
A_Search_flag
=
1;Expand
=
path_num;
return;
}
for(i=0;i“,data[v0].G);
visited[v0]
=
1;
path_num++;
if(v0
==
vg)
{
G_Search_flag
=
1;Expand
=
path_num;
return;
}
for(i=0;i30时，回溯法已经很难找到解，运行时超过了20s。
当N>50时，GA算法运行时间开始逐渐变长，当N>90时运行时间已经超过了60s。
当N=200时，CSP的最小冲突法时间才仅为7.699s。
对比可知当N较大时，CSP的最小冲突法的效率最高，GA算法次之，回溯法在求解大的皇后数是效率最低。
对于回溯法的时间复杂度，最好情况是O(n^2)，最坏情况是O(n!)。
对于CSP的最小冲突法的时间复杂度，最好的情况是O(n^3)，最坏的情况是O（m*n^3）。
对于GA算法的时间复杂度，最好情况是O(n^3)，最坏的情况是O（p*n^3）。
6.主要代码
1、回溯法：
void
backtrack(int
column)
//以列作为判断点
{
int
row,i,j;
double
secs,ms;
BK_stop
=clock();
ms
=
(double)(BK_stop
-
BK_start);
if(ms>20000)
//回溯法运行超过20s就退出
{
printf(“BackT_Queen
Calculations
took
more
than
20
seconds
!/n“);
exit(0);
}
if
(
column==BK_Q_num)
{
BK_end
=
clock
()
;
secs
=
(double)(BK_end
-
BK_start)
/
CLOCKS_PER_SEC
;
printf(“Back_Queen
Calculations
took
%.3lf
second%s./n“,secs,(secs
eachFitness[i]
eachFitness[worst])
worst
=
i
;
if(p->eachFitness[worst]
==
GA_Q_num-1)
return;
baby
=p
;
for
(i
=
0
;
i
p->unitFitness
||
(double)rand()
/
RAND_MAX
slice)
{
selection
=
i;
break;
}
}
return
selection;
}
//
杂交
father,mother，
产生的子代保存在
baby中
void
CrossOverFM
(Population
father,Population
mother,Populationbaby)
{
int
flag[MAX_QUEENS]
;
int
pos1,pos2,tmp
;
int
i,j
;
//
随机产生两个基因断点
do
{
pos1
=
rand()
%
GA_Q_num
;
pos2
=
rand()
%
GA_Q_num
;
}
while
(pos1
==
pos2)
;
if
(pos1
>
pos2)
{
tmp
=
pos1
;
pos1
=
pos2
;
pos2
=
tmp;
}
for
(j
=
0
;
j
pos2)
{
while
(flag[mother.queen[j]])
j++
;
//保证每个皇后都不在同一行
baby->queen[i]
=
mother.queen[j]
;
j
++
;
}
else
baby->queen[i]
=
father.queen[i]
;
}
UpdateFitnessScore
(baby)
;
}
//
杂交产生子代
void
CrossOver
()
{
int
i
;
int
father,mother
;
Population
p[30
+
MAX_QUEENS
/
10]
;
int
count
;
//
计算总共的
Fitness，
用于轮盘赌局规则时候的选择
m_totFitness
=
0
;
for
(i
=
0
;
i
<
m_size
;
i++)
m_totFitness
+=
m_population[i].unitFitness
;
for
(count
=
0
;
count
<
m_size
-
2
;
count++)
{
father
=
RouletteWheelSelection
()
;
mother
=
RouletteWheelSelection
()
;
CrossOverFM
(m_population[father],m_population[mother],//
杂交,后代保存
}
//
将结果覆盖回原种群，加上原种群中适应度最高的两个个体组成新的进化后的种群
for
(count
=
0
;
count
<
m_size
-
2
;
count++)
m_population[count+2]
=
p[count]
;
}
31