徐秀峰,宽度优先n皇后实验报告

1、本科实验报告课程名称： 人工智能 实验项目： 实验地点： 实验室110 专业班级： 学号 学生姓名： 指导教师： 2016年 4月 24日太原理工大学学生实验报告学院名称计算机科学与技术专业班级计Z1303学号2013002007学生姓名宋纯显实验日期20160420 成绩课程名称人工智能实验题目宽度优先n皇后一、实验目的和要求熟悉和掌握宽度优先搜索的定义和算法过程，并利用宽度优先算法求解n皇后问题，理解求解流程和搜索顺序。理解n皇后问题，并且用宽度优先算法求解。二、实验内容和原理用基于宽度优先搜索的方法求解n皇后问题。N皇后：在nn格的国际象棋上摆放八个皇后，使其不能互相攻击，即任意两个皇后

2、都不能处于同一行、同一列或同一斜线上，问有多少种摆法。宽度优先算法：宽度优先算法从一般的图搜索算法演变而来。在宽度优先算法中，每次选择深度最浅的结点优先拓展。将拓展的结点放在open表的最前边。三、主要仪器设备计算机，实验操作环境（jdk，eclipse），四、操作方法与实验步骤1. 先熟悉宽度优先算法的基本概念；2. 熟悉n皇后问题的概念；3. 用编程语言编程实现实验内容；4. java环境下的实验代码如下：代码：package AI2;import java.util.LinkedList;import java.util.Queue;import java.util.Scanner;pu

3、blic class AI2 /* * param args */static Queue open = new LinkedList();static Queue closed = new LinkedList();static int a;public static void main(String args) / TODO Auto-generated method stubint w = 0;System.out.println(请输入n);Scanner sc = new Scanner(System.in);a = sc.nextInt();Queen q1;q1 = new Qu

4、een(0, null);open.offer(q1);System.out.println(结果为：);while (!open.isEmpty() Queen n = open.poll();/closed.offer(n);if (n.deep=a) /System.out.println(pk);for (int i = 0; i n.deep; i+) System.out.print(n.pathi);System.out.print(,);System.out.println();System.out.println(-);w+;elseexpand(n);System.out.

5、println(w); static void expand(Queen q) for (int i = 0; i a; i+) Queen queen = new Queen(q.deep + 1, q.path);queen.setnext(i);if (check(queen) open.offer(queen);static boolean check(Queen q) for (int i = 0; i q.deep - 1; i+) if (q.pathi = q.pathq.deep-1) |(Math.abs(i-q.deep+1) = Math.abs(q.pathi - q

6、.pathq.deep-1) return false;return true;class Queen int path;int deep;Queen(int deep, int path) this.deep = deep;if (this.deep = 0) this.path = new int1; else this.path=new intdeep;for (int i = 0; i deep - 1; i+) this.pathi = pathi;void setnext(int i) this.paththis.deep - 1 = i;五：实验结果与分析4皇后8皇后本程序理论上可以达到n皇后 （n为大于等于4的任意自然数），但是实际上由于电脑性能的现在 ，在11皇后的时候会发现很明显的延迟，12皇后大约需要5秒，13皇后几分钟，14皇后15-20分钟，15皇后就需要2小时以上了。 六、讨论、心得 通过此次实验，对回溯法有了深刻的理解，对递归方面得到巩固，还有编程方面的知识。 在编写n皇后算法的过程中，此次采用宽度优先算法，因此会造成巨大的程序内存，在n 大于1