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

人工智能课程报告课 程: 人工智能实验报告 班 级: 191121班 学 号: 20121004362 学生姓名: 李 华 勇 指导教师: 赵 曼 2014年11月目录一、罗马利亚度假问题31. 问题描述32. 数据结构42.1 广度优先算法42.2 深度优先算法42.3 贪婪算法42.4 a*算法43. 算法思想53.1 广度优先搜索算法53.2 深度优先搜索算法53.3 贪婪算法63.4 a*算法64. 运行结果75. 比较讨论86. 主要代码8二、n皇后问题131.问题描述132.数据结构132.1 回溯法（递归）132.2 ga算法132.3 csp的最小冲突法133.算法思想143.1 回溯法（递归）143.2 csp的最小冲突法143.3 ga算法154.运行结果165.比较讨论176.主要代码18一、罗马利亚度假问题题目： 分别用宽度优先、深度优先、贪婪算法和a*算法求解“罗马利亚度假问题”。要求： 分别用文件存储地图和启发函数表，用生成节点数比较几种算法在问题求解时的效率，并列表给出结果。1. 问题描述 从文件中读取图和启发函数，分别用广度优先、深度优先、贪婪算法、a*算法得到从起始点arad到目标点bucharest的一条路径，即为罗马尼亚问题的一个解。在求解的过程中记录生成扩展节点的个数（用于比较几种算法的优劣），用堆栈记录depthfsearch和broadfsearch的路径。2. 数据结构 分别使用了图结构，顺序队列，顺序表以及堆栈。对于每一个图中的结点，定义了一个结构体heuristicg，结构体中包含结点的名称以及对应的启发函数值。 typedef struct char g20; int value; heuristicg;typedef struct /图结构： typedef struct /链表 seqlist vertices; string list20;int edge2020; int size;int numedge; seqlist;adjmgraph;typedef struct /队列 typedef struct /栈int queue20; int rear; int stack20;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, int *expand, 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, int *expand, 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, int *expand, 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 + edgev0w，转到步骤1）。 4. 运行结果深度优先搜索宽度优先搜索 a*算法 贪婪算法 扩展节点数121154 路径节点数54545. 比较讨论从运行结果中可以看出，在搜索的过程中：dfs算法扩展结点数为12bfs算法扩展结点数为11a*算法扩展结点数为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- ,datav0.g);visitedv0=1; if(v0 != -1) w=getfirstvex(g,v0,visited); /获取第一个临接点 while(!dfs_flag & w != -1) if(w = vg)dfs_flag = 1;*expand = flag;break;if(! visitedw & w != vg & dfs_flag = 0)df_search(g, s, data, expand, w, vg, visited);if(dfs_flag) break; stackpop(s, &t); 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, int *expand, int * count, int visited, int bfs_path)int u,w,y,sumexpand=1, i=0;seqcqueue q;seqstack saveq,linesave; /saveq将出队列的节点全部进栈,linesave用于保存路径stackinitiate(&saveq);stackinitiate(&linesave);printf(%s- ,datav0.g);visitedv0=1;queueinitiate(&q);queueappend(&q,v0); /首先将起始节点入队列 while(queennotempty(q)queuedelete(&q,&u); stackpush(&saveq,u); /将每一个出队列的结点进行保存w = getfirstvex(g, u, visited);if(w = vg)sumexpand+;*expand = sumexpand;break;while(w != -1)if( !visitedw) printf(%s- ,dataw.g);visitedw = 1;queueappend(&q,w);sumexpand+;w = getnextvex(g, u, w, visited);stackpush(&linesave,w);/此时w为目标节点stackpush(&linesave,u); /此时u为w的父节点stackpop(&saveq,&u);while(stacknotempty(saveq)stackpop(&saveq,&u);stacktop(linesave,&y);if ( edge(g,u,y)=1 & visitedu=1)/如果没有相同的父亲,被访问过，并且之间有边则保存路径stackpush(&linesave,u);while(stacknotempty(linesave)stackpop(&linesave,&u);bfs_pathi+=u; * count = i;3）a* 搜索 / v0-起始节点 vg-目标节点 / distance-用来保存已经过路径值 / expand-返回扩展结点数 / g、data-用来读取图的各种信息 /void a_search(adjmgraph g, heuristicg data, int v0, int vg, int distance, int *expand, 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,datav0.g); else printf(%s-,datav0.g);visitedv0 = 1;path_num+;if(v0 = vg) a_search_flag = 1;*expand = path_num;return;for(i=0;i20;i+)if(edge(g, v0, i) & visitedi = 0 & a_search_flag = 0)fx = distance+datai.value+g.edgev0i;if(fx ,datav0.g);visitedv0 = 1;path_num+; if(v0 = vg) g_search_flag = 1;*expand = path_num;return;for(i=0;i20;i+)if(edge(g, v0, i) & visitedi = 0 & g_search_flag = 0 & datai.value 30时，回溯法已经很难找到解，运行时超过了20s。当n50时，ga算法运行时间开始逐渐变长，当n90时运行时间已经超过了60s。当n=200时，csp的最小冲突法时间才仅为7.699s。对比可知当n较大时，csp的最小冲突法的效率最高，ga算法次之，回溯法在求解大的皇后数是效率最低。对于回溯法的时间复杂度，最好情况是o(n2)，最坏情况是o(n!)。对于csp的最小冲突法的时间复杂度，最好的情况是o(n3)，最坏的情况是o（m*n3）。对于ga算法的时间复杂度，最好情况是o(n3)，最坏的情况是o（p*n3）。 6.主要代码1、回溯法：void backtrack(int column) /以列作为判断点 int row,i,j;double secs, ms;bk_stop =clock();ms = (double)(bk_stop - bk_start);if(ms20000) /回溯法运行超过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 1 ? : s);exit(0); else/放置第column列上的皇后，从第一行开始试探放置 for (row=0;rowbk_q_num;row+)queencolumn = row;if ( issafe(queen,column)backtrack(column+1); /该点安全，向第column列递归2、 csp的最小冲突法：void min_conflict_queens () int i, j,min;mf_queens temp; /从第一列开始寻找该列冲突数最小的皇后所在行，循环执行每一列for(i=0;icsp_q_num;i+) temp = min_conflictsq; updateconflictnum(&temp) ; /更新该行皇后在每一列形成的新的棋面的总冲突数 min = rand_max; for(j=0;jcsp_q_num;j+) temp.queeni = j; updatecolumn (&temp, i) ; /更新棋盘第i列皇后放在j行的冲突度 if(temp.eachconflicti min) /把冲突数小的棋盘赋给 min_conflictsq min = temp.eachconflicti; min_conflictsq = temp; if(temp.eachconflicti = min) /如果冲突数相等，则随机更新棋盘 min_conflictsq = rand() % 2 ? min_conflictsq : temp; 3、 ga算法：/ 双亲遗传中的变异算子/ 对种群中的最优两个个体保留，并局部变异看是否可以达到结果 void multimutate (population* p)int i, j, swap ;int worst ;population baby ;worst = 0 ;for (i = 0 ; i eachfitnessi eachfitnessworst)worst = i ;if(p-eachfitnessworst = ga_q_num-1) return;baby = *p ;for (i = 0 ; i p-unitfitness | (double)rand() / rand_max m_critical)*p = baby ;break ;/ 采取轮盘赌局规则进行双亲的选择/ 即被选到的概率与适应度呈正比 （越是优越的个体基因越容易被保留下来）int roulettewheelselection()int selection = 0;int i ;double slice = (double)rand() / rand_max;double addfitness = 0;for(i = 0; i slice)selection = i;break;return selection;/ 杂交 father , mother， 产生的子代保存在 baby中void crossoverfm (population father, population mother, population *baby)int flagmax_queens ;int pos1, pos2, tmp ;int i, j ;/ 随机产生两个基因断点do pos1 = rand() % ga_q_num ;pos2 = rand()