n皇后问题和罗马尼亚问题实习报告.doc

人工智能 PAGE 10 人工智能课程实 习报告 题目：n皇后问题和罗马尼亚问题 班号： 191122 学号： 20121003553 姓名： 叶 超 指导老师：赵曼 2014.11 目录 TOC \o 1-4 \h \z \u 25370 人工智能课程实习报告 1 20347 目录 2 2571 罗马尼亚问题 4 25903 一、问题描述 4 26234 二、图的数据结构 5 20710 三、实现算法 5 4975 1.宽度优先 5 8283 1.1数据结构： 5 11827 1.2算法思想： 6 4168 1.3运行结果： 6 2785 2.深度优先 7 11643 2.1数据结构： 7 28585 2.2算法思想： 7 18331 2.3运行结果： 7 20228 3.贪婪算法 8 2810 3.1数据结构： 8 8370 3.2算法思想： 8 561 3.3运行结果： 8 14197 4.A*算法 9 1362 4.1数据结构： 9 8685 4.2算法思想： 9 3061 4.3运行结果： 9 22270 四、比较结论 9 16498 N皇后问题 11 12958 一、问题描述： 11 26101 二、数据结构 11 11789 三、实现算法 11 28770 1、回溯法 12 22201 1.1数据结构： 12 25629 1.2算法思想： 12 24932 1.3运行结果: 12 1321 2、遗传算法 12 25405 2.1数据结构： 13 22597 2.2算法思想： 13 18705 2.3运行结果 13 19951 3、CSP最小冲突法 13 9411 3.1数据结构： 13 28271 3.2算法思想： 14 27553 3.3运行结果: 14 22367 四、比较结论 14 21591 总结 15 7753 附源代码 15 14737 罗马尼亚问题 15 2383 N皇后问题 26 20102 递归算法 27 22010 遗传算法 29 7429 csp 最小冲突法 35 罗马尼亚问题 一、问题描述 （1）罗马尼亚问题：Find Bucharest starting at Arad 分别用宽度优先、深度优先、贪婪算法和A*算法求解“罗马利亚度假问题”。要求：分别用文件存储地图和启发函数表，用生成节点数比较几种算法在问题求解时的效率，列表给出结果。 附（罗马尼亚地图） （3）各结点启发值： 二、图的数据结构 (1)节点信息： typedef struct { char cityname[20];／／城市名 int value;　　　／／启发函数值 int cost;　　　　／／路径花费 }Ver; (２)地图信息 typedef struct { Ver V[MaxV];／／一维城市数组 int edge[MaxV][MaxV];／／二维边数组 int numofedges; }Graph; （3）图的操作函数 void Read_V(Graph G)；//从文件读取顶点信息 void Read_edge(Graph G)；//从文件读取边的信息 int GetFirstV(Graph G,int v)；//取节点v的第一个子节点 int GetNextV(Graph G,int v1,int v2)；//取节点v1子节点v2后的第一个子节点 三、实现算法 1.宽度优先 1.1数据结构： 队列（BFS，贪婪，Ａ*公用） typedef struct { int queue[MaxSize]; int rear; int front; int count; } SeqCQuene; 队列操作： 　 void QueueInitiate(SeqCQuene *Q)； 　 int QueueNotEmpty(SeqCQuene Q)； 　 int QueueDelete(SeqCQuene *Q,int *d)； 　 int QueueAppend(SeqCQuene *Q,int x)；　／／先进先出（BFS）　　　 　 记录父亲用于打印路径 typedef struct { int father; int me; }way; 1.2算法思