第1次实验——NPC问题(回溯算法、聚类分析)

题目：八皇后问题，是一个古老而著名的问题，是回溯算法的典型案例。该问题是国际西洋棋棋手马克斯·贝瑟尔于1848年提出：在8X8格的国际象棋上摆放八个皇后，使其不能互相攻击，即随意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法。 高斯觉得有76种方案。1854年在柏林的象棋杂志上不同的作者发表了40种不同的解，后来有人用图论的方法解出92种结果。计算机发明后，有多种方法能够解决此问题。

    请编程实现八皇后问题，并把92种解的前三种解输出到屏幕（8*8的二维矩阵，Q代表皇后，X代表空）。并把此问题的求解过程延伸到N皇后问题。

解题思路：我们採用回溯的思想来解这道题，開始我们从第一行第一列開始放第一个皇后，然后依次在第二行可放皇后的位置放置皇后，直到最后到达列的最大值时还没有将皇后放完，通过又一次回溯到第二列依次进行反复的操作，否则得到对应的皇后排放方法。

以下的代码能够实现n皇后问题的求解。

源码

package review;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class queens {

	public static int num = 0; // 累计方案总数
	public static int queensnumber; // 皇后个数，同一时候也是棋盘行列总数
	public static int[] cols; // 定义cols数组，表示n列棋子摆放情况

	public static void main(String args[]) {
		System.out.println("请输入要展示 的皇后数量");
		BufferedReader strin = new BufferedReader(new InputStreamReader(
				System.in));
		try {
			queensnumber = Integer.parseInt(strin.readLine());
			if (queensnumber <= 0) {
				System.out.println("输入不对");
			} else {
				System.out.println("展示前三种摆法");
				queens queen = new queens(queensnumber);
			}
		} catch (Exception e) {
			System.out.println("输入不对");
		}
	}

	public queens(int queensnumber) {
		cols = new int[queensnumber];
		getArrangement(0, queensnumber);
		System.out.println(queensnumber + "皇后问题有" + num + "种摆放方法。");
	}

	public void getArrangement(int n, int queensnumber) {

		// 遍历该列全部不合法的行，并用rows数组记录，不合法即rows[i]=true
		boolean[] rows = new boolean[queensnumber];
		for (int i = 0; i < n; i++) {
			rows[cols[i]] = true; // 摆放了设置为true
			int d = n - i;
			if (cols[i] - d >= 0)
				rows[cols[i] - d] = true;
			if (cols[i] + d <= queensnumber - 1)
				rows[cols[i] + d] = true;
		}
		for (int i = 0; i < queensnumber; i++) {
			// 推断该行是否合法
			if (rows[i])
				continue;
			// 设置当前列合法皇后所在行数
			cols[n] = i;
			// 当前列不为最后一列时
			if (n < queensnumber - 1) {
				getArrangement(n + 1, queensnumber);// 递归
			} else {
				// 累计方案个数
				num++;
				// 打印
				print();
			}
		}
	}

	public void print() {

		if (num >= 4) // 打印前三中方案
		{
			return;
		} else {
			System.out.println("第" + num + "种摆法 ");
			for (int i = 0; i < queensnumber; i++) {
				for (int j = 0; j < queensnumber; j++) {
					if (i == cols[j]) {
						System.out.print("Q ");
					} else
						System.out.print("* ");
				}
				System.out.println(" ");
			}
		}
	}
}

结果例如以下：

四皇后：

八皇后

为了实现因材施教的目标，现教务处计划对学生进行摸底并分类，假如使用K均值聚类算法，而且觉得学生大概能够分为四类，分别为“积极主动型”、“学霸型”、“游戏人生型”、“迷茫无目标型”。如今你是该项目的负责人，（1）请设计一个较为完整的项目实施方案；（2）你是否认可对学生进行分类？（3）依照你给定的实施方案与须要測量的要素（如天学习时间），请尝试依照自身情况对其进行回答，以及对自身的评价与定位和努力目标。

分析思路：由于我们是採用k均值聚类算法，以下就是该算法的步骤，那么我们就应该依据步骤来开展和实施。

K-means聚类算法的一般步骤：

1. 初始化。输入基因表达矩阵作为对象集X，输入指定聚类类数N，并在X中随机选取N个对象作为初始聚类中心。设定迭代中止条件，比方最大循环次数或者聚类中心收敛误差容限。
2. 进行迭代。依据相似度准则将数据对象分配到最接近的聚类中心，从而形成一类。初始化隶属度矩阵。
3. 更新聚类中心。然后以每一类的平均向量作为新的聚类中心，又一次分配数据对象。
4. 重复运行第二步和第三步直至满足中止条件。

（1）详细的实施方案：1、准备工作：在我们确定开展这项活动后，首先我们要进行对象的选取形成对象集X,这里我们的对象就是学校的学生，然后我们要进行指定聚类类数N,这个就是我们将学生分成哪几种类型，以及类型的总数。之后，我们就能够从x随机抽取N个对象（学生）作为聚类的中心，设定对应的迭代中止条件。

2、进行迭代，我们開始对我们的对象进行大量的实际调查，得到对应的数据，然后依据相似度准则将数据对象分配到最接近聚类中心，从而形成一类，初始化隶属度矩阵。实际上这个做的就是将收集后的数据通过迭代的方式进行分类，达到我们对几种不同学生数据的分类。

3、更新聚类中心，然后以每一类的平均量作为新的聚类中心，又一次分配数据对象。这个的优点就是通过调查统计过程中的实时数据来不断的更新我们的实施方案，能够降低统计的出错率。

4、重复进行第二第三步，达到中止条件为止。也就是我们在开展调查时，数量达到一定量（预估足够完毕我们的统计工作，事先设立的，我们就能够停止调查工作。）

详细的实施过程中，我们能够调查同学的“天学习时间、天游戏时间、上课时间、去图书馆时间、參加社团活动时间、看课外书时间…………

有了上面的这样的思路，我们开展这个调查的方式能够通过的方式有：网上问卷调查，实地跟踪问卷调查。为了达到每一个人參与的效果我们能够把这个加到教务系统的教学评估模块，对大家进行评判。为了能够正确的理解和正确的态度来完毕这个调查，前期一定要做好相关的宣传工作，否则收取不到可靠的数据资料，我们的调查将会大打折扣。

（2）假设这个分类仅仅是作为一个调查，然后依据调查来开展教学活动的话是能够的，这对学生进行分类，并非对学生进行369等的来进行分类和对待。可是我们也应该要有较多的注意事项，比方匿名工作，保护学生的隐私。假设将来开展活动，老师等人要抱着一种同等对待学生的眼光。因此，我们不能大肆的贴上学生类型到个人标签上，这样不利学生的发展。

（3）自身的评价：

天学习时间

1、上课时间：3小时

2、课外完毕作业时间：1小时

3、看课本书：0.2小时

4、其它学习时间：2小时

娱乐时间

1、体育运动：0.3小时

2、看新闻、电视剧、电影：2小时

学生工作时间

1、协助老师完毕工作：0.5小时

2、班级、社团学生会：0.5小时

生活起居时间

1、起床：0.5小时

2、吃饭：1小时

……

自我评价:总的来说，我是一个较为踏实的人，不玩游戏，參加活动比較积极的人。每天都感觉自己有比較多的事情在忙，较为充实。可是专业知识还不够扎实，专业动手能力较差。尽管如今已经是大三了，时间不怎么多，可是自己还是会坚持的学下去。尽自己最大的能力来提高自己。假设要用上面四种类型来限定自己的话，我好想哪一种都不属于，由于我认为我有时主动，有时又不主动，学习态度端正，但并非那种学霸，学习能力特别强。我不玩游戏，也有一定的目标。给自己一个类型的话：我认为我是一个踏实上进型。