一、实验目的与要求：
1、掌握回溯法求解问题的思想
2、学会利用其原理求解八皇后问题
二、实验内容：
运用所学知识，设计并编程实现用回溯法解决相关问题（如：8皇后问题、TSP问题等）。
三、实验器材：
微机+windows操作系统+VC++6.0
四、实验步骤：
1、根据8皇后，可以把其设想为一个数组。
2、根据8皇后的规则，可以设想为在数组上同一直线、横线、跟斜线的数字都不能相同，由此可以得出判断条件。
3、根据判断条件之后，建立回溯点，即可解决问题。
4、撰写实验报告。
五、源代码
JAVA版：
package bahuanghou;
import java.util.Date;
/**
* 在8×8格的国际象棋上摆放八个皇后，使其不能互相攻击， 即任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法。 下面使用递归方法解决
public class EightQueueDemo {
private static final short N = 8; // 使用常量来定义，方便之后解N皇后问题
private static int count = 0; // 结果计数器
public static void main(String[] args) {
Date begin = new Date();
// 初始化棋盘，全部置0
short chess[][] = new short[N][N];
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
chess[i][j] = 0;
}
}
putQueenAtRow(chess, 0);
Date end = new Date();
System.out.println(
"解决 " + N + " 皇后问题，用时：" + String.valueOf(end.getTime() - begin.getTime()) + "毫秒，计算结果：" + count);
}
private static void putQueenAtRow(short[][] chess, int row) {
/**
* 递归终止判断：如果row==N，则说明已经成功摆放了8个皇后 输出结果，终止递归
*/
if (row == N) {
count++;
System.out.println("第 " + count + " 种解：");
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
System.out.print(chess[i][j] + " ");
}
System.out.println();
}
return;
}
short[][] chessTemp = chess.clone();
/**
* 向这一行的每一个位置尝试排放皇后 然后检测状态，如果安全则继续执行递归函数摆放下一行皇后
*/
for (int i = 0; i < N; i++) {
// 摆放这一行的皇后，之前要清掉所有这一行摆放的记录，防止污染棋盘
for (int j = 0; j < N; j++)
chessTemp[row][j] = 0;
chessTemp[row][i] = 1;
if (isSafety(chessTemp, row, i)) {
putQueenAtRow(chessTemp, row + 1);
}
}
}
private static boolean isSafety(short[][] chess, int row, int col) {
// 判断中上、左上、右上是否安全
int step = 1;
while (row - step >= 0) {
if (chess[row - step][col] == 1) // 中上
return false;
if (col - step >= 0 && chess[row - step][col - step] == 1) // 左上
return false;
if (col + step < N && chess[row - step][col + step] == 1) // 右上
return false;
step++;
}
return true;
}
}
-------------------------------------------------------------------------------------------------------
C#版
#include <iostream>
#include <cmath>
using namespace std;
int ans = 0;
int arr[8] = {-1};
bool check(int row, int column){
for(int i = 0; i < row; i++)
if(arr[i] == column) return false;
for(int i = 0; i < row; i++)
if(abs(row-i) == abs(column - arr[i])) return false;
return true;
}
void FindQueen(int row){
if(row > 7){
ans++;
return;
}
for(int column = 0; column < 8; column ++){
if(check(row,column)){
arr[row] = column;
FindQueen(row+1);
arr[row] = -1;
}
}
}
int main(void){
FindQueen(0);
cout << ans << endl;
return 0;
}六、运行结果
实验程序，如下图1所示。
共92种方案 可以任选一种方案显示
图1回溯法求解8皇后问题实验程序界面
实验二：A*算法实验I
一、实验目的与要求：
熟悉和掌握启发式搜索的定义、估价函数和算法过程，并利用A*算法求解N数码难题，理解求解流程和搜索顺序。
1.参考A*算法核心代码，以8数码问题为例实现A*算法的求解程序（编程语言不限），要求设计两种不同的估价函数。
2.设置相同的初始状态和目标状态，针对不同的估价函数，求得问题的解，并比较它们对搜索算法性能的影响，包括扩展节点数、生成节点数等。
3.设置与上述2相同的初始状态和目标状态，用宽度优先搜索算法（即令估计代价h(n)＝0的A*算法）求得问题的解，以及搜索过程中的扩展节点数、生成节点数。
4.参考A*算法核心代码，实现A*算法求解15数码问题的程序，设计两种不同的估价函数，然后重复上述2和3的实验内容。
5.提交实验报告和源程序。
三、实验器材：
微机+windows操作系统+VC++6.0
四、实验步骤：
1.分析不同的估价函数对A*算法性能的影响。
2.根据宽度优先搜索算法和A*算法求解8、15数码问题的结果，分析启发式搜索的特点。
3.画出A*算法求解N数码问题的流程图。
4.完成实验报告要求1和2。
5.总结实验心得体会。
五、上机作业
八数码问题是在3×3的九宫格棋盘上，摆有8个刻有1～8数码的将牌。棋盘中有一个空格，允许紧邻空格的某一将牌可以移到空格中，这样通过平移将牌可以将某一将牌布局变换为另一布局。针对给定的一种初始布局或结构（目标状态），问如何移动将牌，实现从初始状态到目标状态的转变。如下图1表示了一个具体的八数码问题求解。
1.参考A*算法核心代码，以8数码问题为例实现A*算法的求解程序（编程语言不限），要求设计两种不同的估价函数。
2.设置相同的初始状态和目标状态，针对不同的估价函数，求得问题的解，并比较它们对搜索算法性能的影响，包括扩展节点数、生成节点数等。
3.设置与上述2相同的初始状态和目标状态，用宽度优先搜索算法（即令估计代价h(n)＝0的A*算法）求得问题的解，以及搜索过程中的扩展节点数、生成节点数。
4.参考A*算法核心代码，实现A*算法求解15数码问题的程序，设计两种不同的估价函数，然后重复上述2和3的实验内容。
5.提交实验报告和源程序。
六、运行结果
1.分析不同的估价函数对A*算法性能的影响。
2.根据宽度优先搜索算法和A*算法求解8、15数码问题的结果，分析启发式搜索的特点。
实验三：A*算法实验II
一、实验目的与要求：
熟悉和掌握A*算法实现迷宫寻路功能，要求掌握启发式函数的编写以及各类启发式函数效果的比较。
二、实验原理：
A*（A-Star)算法是一种静态路网中求解最短路最有效的方法。公式表示为：f(n)=g(n)+h(n)，其中f(n)是节点n从初始点到目标点的估价函数，g(n)是在状态空间中从初始节点到n节点的实际代价，h(n)是从n到目标节点最佳路径的估计代价。保证找到最短路径（最优解的）条件，关键在于估价函数h(n)的选取：估价值h(n)小于等于n到目标节点的距离实际值)(*nh，这种情况下，搜索的点数多，搜索范围大，效率低，但能得到最优解。如果估价值大于实际值，搜索的点数少，搜索范围小，效率高，但不能保证得到最优解。
寻路问题常见于各类游戏中角色寻路、三维虚拟场景中运动目标的路径规划、机器人寻路等多个应用领域。迷宫寻路问题是在以方格表示的地图场景中，对于给定的起点、终点和障碍物（墙），如何找到一条从起点开始避开障碍物到达终点的最短路径。
假设在一个n*m的迷宫里，入口坐标和出口坐标分别为(1,1)和(5,5)，每一个坐标点有两种可能：0或1，其中0表示该位置允许通过，1表示该位置不允许通过。
如地图：
最短路径应该是：
即：(1,1)-(1,2)-(2,2)-(3,2)-(3,1)-(4,1)-(5,1)-(5,2)-(5,3)-(4,3)-(4,4)-(4,5)-(5,5)
三、实验内容：
1．参考迷宫求解的核心代码，观察求解过程与思路，画出用A*算法求解迷宫最短路径的流程图。
2．设置不同的地图，以及不同的初始状态和目标状态，记录A*算法的求解结果，包括最短路径、扩展节点数、生成节点数和算法运行时间。
3．对于相同的初始状态和目标状态，设计不同的启发式函数，比较不同启发式函数对迷宫寻路速度的提升效果，包括扩展节点数、生成节点数和算法运行时间。
4．提交实验报告和源程序。
四、实验器材：
微机+windows操作系统+VC++6.0
五、实验步骤：
1）、实验目的
2）、实验原理
3）、实验结果
按照实验内容，给出相应结果。
4）、实验总结
1.完成实验报告要求2和3。
2.总结实验心得体会
六、上机作业
1．画出A*算法求解迷宫最短路径问题的流程图。
2．试分析不同启发式函数h(n)对迷宫寻路求解的速度提升效果。
3．分析A*算法求解不同规模迷宫最短路径问题的性能。
七、运行结果
实验四：遗传算法实验I
一、实验目的与要求：
熟悉和掌握遗传算法的原理、流程和编码策略，并利用遗传求解函数优化问题，理解求解流程并测试主要参数对结果的影响。
二、实验内容：
1．用遗传算法求解下列函数的最大值，设定求解精度到15位小数
1）给出适应度函数（Fitness Function）的M文件（Matlab中要求适应度函数最小化）。
2）设计及选择上述问题的编码、选择操作、交叉操作、变异操作以及控制参数等，填入表1，给出最佳适应度(Best fitness)和最佳个体（Best individual）图。
3）使用相同的初始种群（Use random state from previous run），设置不同的种群规模（population size），例如5、20和100，初始种群的个体取值范围（Initial range）为[0;1]，其他参数同表1，然后求得相应的最佳适应度(Best fitness)、平均适应度（Mean fitness）和最佳个体（Best individual），填入下表2，分析种群规模对算法性能的影响。
4)设置种群规模（population size）为20，初始种群的个体取值范围（Initial range）为[0;10]，选择不同的选择操作、交叉操作和变异操作，其他参数同表1，然后独立运行算法10次，完成下表3，并分析比较采用不同的选择策略、交叉策略和变异策略的算法运行结果。
2．用遗传算法求解下面一个Rastrigin函数的最小值，设定求解精度到15位小数。
1）给出适应度函数的M文件（Matlab中要求适应度函数最小化）。
2）设计上述问题的编码、选择操作、交叉操作、变异操作以及控制参数等，填入表4，并画出最佳适应度(Best fitness)和最佳个体（Best individual）图。
3）设置种群的不同初始范围，例如[1;1.1]、[1;100]和[1;2]，画出相应的最佳适应度值(Best fitness)和平均距离（Distance）图，比较分析初始范围及种群多样性对遗传算法性能的影响。
4）设置不同的交叉概率（Crossover fraction=0、0.8、1），画出无变异的交叉（Crossover fraction=1）、无交叉的变异(Crossover fraction=0)以及交叉概率为0.8时最佳适应度值(Best fitness)和和平均距离（Distance）图，分析交叉和变异操作对算法性能的影响。
三、实验器材：
Matlab 7.X的遗传算法工具箱。
四、实验步骤：
1．画出遗传算法的算法流程图。
2．根据实验内容，给出相应结果。
3.总结遗传算法的特点，并说明适应度函数在遗传算法中的作用。
五、上机作业
1．画出遗传算法的算法流程图。
2．根据实验内容，给出相应结果。
六、运行结果
实验五：遗传算法实验II
一、实验目的与要求：
熟悉和掌握遗传算法的原理、流程和编码策略，理解求解TSP问题的流程并测试主要参数对结果的影响，掌握遗传算法的基本实现方法。
二、实验内容：
1、参考实验系统给出的遗传算法核心代码，用遗传算法求解不同规模（例如10个城市，20个城市，100个城市）的TSP问题，把结果填入表1。
2、对于同一个TSP问题（例如10个城市），设置不同的种群规模（例如10，20，100）、交叉概率（0，0.5，1）和变异概率（0，0.5，1），把结果填入表2。
3、设置种群规模为100，交叉概率为0.85，变异概率为0.15，然后增加1种变异策略（例如相邻两点互换变异、逆转变异或插入变异等）和1种个体选择概率分配策略（例如按线性排序或者按非线性排序分配个体选择概率）用于求解同一TSP问题（例如10个城市），把结果填入表3。
4、提交实验报告和源程序。
三、实验器材：
Matlab 7.X的遗传算法工具箱。
四、实验步骤：
1、画出遗传算法求解TSP问题的流程图。
2、分析遗传算法求解不同规模的TSP问题的算法性能。
3、对于同一个TSP问题，分析种群规模、交叉概率和变异概率对算法结果的影响。
4、增加1种变异策略和1种个体选择概率分配策略，比较求解同一TSP问题时不同变异策略及不同个体选择分配策略对算法结果的影响。
五、上机作业
1、画出遗传算法求解TSP问题的流程图。
2、分析遗传算法求解不同规模的TSP问题的算法性能。
六、运行结果
实验六：基于神经网络的模式识别实验
一、实验目的与要求：
理解BP神经网络和离散Hopfield神经网络的结构和原理，掌握反向传播学习算法对神经元的训练过程，了解反向传播公式。通过构建BP网络和离散Hopfield网络模式识别实例，熟悉前馈网络和反馈网络的原理及结构。
二、实验原理
BP学习算法是通过反向学习过程使误差最小，其算法过程从输出节点开始，反向地向第一隐含层(即最接近输入层的隐含层)传播由总误差引起的权值修正。BP网络不仅含有输入节点和输出节点，而且含有一层或多层隐(层)节点。输入信号先向前传递到隐节点，经过作用后，再把隐节点的输出信息传递到输出节点，最后给出输出结果。
离散Hopfield神经网络的联想记忆过程分为学习和联想两个阶段。在给定样本的条件下，按照Hebb学习规则调整连接权值，使得存储的样本成为网络的稳定状态，这就是学习阶段。联想是指在连接权值不变的情况下，输入部分不全或者受了干扰的信息，最终网络输出某个稳定状态。
三、实验内容：
1.针对教材P243例8.1，设计一个BP网络结构模型（63-6-9），并以教材图8.5 为训练样本数据，图8.6为测试数据。
（1）从Matlab工作空间导入（Import）训练样本数据（inputdata，outputdata）和测试数据（testinputdata），然后新建一个神经网络（New Network），选择参数如下表1，给出BP神经网络结构图。
（2）输入训练样本数据（inputdata，outputdata），随机初始化连接权（Initialize Weights），给出BP神经网络训练成功后的误差变化曲线图，训练参数设置如表2所示。
（3）选择不同的训练函数，例如TRAINGDM（梯度下降动量BP算法）、TRAINLMM（Levenberg-Marquardt BP训练函数），然后输入训练样本数据（inputdata，outputdata），训练参数设置如表2所示，设置相同的初始连接权（Revert Weights），观察不同BP训练算法的学习效果，给出各训练算法下的误差变化曲线图。
（4）在上述3个训练好的BP神经网络中，选择训练误差最小的一个网络，并给出训练后的连接权值和偏置，然后输入测试数据（testinputdata）进行仿真（Simulate），并把训练和测试的结果都导出到工作空间，给出训练后的输出结果和输出误差，以及测试后的输出结果和输出误差。
（5）针对Training function（训练函数）为TRAINGD的BP网络，然后设置不同的学习率（lr），例如0.01、0.1、0.5、1，观察TRAINGD训练算法的学习效果，给出各学习率下的误差变化曲线图。
2.已知字符点阵为 模式，两组训练数据为
设计一个能够存储这两个字符的离散Hopfield神经网络，要求：
（1）给出相应的离散Hopfield神经网络结构图；
（2）计算连接权值及阈值（阈值可设为 0）；
（3）输入下列测试数据
给出网络最终输出的稳定状态。
四、实验器材：
Matlab7.X的神经网络工具箱：在Matlab7.X的命令窗口输入nntool，然后在键盘上输入Enter键，即可打开神经网络工具箱。
五、实验步骤：
1．按照实验内容，给出相应结果。
2．分析比较采用梯度下降训练算法的BP网络学习率的变化对于训练结果的影响。
3.分析比较BP网络和离散Hopfield网络在模式识别方面的异同点。
六、上机作业
1．分析比较采用梯度下降训练算法的BP网络学习率的变化对于训练结果的影响。
2.分析比较BP网络和离散Hopfield网络在模式识别方面的异同点。
实验七：基于神经网络的优化计算实验
掌握连续Hopfield神经网络的结构和运行机制，理解连续Hopfield神经网络用于优化计算的基本原理,掌握连续Hopfield神经网络用于优化计算的一般步骤。
二、实验内容：
1、参考求解TSP问题的连续Hopfield神经网络源代码，给出15个城市和20个城市的求解结果（包括最短路径和最佳路线），分析连续Hopfield神经网络求解不同规模TSP问题的算法性能。
2、对于同一个TSP问题（例如15个城市的TSP问题），设置不同的网络参数，分析不同参数对算法结果的影响。
3、上交源代码。
三、实验器材：
微机+windows操作系统+VC++6.0
四、实验步骤：
1、画出连续Hopfield神经网络求解TSP问题的流程图。
2、根据实验内容，给出相应结果及分析。
3、总结连续Hopfield神经网络和遗传算法用于TSP问题求解时的优缺点。
4、实验总结
五、上机实验
1）实验原理
连续Hopfield神经网络的能量函数的极小化过程表示了该神经网络从初始状态到稳定状态的一个演化过程。如果将约束优化问题的目标函数与连续Hopfield神经网络的能量函数对应起来，并把约束优化问题的解映射到连续Hopfield神经网络的一个稳定状态，那么当连续Hopfield神经网络的能量函数经演化达到最小值时，此时的连续Hopfield神经网络的稳定状态就对应于约束优化问题的最优解。
2）流程图
实验八：模糊推理系统实验
一、实验目的与要求：
理解模糊逻辑推理的原理及特点，熟练应用模糊推理，了解可能性理论。
二、实验内容：
1、设计洗衣机洗涤时间的模糊控制。已知人的操作经验为：
“污泥越多，油脂越多，洗涤时间越长”；
“污泥适中，油脂适中，洗涤时间适中”；
“污泥越少，油脂越少，洗涤时间越短”。
要求：
（1）假设污泥、油脂、洗涤时间的论域分别为[0,100]、[0,100]和[0,120]，设计相应的模糊推理系统，给出输入、输出语言变量的隶属函数图，模糊控制规则表和推论结果立体图。
（2）假定当前传感器测得的信息为00(60,70xy==污泥）（油脂），采用面积重心法反模糊化，给出模糊推理结果，并观察模糊推理的动态仿真环境，给出其动态仿真环境图。
提示：模糊控制规则如下表1所示，其中SD（污泥少）、MD（污泥中）、LD（污泥多）、NG（油脂少）、MG（油脂中）、LG（油脂多）、VS（洗涤时间很短）、S（洗涤时间短）、M（洗涤时间中等）、L（洗涤时间长）、VL（洗涤时间很长）。
2．假设两汽车均为理想状态，即
，Y为速度，U为油门控制输入。
（1）设计模糊推理系统控制2号汽车由静止启动，追赶200m外时速90km的1号汽车并与其保持30m的距离。
（2）在25时刻1号汽车速度改为时速110km时，仍与其保持30m距离。
（3）在35时刻1号汽车速度改为时速70km时，仍与其保持30m距离。
要求：
（1）如下图1所示，设计两输入一输出的模糊推理系统作为2号汽车的模糊控制器，其中输入为误差e和误差的变化e&，输出为1号汽车的油门控制u，采用面积等分法反模糊化，给出输入、输出语言变量的隶属函数图，模糊控制规则表，推论结果立体图和模糊推理的动态仿真环境图。
（2）用SIMULINK仿真两车追赶的模糊控制系统，给出目标车（1号汽车）的速度曲线图，以及追赶车（2号汽车）的速度曲线图和与目标车（1号汽车）相对距离变化图。
提示：模糊控制规则如下表2所示，其中
和油门控制u的论域分别为[0,1]、[-3,3]和[-1,1]，r的隶属函数如图2所示。
三、实验器材：
Matlab7.0的Fuzzy Logic Tool。
四、实验步骤：
1）实验目的
2）实验内容
3）实验结果
按照实验要求，给出相应结果。
4）实验总结
4.1）分析隶属度、模糊关系和模糊规则的相互关系。
4.2）总结实验心得体会
五、上机作业
1、设计洗衣机洗涤时间的模糊控制。
2．假设两汽车均为理想状态，设计汽车追赶的模糊控制。
六、运行结果
