人工智能课程设计报告

人工智能课程设计报告

学号：20091000608

姓名：王沙沙

班级：191091

指导老师：赵老师

2011年10月14

目录

1．N皇后问题 (1)

需求分析，设计 (1)

设计表示 (1)

运行结果 (2)

用户手册即测试数据 (2)

结论 (5)

主要算法代码 (5)

2罗马尼亚问题 (9)

需求分析，设计 (9)

设计表示，详细设计 (9)

用户手册 (11)

运行结果 (11)

主要算法代码 (12)

3.实习心得 (21)

1 N 皇后问题

1．问题描述、需求分析

在N*N 的棋盘上分布N 个皇后，其中N 个皇后不能在同一行同一列，也

不能出现在同一对角线上，此时N 个皇后不会相互攻击。

程序需能手动输入皇后个数，并分别采用回溯法、爬山法、遗传法得出

皇后的分布情况，输出皇后的位置即棋盘。

2．设计思想

2.1 形式化

N 个皇后的位置可用一个N 维数组表示，如921543……，意思是第一个皇后在第一列的第9行。

2.2 程序模块

CreatIndividual( )函数用于产生一组表示皇后不在同一行也不再同一列的的一位数组，即产生一组互不相等的0~N 之间的整数，便于快速求解。

IsLegal( )函数用于判断新放置的皇后是否合法，在回溯法中用到。 AttackQueenNum( )用于计算整个棋盘的攻击皇后个数，相当于一个评价函数，在爬山法和遗传法中用到；

Find( )回溯法求解函数

ClimbHill( )爬山法求解函数； GA( )遗传算法求解函数；

（1）函数调用关系图如下：

（2）函数接口规格说明：下图中的箭头指向表示为被指向函数所用

2.3 详细设计

a: CreatIndividual(int *A,int QueenNum)：以当时时间为种子循环产生

随机数，为了使得产生的随机数都不想等，设计集合S[N]并初始化为0，表示还没有产生一个皇后，当产生的皇后不在S[N]中即S[N]！=1时将S[n]置为1，接着产生下一个皇后，如此循环便产生一组互不相等的值。 b: IsLegal(int *A,int t)此函数用于判断第t

列的皇后是否合法，即有

没有皇后在同一行、同一列，同一对角线上，并返回true或者false。

c: AttackQueenNum(int *A,int QueenNum)循环调用IsLegal()函数对攻击数进行累加并返回其值，此函数作为棋盘的评价函数。

d: Find(int *A,int k,int QueenNum,long beginTime)回溯法求解，因为

回溯法的每一层都是for循环，所以不能单纯的用break语句进行控制，

因为即使当前层循环停止了，程序还会继续执行上一层的循环，所以将

起始时间作为参数进行传递，以便求出算法执行时间，然后用exit（0）

语句终止程序，所以要将回溯法放在其它两个算法的后面执行。

e: ClimbHill(int *A,int QueenNum)：由于在产生一个棋盘个体的时候所

有的皇后就不在同一行同一列，所以在爬山法中只对棋盘的列进行交

换，这样即使再怎么交换所有的皇后还是不在同一行同一列，但在交换

的时候需要调用AttackQueenNum( )函数进行棋盘的评价，如果交换前

的攻击数大于交换后的攻击数则进行交换，否则与下一列进行交换比

较，如此循环直到找出解。

f: GA( )

3．用户手册

运行程序，输入皇后个数N，各种算法得到的皇后分布情况、耗时自动显示；

4．测试数据及测试结果

分别测试4，20,30,50皇后，测试结果如下：

程序运行结果：

4皇后运行结果

20皇后运行结果如下

30皇后运行结果如下：

50皇后运行结果如下

由于50皇后的棋盘稍大，这里只给出运行时间

结论：根据输入皇后个数递增的运行结果可以看出爬山法的速度是相当快的，在皇后个数比较少时回溯法的速度要快于遗传算法，而当皇后个数比较多时，回溯法的深度搜索明显慢于遗传算法。

主要算法程序代码：

1：bool IsLegal(int *A,int t) //判断第t列的皇后位置是否合法

{

int i;

for (i=0;i

{

if (A[i]==A[t])

return false;

}

if (t>0 && abs(A[t-1]-A[t])==1)

//然后再判断是否与相邻前一列皇后发生冲突

return false;

return true;

}

2：void CreatIndividual(int *A,int QueenNum)

{

int i,x;//在产生随机数时使用

int *s=new int[QueenNum];//集合，用于产生一组皇后位置

for (i=0;i

s[i]=0;

srand((unsigned)time(NULL));//种子

A[0]=rand()%QueenNum;//第一列的皇后可以没有限制的产生，所以先产生s[A[0]]=1;

for (i=1;i

{

do

{

x=rand()%QueenNum;

} while (s[x]==1);

//s[x]==1表示此位置已有皇后，则重新产生新的位置

A[i]=x;

s[A[i]]=1;

}

}

3：void Find(int *A,int k,int QueenNum,long beginTime)

{

int i,j;

if (k==QueenNum )

{

for (i=0;i

{

printf(" ");

for (j=0;j

{

if (A[j]==i) printf("# ");

else printf("O ");

}

printf("\n");

}

long endTime = clock();

//获得结束时间(endTime-beginTime)<10000，单位为毫秒printf("回溯法 %d 皇后耗时： %d ms\n",QueenNum,endTime-beginTime);

exit(0);

}

else

{

for (i=0;i

{

A[k]=i; //对A[k]从0开始进行赋值，下面再判断所赋的值是否合法，合法的话进行下一列皇后位置的赋值

if (IsLegal(A,k))

Find(A,k+1,QueenNum,beginTime);

//当循环结束时仍然找不到则返回一层，A[k]的层数加1

}

}

}

4：int AttackQueenNum(int *A,int QueenNum)

{

int i,CountAttack=0;

if (abs(A[0]-A[1])==1) //判断第一列

CountAttack++;

for (i=1;i

{

if (abs(A[i]-A[i-1])==1) //与前一列是否冲突

CountAttack++;

if (abs(A[i]-A[i+1])==1) //与后一列是否冲突

CountAttack++;

}

if (abs(A[QueenNum-2]-A[QueenNum-1])==1)//判断最后一列

CountAttack++;

return CountAttack;

}

5：void ClimbHill(int *A,int QueenNum)

{

int i,j,temp,Mark,Count,CountAttack; //Mark用于标记交换的位置

int MinCountAttack;//在选取移动方案时使用

int *SaveTry=new int[QueenNum];//存储临时方案，用于比较

CreatIndividual(A,QueenNum);

CountAttack=AttackQueenNum(A,QueenNum);

MinCountAttack=CountAttack;

for (i=0;i

SaveTry[i]=A[i];

while (CountAttack!=0)

{

for (i=0;i

{

Mark=-1;

MinCountAttack=AttackQueenNum(SaveTry,QueenNum);

//在每一列与其他列交换之前MinCountAttack都等于当前的Try的攻击数for (j=0;j

{

if (i!=j) //只与其他列进行交换

{

temp=SaveTry[j];

SaveTry[j]=SaveTry[i];

SaveTry[i]=temp;

Count=AttackQueenNum(SaveTry,QueenNum);

if (Count==0)

{

MinCountAttack=Count;//即为0

Mark=j; //记录交换列的位置

break; //如果攻击数位0直接跳出循环

}

if (Count

{

MinCountAttack=Count;

Mark=j; //记录交换列的位置

}

temp=SaveTry[j]; //再将刚刚交换的位置复原，用于与下一列进行比较，交换两次即达到交换的效果

SaveTry[j]=SaveTry[i];

SaveTry[i]=temp;

}

}

if (MinCountAttack==0) break;

if (Mark!=-1)

{

temp=SaveTry[Mark]; //再将刚刚交换的位置复原，用于与下一列进行比较，交换两次即达到交换的效果

SaveTry[Mark]=SaveTry[i];

SaveTry[i]=temp;

}

}

CountAttack=AttackQueenNum(SaveTry,QueenNum);

}

for (i=0;i

A[i]=SaveTry[i]; //存储存储最终结果

}

2 罗马尼亚问题

1．需求分析：

从文件中读取图和启发函数，分别用Dijkstra、深度优先、广度优先、贪婪算法、A*算法得到从起始点Arad到目标点Bucharest的一条路径，即为罗马

尼亚问题的一个解，在求解的过程中记录扩展节点的个数（用于比较几种算法的

优劣），记录每种算法得到的解，即输出每种解得到的条路径。

2．设计：

2.1 设计思想

对于图的存储采用邻接矩阵进行存储，因为此图节点与边比较多（若比较少则采用邻接表结构，此时效率比较高），采用堆栈和队列等进行路

径的存储，并且在某条路径走到最大深度都没有发现目标节点时具有返

回上一节点的能力（好处：在某条路上找不到时可以进入相邻的一条路

径，并不是单纯的返回：索索失败），为了不重复访问同一个节点（此时

路径会出现环，导致程序循环执行）利用集合的思想，即将访问过的节

点状态置为1没有访问过的置为0，以此来避免路径出现环。

2.2 设计表示

（1）函数调用关系图

2.3 详细设计

a: Dijkstra( ) 设置集合数组Gather[MaxVertices]，按照路径长度递增的顺序逐步产生最短路径，并将起始点到其他节点的距离存放到数组distance[]中，将到每一个节点的最短路径的前一节点存至path[]数组中，从起始节点Arad开始，将其状态标为1，重复执行如下步骤N-1次，直至所有节点的状态都为1.

1）在所有不在集合的顶点中选取选取distance[i]最小的一个顶点，设置为第u个顶点；

2）将选出的终结点序号U并入集合中，即其状态改为1；

3）以u作为新考虑的中间点，修改不在集合中的个顶点的distance[j]值，如果distance[u]+G.edge[u,j]< distance[i]则令distance[i]=distance[u]+

G.edge[u,j]，同时记下此路径，path[j]=u;

在主函数中利用堆栈和path[]数组将起始节点到目标节点的路径找出来（因为寻找路径时是从目标点向前倒推寻找的，所以先将路径入栈，再出栈得到的既是从起始点到目标点的一条路径）。

b: DF_Searth( ) 设置集合数组Gather[MaxVertices]，采用堆栈寻找路径；首先将起始节点入栈，然后执行如下循环：

1）读取栈顶元素，获得栈顶元素的一个邻接点（此节点的状态需是0，即未访问过），在获得邻接顶点的过程中如果发现目标顶点则进栈，退出循环；

2）如果此节点未访问过则进栈，并将其状态标为1；

3）如果找不到邻接点则出栈，执行（1）；

在执行循环的过程中对扩展的节点个数进行计数，并将堆栈中的路径出栈到数组，在主函数中进行输出。

c: BF_Searth( ) 设置集合数组Gather[MaxV ertices]，采用队列寻找路径；首先将起始节点入队列，然后执行如下循环：

1）出队列，并将出队列的节点入栈（用于保存路径）；

2）循环获取此节点的邻接顶点（未访问过的，即状态为0的节点）并入队列，状态标为1，在寻找邻接点的过程中如果发现目标节点则退出循环；

3）将每一次出队列的顶点都进栈保存（用于输出路径）

然后执行寻找路径部分：此处再定义一个堆栈，首先将目标点进栈，设此栈为栈2，先前存储出队列元素的栈设为栈1：

1）栈2出栈；

2）栈1循环出栈，如果出栈的顶点状态为1并且与当前顶点不在图的同一行，即不相邻，那么由栈1出栈的顶点即为栈2出栈顶点的父节点，将此节点入栈2，执行（1）；

最后将栈2中的所有节点出栈即为宽度优先寻找到的一条路径，同样在寻找的过程中记录扩展节点的个数；

d: Greedy_Searth( ) 设置集合数组Gather[MaxV ertices]，采用堆栈，首先将起始节点入栈，执行如下循环：

1）读出栈顶元素（只读，并不进行出栈操作）；

2）循环获取此元素的邻接顶点（即其所有的还未访问过的孩子），利用排序找到启发函数值最小的孩子结点，将此孩子节点入栈，状态标为1，

执行（1）；

3）如果读出的栈顶元素以找不到邻接顶点即孩子，说明此条路径已经走到最大深度处，则出栈（即返回上一层），此时执行（1），因为只对入栈的元

素状态值为1，所以返回上一层的时候寻找出所有的邻接顶点，并找出最

小值，此时的最小值是次小值（因为最小值那条路不通），这样程序便进

入下一条路径的寻找；

e: A_Searth( )设置集合数组Gather[MaxV ertices]，采用堆栈，首先将起始节点入栈，执行如下循环：

1）读取栈顶元素，获取此节点的所有邻接顶点（即所有孩子），选取实际路程g(N)与启发函数值最小的节点入栈，将其状态标为1，在此过程中如果

发现目标顶点则循环结束；

2）如果此条路已走到最大深度处则出栈，寻找下一条路径，执行（1）；

在此函数中定义了一个20*3的数组GHF[MaxVertices][3]用于比较

f(N)=g(N)+h(N)（作业的表相似，执行过程相同）；

f: ReadGraphFile( ) 与ReadHFile( )完成文件的读操作，利用fgetc(fp)函数进行一位一位的读，并将读取的数据转换为整数形式进行存储，以供于其他算法的使用，在循环读取文件的过程中注意文件尾的处理。

3．用户手册

直接运行程序即可得到Dijkstra、深度优先、广度优先、贪婪算法、A*算法得到的解，即根据相应的算法的到从起始节点到目标节点的一条路径。

4．整体运行结果如下：

5．主要算法代码如下：

//Dijkstra算法

void Dijkstra(AdjMGraph G, int v0, int distance[], int path[])

{

int n = G.vertices.size;

int *s = (int *)malloc(sizeof(int)*n); //集合

int minDis, i, j, u;

//初始化

for(i = 0; i < n; i++)

{

distance[i] = G.edge[v0][i];

s[i] = 0;

if(i != v0 && distance[i] < MaxWeight) path[i] = v0;

else path[i] = -1;

}

s[v0] =1;

for(i = 1; i < n; i++)

{

minDis = MaxWeight;

for(j = 0; j < n; j++)

if(s[j] == 0 && distance[j] < minDis)

{

u = j;

minDis = distance[j];

}

if(minDis == MaxWeight) return;

s[u] = 1;

for(j = 0; j < n; j++)

if(s[j] == 0 && G.edge[u][j] < MaxWeight &&

distance[u] + G.edge[u][j] < distance[j])

{

distance[j] = distance[u] + G.edge[u][j];

path[j] = u;

}

}

}

//深度优先搜索

void DF_Searth(AdjMGraph G,int v0,int vg,int path[],int *Expand,int *AnswerWay)

{

int i,x,SumExpand=0;

int Vertex; //用于寻找目标节点

int Gather[MaxVertices];//集合

SeqStack S;

StackInitiate (&S);

for (i=0;i

Gather[i]=0;

StackPush(&S,v0); //首先将起始节点入栈

SumExpand++;

Gather[v0]=1;

while(1)

{

StackTop(S,&x);

Vertex=GetFirstVex(G,x); //获取第一个临接点

while (Gather[Vertex]==1)

{

Vertex=GetNextVex(G,x,Vertex);

}

while (Vertex==-1)//此时未找到下一个临接点

{

StackPop(&S,&x);

StackTop(S,&x);

Vertex=GetFirstVex(G,x);

while (Gather[Vertex]==1)

{

Vertex=GetNextVex(G,x,Vertex);

}

}

StackPush(&S,Vertex);

SumExpand++;

Gather[Vertex]=1;

//同一条路径上那个不允许出现相同的节点，防止转圈if (Vertex==vg) break;

}

*Expand=SumExpand;

*AnswerWay=S.top;

if (S.top==0)

printf("深度优先搜索失败!!!");

else

{

while(StackNotEmpty(S))

{

StackTop(S,&x);

path[S.top-1]=x;

StackPop(&S,&x);

}

}

}

//宽度优先搜索

void BF_Searth(AdjMGraph G,int v0,int vg,int path[],int *Expand,int *AnswerWay)

{

int i,x,y,SumExpand=0;

int Vertex; //用于寻找目标节点

int Gather[MaxVertices];//集合

SeqStack SaveQ,LineSave;

//SaveQ将出队列的节点全部进栈,LineSave用于保存路径,

StackInitiate(&SaveQ);

StackInitiate(&LineSave);

SeqCQueue Q;

QueueInitiate(&Q);

for (i=0;i

Gather[i]=0;

QueueAppend(&Q,v0); //首先将起始节点入队列

SumExpand++;

Gather[v0]=1;

while(1)

{

QueueDelete(&Q,&x);

StackPush(&SaveQ,x); //将每一个出队列的结点进行保存

Vertex=GetFirstVex(G,x); //获取第一个临接点

if (Vertex==vg) break; //此时找到目标节点

if (Vertex==-1)

{

printf("宽度优先搜索失败!!!");

return;

}

while(Vertex!=-1) //将x的所有邻接顶点入队列

{

if (Gather[Vertex]==0) //表示还未扩展

{

QueueAppend(&Q,Vertex);

SumExpand++;

Gather[Vertex]=1;

}

Vertex=GetNextVex(G,x,Vertex);

if (Vertex==vg) break; //此时找到目标节点，截止搜索}

if (Vertex==vg) break; //此语句用于终止外层循环

}

StackPush(&LineSave,Vertex);//此时Vertex为目标节点

StackPush(&LineSave,x); //此时x为Vertex的父节点

StackPop(&SaveQ,&x);

while(StackNotEmpty(SaveQ))

{

StackPop(&SaveQ,&x);

StackTop(LineSave,&y);

if (IsShareFatherEdge(G,x,y)<0 && IsEdge(&G,x,y) && Gather[x]==1)//如果没有相同的父亲,被访问过，并且之间有边则保存路径

StackPush(&LineSave,x);

}

*Expand=SumExpand;

*AnswerWay=LineSave.top;

i=0;

while(StackNotEmpty(LineSave))

{

StackPop(&LineSave,&x);

path[i]=x;

i++;

}

}

//贪婪算法

void Greedy_Searth(AdjMGraph G,int H[],int v0,int vg,int path[],int *Expand,int *AnswerWay)

{

int i,x,SumExpand=0;

int MinWorth,MinX; //MinX用于记录具有最小权值的扩展节点

int Vertex; //用于寻找目标节点

int Gather[MaxVertices];//集合

SeqStack S;

StackInitiate (&S);

for (i=0;i

Gather[i]=0;

StackPush(&S,v0); //首先将起始节点入栈

SumExpand++;

Gather[v0]=1;

while(1)

{

MinWorth=MaxWeight; //MaxWeight=1000表示无穷大

StackTop(S,&x);

Vertex=GetFirstVex(G,x); //获取第一个临接点

if (Vertex==vg)

{

StackPush(&S,Vertex); //将目标节点压栈

Gather[Vertex]=1;

SumExpand++;

break; //此时找到目标节点

}

if (Gather[Vertex]==0 && H[Vertex]

{

MinWorth=H[Vertex];

MinX=Vertex; //记录最小节点

}

if (Vertex!=-1)

{

while (Vertex!=-1)

{

Vertex=GetNextVex(G,x,Vertex);

if (Vertex==-1)

{

StackPush(&S,MinX); //将当前最小节点压栈

Gather[MinX]=1;

SumExpand++;

break;

}

if (Vertex==vg)

{

StackPush(&S,Vertex); //将目标节点压栈

Gather[Vertex]=1;

SumExpand++;

break; //此时找到目标节点

}

if (H[Vertex]

{

MinWorth=H[Vertex];

MinX=Vertex; //记录最小节点

}

}

}

else

{

while (Vertex==-1) //此时未找到下一个临接点,往回退一步

{

StackPop(&S,&x);

}

}

}

*Expand=SumExpand;

*AnswerWay=S.top;

if (S.top==0)

printf("贪婪算法失败!!!");

else

{

while(StackNotEmpty(S))

{

StackTop(S,&x);

path[S.top-1]=x;

StackPop(&S,&x);

}

}

}

//A*算法

void A_Searth(AdjMGraph G,int H[],int v0,int vg,int path[],int *Expand,int *AnswerWay)

{

int i,j,x,SumExpand=0;

int MinF,MinX;//记录最小f(N)与对应的节点，在比较f(N)时使用

int Vertex; //用于寻找目标节点

int Gather[MaxVertices];//集合

int GHF[MaxVertices][3];//分别用于存储g(N) h(N) f(N)

SeqStack S;

StackInitiate (&S);

for (i=0;i

{

Gather[i]=0;

GHF[i][0]=0;

GHF[i][2]=1000; //对f(N)进行初始化，因为在后面要进行比较，所以必须初始化

}

StackPush(&S,v0); //首先将起始节点入栈

GHF[v0][0]=0; //g(N)

GHF[v0][1]=H[v0]; //h(N)

GHF[v0][2]=GHF[v0][0]+GHF[v0][1]; //f(N)=g(N)+h(N)

SumExpand++;

Gather[v0]=1;

i=0;

while(1)

{

MinF=MaxWeight; //MaxWeight=1000表示无穷大

StackTop(S,&x);

Vertex=GetFirstVex(G,x); //获取第一个临接点

if (Vertex==vg)

{

StackPush(&S,Vertex); //将目标节点压栈

Gather[Vertex]=1;

SumExpand++;

break; //此时找到目标节点

}

if (Vertex!=-1)

{

if (Gather[Vertex]==0)

{

GHF[Vertex][0]=G.edge[x][Vertex]+GHF[x][0]; //g(N)

GHF[Vertex][1]=H[Vertex]; //h(N)

GHF[Vertex][2]=GHF[Vertex][0]+GHF[Vertex][1]; //f(N)=g(N)+h(N) if (GHF[Vertex][2]

{

MinF=GHF[Vertex][2];

MinX=Vertex;

}

}

while (Vertex!=-1)

{

Vertex=GetNextVex(G,x,Vertex);

if (Vertex!=-1 && Gather[Vertex]==0)

{

GHF[Vertex][0]=G.edge[x][Vertex]+GHF[x][0]; //g(N)

GHF[Vertex][1]=H[Vertex]; //h(N)

GHF[Vertex][2]=GHF[Vertex][0]+GHF[Vertex][1]; //f(N)=g(N)+h(N) if (GHF[Vertex][2]

{

MinF=GHF[Vertex][2];

MinX=Vertex;

}

}

if (Vertex==-1)

{

StackPush(&S,MinX); //将当前最小节点压栈

Gather[MinX]=1;

SumExpand++;

break;

}

if (Vertex==vg)

{

StackPush(&S,Vertex); //将目标节点压栈

Gather[Vertex]=1;

SumExpand++;