人工智能课程设计报告(八皇后问题与罗马尼亚问题)

人工智能课程设计报告学号：姓名：王沙沙班级：指导老师：赵老师 2011年10月14目录1N皇后问题1 需求分析，设计1 设计表示1运行结果2用户手册即测试数据2结论5主要算法代码52罗马尼亚问题9 需求分析，设计9 设计表示，详细设计9用户手册11 运行结果11 主要算法代码12 3.实习心得211 N皇后问题1问题描述、需求分析 在N*N 的棋盘上分布N个皇后，其中N个皇后不能在同一行同一列，也不能出现在同一对角线上，此时N个皇后不会相互攻击。 程序需能手动输入皇后个数，并分别采用回溯法、爬山法、遗传法得出皇后的分布情况，输出皇后的位置即棋盘。2设计思想2.1 形式化N个皇后的位置可用一个N维数组表示，如，意思是第一个皇后在第一列的第9行。2.2 程序模块CreatIndividual( )函数用于产生一组表示皇后不在同一行也不再同一列的的一位数组，即产生一组互不相等的0N之间的整数，便于快速求解。IsLegal( )函数用于判断新放置的皇后是否合法，在回溯法中用到。AttackQueenNum( )用于计算整个棋盘的攻击皇后个数，相当于一个评价函数，在爬山法和遗传法中用到；Find( )回溯法求解函数ClimbHill( )爬山法求解函数；GA( )遗传算法求解函数；（1）函数调用关系图如下：（2）函数接口规格说明：下图中的箭头指向表示为被指向函数所用CreatIndividual()AttackQueenNum( )Find( )IsLegal( )主函数GA( )ClimbHill( )2.3 详细设计a: CreatIndividual(int *A,int QueenNum)：以当时时间为种子循环产生随机数，为了使得产生的随机数都不想等，设计集合SN并初始化为0，表示还没有产生一个皇后，当产生的皇后不在SN中即SN！=1时将Sn置为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;i0 & abs(At-1-At)=1)/然后再判断是否与相邻前一列皇后发生冲突return false;return true;2：void CreatIndividual(int *A,int QueenNum)int i,x;/在产生随机数时使用int *s=new intQueenNum;/集合，用于产生一组皇后位置for (i=0;iQueenNum;i+)si=0;srand(unsigned)time(NULL);/种子A0=rand()%QueenNum;/第一列的皇后可以没有限制的产生，所以先产生sA0=1;for (i=1;iQueenNum;i+)do x=rand()%QueenNum; while (sx=1);/sx=1表示此位置已有皇后，则重新产生新的位置Ai=x;sAi=1;3：void Find(int *A,int k,int QueenNum,long beginTime)int i,j;if (k=QueenNum )for (i=0;iQueenNum;i+)printf( );for (j=0;jQueenNum;j+)if (Aj=i) printf(# );else printf(O );printf(n);long endTime = clock();/获得结束时间(endTime-beginTime)10000，单位为毫秒printf(回溯法 %d 皇后耗时： %d msn,QueenNum,endTime-beginTime);exit(0);elsefor (i=0;iQueenNum;i+)Ak=i; /对Ak从0开始进行赋值，下面再判断所赋的值是否合法，合法的话进行下一列皇后位置的赋值if (IsLegal(A,k)Find(A,k+1,QueenNum,beginTime); /当循环结束时仍然找不到则返回一层，Ak的层数加14：int AttackQueenNum(int *A,int QueenNum)int i,CountAttack=0;if (abs(A0-A1)=1) /判断第一列CountAttack+;for (i=1;iQueenNum-1;i+) /首先判断前面几列同一行有没有皇后if (abs(Ai-Ai-1)=1) /与前一列是否冲突CountAttack+;if (abs(Ai-Ai+1)=1) /与后一列是否冲突CountAttack+;if (abs(AQueenNum-2-AQueenNum-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 intQueenNum;/存储临时方案，用于比较CreatIndividual(A,QueenNum);CountAttack=AttackQueenNum(A,QueenNum);MinCountAttack=CountAttack;for (i=0;iQueenNum;i+)SaveTryi=Ai;while (CountAttack!=0)for (i=0;iQueenNum & MinCountAttack!=0;i+)Mark=-1;MinCountAttack=AttackQueenNum(SaveTry,QueenNum); /在每一列与其他列交换之前MinCountAttack都等于当前的Try的攻击数for (j=0;jQueenNum & MinCountAttack!=0;j+)if (i!=j) /只与其他列进行交换temp=SaveTryj;SaveTryj=SaveTryi;SaveTryi=temp;Count=AttackQueenNum(SaveTry,QueenNum);if (Count=0)MinCountAttack=Count;/即为0Mark=j; /记录交换列的位置break; /如果攻击数位0直接跳出循环if (CountMinCountAttack)MinCountAttack=Count;Mark=j; /记录交换列的位置temp=SaveTryj; /再将刚刚交换的位置复原，用于与下一列进行比较，交换两次即达到交换的效果SaveTryj=SaveTryi;SaveTryi=temp;if (MinCountAttack=0) break;if (Mark!=-1)temp=SaveTryMark; /再将刚刚交换的位置复原，用于与下一列进行比较，交换两次即达到交换的效果SaveTryMark=SaveTryi;SaveTryi=temp;CountAttack=AttackQueenNum(SaveTry,QueenNum);for (i=0;iQueenNum;i+)Ai=SaveTryi; /存储存储最终结果2 罗马尼亚问题1 需求分析：从文件中读取图和启发函数，分别用Dijkstra、深度优先、广度优先、贪婪算法、A*算法得到从起始点Arad到目标点Bucharest的一条路径，即为罗马尼亚问题的一个解，在求解的过程中记录扩展节点的个数（用于比较几种算法的优劣），记录每种算法得到的解，即输出每种解得到的条路径。 2 设计：2.1 设计思想对于图的存储采用邻接矩阵进行存储，因为此图节点与边比较多（若比较少则采用邻接表结构，此时效率比较高），采用堆栈和队列等进行路径的存储，并且在某条路径走到最大深度都没有发现目标节点时具有返回上一节点的能力（好处：在某条路上找不到时可以进入相邻的一条路径，并不是单纯的返回：索索失败），为了不重复访问同一个节点（此时路径会出现环，导致程序循环执行）利用集合的思想，即将访问过的节点状态置为1没有访问过的置为0，以此来避免路径出现环。2.2 设计表示（1）函数调用关系图ReadGraphFile( )Greedy_Searth( )BF_Searth( )DF_Searth( )ReadHFile( )A_Searth( )Dijkstra( )主函数2.3 详细设计 a: Dijkstra( ) 设置集合数组GatherMaxVertices，按照路径长度递增的顺序逐步产生最短路径，并将起始点到其他节点的距离存放到数组distance中，将到每一个节点的最短路径的前一节点存至path数组中，从起始节点Arad开始，将其状态标为1，重复执行如下步骤N-1次，直至所有节点的状态都为1.1） 在所有不在集合的顶点中选取选取distancei最小的一个顶点，设置为第u个顶点；2） 将选出的终结点序号U并入集合中，即其状态改为1；3） 以u作为新考虑的中间点，修改不在集合中的个顶点的distancej值，如果distanceu+G.edgeu,j distancei则令distancei=distanceu+ G.edgeu,j，同时记下此路径，pathj=u; 在主函数中利用堆栈和path数组将起始节点到目标节点的路径找出来（因为寻找路径时是从目标点向前倒推寻找的，所以先将路径入栈，再出栈得到的既是从起始点到目标点的一条路径）。b: DF_Searth( ) 设置集合数组GatherMaxVertices，采用堆栈寻找路径；首先将起始节点入栈，然后执行如下循环：1） 读取栈顶元素，获得栈顶元素的一个邻接点（此节点的状态需是0，即未访问过），在获得邻接顶点的过程中如果发现目标顶点则进栈，退出循环；2） 如果此节点未访问过则进栈，并将其状态标为1；3） 如果找不到邻接点则出栈，执行（1）；在执行循环的过程中对扩展的节点个数进行计数，并将堆栈中的路径出栈到数组，在主函数中进行输出。c: BF_Searth( ) 设置集合数组GatherMaxVertices，采用队列寻找路径；首先将起始节点入队列，然后执行如下循环：1） 出队列，并将出队列的节点入栈（用于保存路径）；2）循环获取此节点的邻接顶点（未访问过的，即状态为0的节点）并入队列，状态标为1，在寻找邻接点的过程中如果发现目标节点则退出循环； 3）将每一次出队列的顶点都进栈保存（用于输出路径） 然后执行寻找路径部分：此处再定义一个堆栈，首先将目标点进栈，设此栈为栈2，先前存储出队列元素的栈设为栈1：1） 栈2出栈；2） 栈1循环出栈，如果出栈的顶点状态为1并且与当前顶点不在图的同一行，即不相邻，那么由栈1出栈的顶点即为栈2出栈顶点的父节点，将此节点入栈2，执行（1）； 最后将栈2中的所有节点出栈即为宽度优先寻找到的一条路径，同样在寻找的过程中记录扩展节点的个数；d: Greedy_Searth( ) 设置集合数组GatherMaxVertices，采用堆栈，首先将起始节点入栈，执行如下循环：1） 读出栈顶元素（只读，并不进行出栈操作）；2） 循环获取此元素的邻接顶点（即其所有的还未访问过的孩子），利用排序找到启发函数值最小的孩子结点，将此孩子节点入栈，状态标为1，执行（1）；3） 如果读出的栈顶元素以找不到邻接顶点即孩子，说明此条路径已经走到最大深度处，则出栈（即返回上一层），此时执行（1），因为只对入栈的元素状态值为1，所以返回上一层的时候寻找出所有的邻接顶点，并找出最小值，此时的最小值是次小值（因为最小值那条路不通），这样程序便进入下一条路径的寻找；e: A_Searth( )设置集合数组GatherMaxVertices，采用堆栈，首先将起始节点入栈，执行如下循环：1） 读取栈顶元素，获取此节点的所有邻接顶点（即所有孩子），选取实际路程g(N)与启发函数值最小的节点入栈，将其状态标为1，在此过程中如果发现目标顶点则循环结束；2） 如果此条路已走到最大深度处则出栈，寻找下一条路径，执行（1）； 在此函数中定义了一个20*3的数组GHFMaxVertices3用于比较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+)distancei = G.edgev0i;si = 0;if(i != v0 & distancei MaxWeight) pathi = v0;else pathi = -1;sv0 =1;for(i = 1; i n; i+)minDis = MaxWeight;for(j = 0; j n; j+)if(sj = 0 & distancej minDis)u = j;minDis = distancej;if(minDis = MaxWeight) return;su = 1;for(j = 0; j n; j+)if(sj = 0 & G.edgeuj MaxWeight &distanceu + G.edgeuj distancej)distancej = distanceu + G.edgeuj;pathj = u;/深度优先搜索void DF_Searth(AdjMGraph G,int v0,int vg,int path,int *Expand,int *AnswerWay) int i,x,SumExpand=0;int Vertex; /用于寻找目标节点int GatherMaxVertices;/集合SeqStack S;StackInitiate (&S);for (i=0;iMaxVertices;i+)Gatheri=0;StackPush(&S,v0); /首先将起始节点入栈 SumExpand+;Gatherv0=1;while(1)StackTop(S,&x);Vertex=GetFirstVex(G,x); /获取第一个临接点while (GatherVertex=1)Vertex=GetNextVex(G,x,Vertex);while (Vertex=-1)/此时未找到下一个临接点StackPop(&S,&x);StackTop(S,&x); Vertex=GetFirstVex(G,x);while (GatherVertex=1)Vertex=GetNextVex(G,x,Vertex);StackPush(&S,Vertex);SumExpand+;GatherVertex=1;/同一条路径上那个不允许出现相同的节点，防止转圈if (Vertex=vg) break;*Expand=SumExpand;*AnswerWay=S.top;if (S.top=0)printf(深度优先搜索失败!);elsewhile(StackNotEmpty(S)StackTop(S,&x);pathS.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 GatherMaxVertices;/集合SeqStack SaveQ,LineSave; /SaveQ将出队列的节点全部进栈,LineSave用于保存路径,StackInitiate(&SaveQ);StackInitiate(&LineSave);SeqCQueue Q;QueueInitiate(&Q);for (i=0;iMaxVertices;i+)Gatheri=0;QueueAppend(&Q,v0); /首先将起始节点入队列SumExpand+;Gatherv0=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 (GatherVertex=0) /表示还未扩展QueueAppend(&Q,Vertex);SumExpand+;GatherVertex=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) & Gatherx=1)/如果没有相同的父亲,被访问过，并且之间有边则保存路径StackPush(&LineSave,x);*Expand=SumExpand;*AnswerWay=LineSave.top;i=0;while(StackNotEmpty(LineSave)StackPop(&LineSave,&x);pathi=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 GatherMaxVertices;/集合SeqStack S;StackInitiate (&S);for (i=0;iMaxVertices;i+)Gatheri=0;StackPush(&S,v0); /首先将起始节点入栈 SumExpand+;Gatherv0=1;while(1)MinWorth=MaxWeight; /MaxWeight=1000表示无穷大StackTop(S,&x);Vertex=GetFirstVex(G,x); /获取第一个临接点if (Vertex=vg)StackPush(&S,Vertex); /将目标节点压栈GatherVertex=1;SumExpand+;break; /此时找到目标节点if (GatherVertex=0 & HVertexMinWorth)MinWorth=HVertex;MinX=Vertex; /记录最小节点if (Vertex!=-1)while (Vertex!=-1)Vertex=GetNextVex(G,x,Vertex);if (Vertex=-1)StackPush(&S,MinX); /将当前最小节点压栈GatherMinX=1;SumExpand+;break;if (Vertex=vg)StackPush(&S,Vertex); /将目标节点压栈GatherVertex=1;SumExpand+;break; /此时找到目标节点if (HVertexMinWorth)MinWorth=HVertex;MinX=Vertex; /记录最小节点elsewhile (Vertex=-1) /此时未找到下一个临接点,往回退一步StackPop(&S,&x);*Expand=SumExpand;*AnswerWay=S.top;if (S.top=0)printf(贪婪算法失败!);elsewhile(StackNotEmpty(S)StackTop(S,&x);pathS.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 GatherMaxVertices;/集合int GHFMaxVertices3;/分别用于存储g(N) h(N) f(N)SeqStack S;StackInitiate (&S);for (i=0;iMaxVertices;i+)Gatheri=0;GHFi0=0;GHFi2=1000; /对f(N)进行初始化，因为在后面要进行比较，所以必须初始化StackPush(&S,v0); /首先将起始节点入栈 GHFv00=0; /g(N) GHFv01=Hv0; /h(N)GHFv02=GHFv00+GHFv01; /f(N)=g(N)+h(N)SumExpand+;Gatherv0=1;i=0;while(1)MinF=MaxWeight; /MaxWeight=1000表示无穷大StackTop(S,&x);Vertex=GetFirstVex(G,x); /获取第一个临接点if (Vertex=vg)StackPush(&S,Vertex); /将目标节点压栈GatherVertex=1;SumExpand+;break; /此时找到目标节点if (Vertex!=-1)if (GatherVertex=0)GHFVertex0=G.edgexVertex+GHFx0; /g(N) GHFVertex1=HVertex; /h(N) GHFVertex2=GHFVertex0+GHFVertex1; /f(N)=g(N)+h(N)if (GHFVertex2MinF)MinF=GHFVertex2;MinX=Vertex;while (Vertex!=-1)Vertex=GetNextVex(G,x,Vertex);if (Vertex!=-1 & GatherVertex=0)GHFVertex0=G.edgexVertex+GHFx0; /g(N) GHFVertex1=HVertex; /h(N) GHFVertex2=GHFVertex0+GHFVertex1; /f(N)=g(N)+h(N)if (GHFVertex2MinF)MinF=GHFVertex2;MinX=Vertex;if (Vertex=-1)StackPush(&S,MinX); /将当前最小节点压栈GatherMinX=1;SumExpand+;break;if (Vertex=vg)StackPush(&S,Vertex); /将目标节点压栈GatherVertex=1;SumExpand+;break; /此时找到目标节点elsewhile (Vertex=-1) /此时未找到下一个临接点,往回退一步StackPop(&S,&x);*Expand=SumExpand;*AnswerWay=S.top;if (S.top=0)printf(贪婪算法失败!);elsewhile(StackNotEmpty(S)StackTop(S,&x);pathS.top-1=x;StackPop(&S,&x);void ReadGraphFile(FILE *fp,AdjMGraph *g1,int n,int e)int i,