人工智能课程报告--分别用宽度优先、深度优先、贪婪算法和A_算法求解“罗马利亚度假问题”

时间：2021-02-28 12:05:13 来源：蒲公英阅读网 本文已影响人

相关热词搜索：算法 优先 罗马

人工智能课程报告--分别用宽度优先、深度优先、贪婪算法和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