AI报告-李华勇

人工智能课程报告1课程:人工智能实验报告班级:191121班学号:20121004362学生姓名:李华勇指导教师:赵曼2014年11月人工智能课程报告2目录一、罗马利亚度假问题...............................................................................................31.问题描述.........................................................................................................32.数据结构.........................................................................................................42.1广度优先算法.......................................................................................42.2深度优先算法.......................................................................................42.3贪婪算法...............................................................................................42.4A*算法...................................................................................................43.算法思想.........................................................................................................53.1广度优先搜索算法...............................................................................53.2深度优先搜索算法...............................................................................53.3贪婪算法...............................................................................................63.4A*算法...................................................................................................64.运行结果.........................................................................................................75.比较讨论.........................................................................................................86.主要代码.........................................................................................................8二、N皇后问题..........................................................................................................131.问题描述.........................................................................................................132.数据结构.........................................................................................................132.1回溯法（递归）.................................................................................132.2GA算法................................................................................................132.3CSP的最小冲突法..............................................................................133.算法思想.........................................................................................................143.1回溯法（递归）.................................................................................143.2CSP的最小冲突法..............................................................................143.3GA算法................................................................................................154.运行结果.........................................................................................................165.比较讨论.........................................................................................................176.主要代码.........................................................................................................18人工智能课程报告3一、罗马利亚度假问题题目：分别用宽度优先、深度优先、贪婪算法和A*算法求解“罗马利亚度假问题”。要求：分别用文件存储地图和启发函数表，用生成节点数比较几种算法在问题求解时的效率，并列表给出结果。1.问题描述从文件中读取图和启发函数，分别用广度优先、深度优先、贪婪算法、A*算法得到从起始点Arad到目标点Bucharest的一条路径，即为罗马尼亚问题的一个解。在求解的过程中记录生成扩展节点的个数（用于比较几种算法的优劣），用堆栈记录DepthFSearch和BroadFSearch的路径。人工智能课程报告42.数据结构分别使用了图结构，顺序队列，顺序表以及堆栈。对于每一个图中的结点，定义了一个结构体HeuristicG，结构体中包含结点的名称以及对应的启发函数值。typedefstruct{charG[20];intvalue;}HeuristicG;typedefstruct//图结构：typedefstruct//链表{{SeqListVertices;stringlist[20];intedge[20][20];intsize;intnumedge;}SeqList;}AdjMGraph;typedefstruct//队列typedefstruct//栈{intqueue[20];{intrear;intstack[20];intfront;inttop;intcount;}SeqStack;}SeqCQueue;2.1广度优先算法使用了数据结构中的图、队列和堆栈。2.2深度优先算法使用了数据结构中的图和堆栈。2.3贪婪算法使用了数据结构中的图。2.4A*算法使用了数据结构中的图。人工智能课程报告53.算法思想3.1广度优先搜索算法voidBF_Search(AdjMGraphG,HeuristicGdata[],intv0,intvg,int*Expand,int*count,intvisited[],intBFS_path[])v0---起始节点vg---目标节点Expand---返回扩展结点数count---返回路径结点数BFS_path[]---存储路径信息G、data[]---用来读取图的各种信息visited[]---用来存储节点是否已经被访问的信息广度优先搜索是分层搜索的过程，广度优先搜索算法思想是用一个队列来保存访问过的顶点的顺序，以便按顺序访问这些顶点的邻接顶点，并把这些邻接顶点依次入栈。在函数中我还创建了两个栈，SeqStackSaveQ，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深度优先搜索算法voidDF_Search(AdjMGraphG,SeqStack*S,HeuristicGdata[],int*Expand,intv0,intvg,intvisited[])v0---起始节点vg---目标节点Expand---返回扩展结点数人工智能课程报告6SeqStack*S---用堆栈存储路径信息visited[]---存储路径是否被访问的信息G、data[]---用来读取图的各种信息深度优先搜索的算法思想是用栈来保存已经访问过的节点，递归找该节点的第一个邻接顶点并把把顶点入栈，直到找不到顶点的邻接顶点为止，然后回溯，找该顶点父顶点的下一个邻接顶点。使用深度优先搜索算法，每次都在访问完当前顶点后首先访问当前顶点的第一个邻接顶点。深度优先搜索算法如下：1)访问顶点v并标记顶点v为以访问，把v0压入栈S，并在屏幕上输出v。2)如果v0！=-1，查找顶点v的第一个邻接顶点w3)若顶点v的邻接顶点w存在且为被访问，则继续执行，否则算法结束。4)若果w=vg，即找到目标节点，算法结束。5)弹出S栈顶元素。6)查