四皇后问题实验报告

第一篇：四皇后问题实验报告

人工智能——四皇后问题

一、问题描述

四皇后问题

一个4×4国际象棋盘，依次放入四个皇后，条件：每行、每列及对角线上只允许出现一枚棋子。

设：DATA=L（表）x∈L x ∈﹛i j﹜ 1≤ i, j ≤4 其中：i j 表示棋子所在行列 如：24 表示第二行第四列有一枚棋子 ∵棋盘上可放入的棋子数为0 ～ 4 个

∴L表中的元素数为0 ～ 4 个，即 Length L = 0 ～ 4，如图A ﹛12，24，31，43 ﹜

定义规则： if 1≤ i ≤4 and Length DATA = i －1 then APPEND(DATA(ij))1≤ j ≤4 ① 对于任一行i，1≤ j ≤4 表明每行有四条规则。

比如第一行：R11，R12，R13，R14 ② 棋盘中共有四行，所以共有16条规则。

即： R11，R12，R13，R14 R21，R22，R23，R24 R31，R32，R33，R34 R41，R42，R43，R44 ③ 16条规则中，哪些是当前可用规则，取决于DATA的长度，即：DATA中的元素个数。换言之，每次只能将一个棋子放在当前行的下一行。

二、回溯法搜索策略图

讨论：

上述算法产生22次回溯，原因在于规则自然顺序排列，没考虑任何智能因素。改进算法

定义对角线函数：diag(i,j)：过ij点最长的对角线长度值。

规定：① 如果： diag(i,k)≤ diag(i,j)则规则排列次序为： Rik，Rij 同一行四条规则中，对角线函数值小的排在前面

② 如果：diag(i,k)＝ diag(i,j)则规则排列次序为： Rij，Rik j ＜ k 对角线长度相等的规则按照字母排列顺序排序

讨论：

① 利用局部知识排列规则是有效的。

② BACKTRACK算法对重复出现的状态没有判断，所以可能造成出现死循环。③ 没有对搜索深度加以限制，可能造成搜索代价太大。

三、算法描述

回溯法——在约束条件下先序遍历，并在遍历过程中剪去那些不满足条件的分支。

使用回溯算法求解的问题特征，求解问题要分为若干步，且每一步都有几种可能的选择，而且往往在某个选择不成功时需要回头再试另外一种选择，如果到达求解目标则每一步的选择构成了问题的解，如果回头到第一步且没有新的选择则问题求解失败。

在回溯策略中，也可以通过引入一些与问题相关的信息来加快搜索解的速度。对于皇后问题来说，由于每一行、每一列和每一个对角线，都只能放一个皇后，当一个皇后放到棋盘上后，不管它放在棋盘的什么位置，它所影响的行和列方向上的棋盘位置是固定的，因此在行、列方面没有什么信息可以利用。但在不同的位置，在对角线方向所影响的棋盘位置数则是不同的。可以想象，如果把一个皇后放在棋盘的某个位置后，它所影响的棋盘位置数少，那么给以后放皇后留下的余地就太大，找到解的可能性也大；反之留有余地就小，找到解的可能性也小。

四、算法流程图

五、源程序

#include #define N 4 char board[N][N];int t;int col[N];

//存储第i行对应的列的值，这样的(i,j)值满足当前棋盘上的皇后不能互相攻击。

int safetyPlace(int x,int y)//(x,y)位置是否安全 {

int i,j;

for(i=0;i

{

j=col[i];

if(x==i||y==j)

return 0;

if(x-y==i-j||x+y==i+j)

//判断左右对角线

return 0;

}

return 1;} void get_position(int i)

//处在第i行时状态 {

int w,j;

char a[1]={3};

if(i==N)

//输出棋盘

{

for(w=0;w

{

for(j=0;j

{

if(board[w][j]==001)

printf(“%c ”,board[w][j]);

else

{

printf(“%c”,a[0]);

printf(“%c ”,board[w][j]);

}

}

printf(“n”);

}

printf(“n”);

printf(“--------------n”);

t++;

}

else

{

int u;

for(u=0;u

{

if(safetyPlace(i,u)==1)

{

col[i]=u;

//记录下第i行可行的列的位置

board[i][u]=001;

//放置皇后

get_position(i+1);

//转换到下一个状态，即下一行

col[i]=0;

//回溯到当前状态，重置列和棋盘的值

board[i][u]=0;

} }

} } main(){

printf(“%c是皇后!nn”,001);get_position(0);printf(“一共有%d种方法！n”,t);}

六、结果截图

七、总结——心得体会

通过对四皇后问题的编程学习，让我对搜索策略更深层次的理解，尤其能比较熟练掌握回溯策略——首先将规则给出一个固定的排序，在搜索时，对当前状态（搜索开始时，当前状态是初始状态）依次检测每一条规则，在当前状态未使用过的规则中找到第一条可应用规则，应用于当前状态，得到的新状态重新设置为当前状态，并重复以上搜索。如果当前状态无规则可用，或者所有规则已经被试探过仍未找到问题的解，则将当前状态的前一个状态（即直接生成该状态的状态）设置为当前状态。重复以上搜索，直到找到问题的解，或者试探了所有可能后仍找不到问题的解为止。

同时，在整个编程学习过程中，使得我对人工智能感到越来越多的趣味性（例如四皇后问题上升到n皇后如何求解），更引起我对学习人工智能这门课程的积极性。

第二篇：数据结构实验报告--八皇后（写写帮整理）

数据结构实验报告

1．实验要求

实验目的：利用栈结构实现八皇后问题

八皇后问题如下：八皇后问题是19世纪著名的数学家高斯于1850年提出的。他的问题是，在8*8的棋盘上放置8个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行，同一列，同一斜线上。

实验内容：利用所学的栈结构用递归或非递归解决八皇后问题。

2.程序分析

程序使用程序最主要只是在主函数用了一个递归函数Queen。

Queen函数使用了三个参数m,flag[][],chess[][]。其中m是行数，flag[][]是判断二维数组何处可以放置皇后，chess[][]是存储字符串的二维数组。

主函数中对Queen函数中的形参数组flag[][],chess[][]进行初始化，在Queen函数中再进行各种操作。

Queen函数执行代码，首先行数m为0，当m小于7时，通过if…else…语句，利用Queen(m+1,f,c)重新执行递归函数到下一行。

2.1 存储结构

存储结构：数组存储。

flag[][]数组存储数字判断输出和储能放置皇后,chess[][]数组存储字符串即皇后和非皇后的形状。

2.2 关键算法分析

1、关键算法： a．

for(i=0;i<8;i++)

for(j=0;j<8;j++)

{

f[i][j]=0;

c[i][j]='*';

说明：对棋盘进行初始化 未放置皇后的为“*” b．

for(i=0;i<8;i++)

for(j=0;j<8;j++)

{

c[i][j]=chess[i][j];

f[i][j]=flag[i][j];

} 说明：对c[][]，f[][]进行初始化。c．

for(i=0;i<8;i++)

for(j=0;j<8;j++)

{

if(f[i][j]==0 &&(i+j==m+k || m==i || k==j || m-k==i-j))

f[i][j]=-1;

}

c[m][k]='#';

说明：已放置皇后的行、列以及对角线都不能再放置皇后。

已放置皇后的显示为“#”。d.if(m==7)

{

cout<<“算法的第”<<++count<<“个解为：”<

for(int i=0;i<8;i++)

{

for(int j=0;j<8;j++)

{

cout<

}

cout<

}

cout<

cout<

return;

}

else Queen(m+1,f,c);

说明：首先判断是否已执行到最后一行

每输出一个算法，count计数器加1 若没有执行到最后一行，m+1继续执行Queen函数

2.3 其他

要求程序在一开始创建一个统计算法解个数的加法器。

3.程序运行结果

1、测试主函数流程：流程图如图所示

2、测试结论：输出解决算法的个数及八皇后问题的图解。

4.总结

一．问题及解决办法

1.一开始编的时候对同一行，同一列以及同一斜行不能排皇后的算法不能准确编写，后来通过画图发现了这三个情况数组行标和列标的特点，从而解决了这个问题。

2.程序只能输出从65至99的解，其他解不显示，后来发现是因为界面太小的原因。二．心得体会

对于刚学的栈表以及递归函数一定要多用才能熟悉，才能知道实现的具体细节问题。对一些出现的错误一点要仔细分析，明白以后就会掌握的很牢固。对于递归函数一定要充分理解它的意义才能用好它。

在编写代码中如果对于一些抽象的算法构思感到困难，可以通过画图，在纸上先进行演算推导出各变量之间的关系，再进行编写可能会使问题变得简单明了一些。三．改进

递归算法解决八皇后问题比较简单明了，下次可以尝试不使用递归而用非递归编写算法，这样可能会更牢固更好的掌握栈的思想，巩固已学的知识。

第三篇：分析化学实验报告四

实验四标定氢氧化钠、测定铵态氮

摘要：固体NaOH容易吸收空气中的水分和CO2，因此不能直接配制准确浓度的NaOH标准溶液，只能先配置近似浓度的溶液，然后用基准物质标定其准确 浓度，标定结果显示NaOH溶液浓度为0.09675mol/L。铵态氮中除碳酸氢铵 可用标准酸直接滴定外，其他铵盐由于NH4+是一种极弱酸（Ka=5.6x10-10), 不能用标准碱直接滴定。一般用“蒸馏法”或“甲醛法”来测定其含量，测 定结果显示铵态氮的含量为26.12％。

关键词：滴定；NaOH标准溶液；铵态氮

前言

由于NaOH固体在空气中易变质，很难配制标准浓度的NaOH溶液，所以先配制近似浓度的溶液，再用基准物质来标定其准确浓度；测定除NaHCO3外的铵态氮，因NH4+是一种极弱酸，不能用标准碱直接滴定，应采用“蒸馏法”或“甲醛法”间接测定，本次试验采用“甲醛法”，即铵盐先与甲醛生成六亚甲基四胺酸和强酸，再用标定后的NaOH溶液滴定，w

计算可得铵态氮的含量。

一、仪器与试剂

50mL碱式滴定管1支、20mL移液管1支、25mL移液管1支、250mL容量瓶1个、250mL锥形瓶3只、200mL烧杯1只、电子天平；KHR固体、酚酞指示剂、3mol/L NaOH溶液。

二、试验方法

1、制备NaOH溶液：17mL 3mol/L NaOH→0.1mol/L 500mL NaOH；

2、标定NaOH：称取KHR 0.405~0.415g，加20mL水溶解，再加两滴酚酞指示剂，最后用NaOH溶液滴定至浅红色且30s不褪色，平行五次；

3、测定铵态氮：

称取1.6g氯化铵，加水溶解，250mL容量瓶定容，移取25.00mL至锥形瓶，加入5mL甲醛，再滴加两滴酚酞指示剂，最后用标定过后的NaOH溶液滴定至浅红色，平行五次：

空白试验：取25.00mL蒸馏水代替氨溶液进行测定，平行三次。cNaOHVNaOHMmN100%

注意：标定NaOH要求

ds或

d≤0.2％；测定铵态氮要求

s或

d≤0.4％；空白滴

定要求≤0.4%，且空白>0.2mL要扣除。

三、结果与讨论

1、标定NaOH 初读数(mL)末读数(mL)V滴定(mL)

0.03 20.72 20.69

0.12 20.79 20.67

xni

0.03

20.72 20.69 0.11 20.78 20.67 0.22 20.86 20.64

V

=20.672mL，s

cKHRVKHRVNaOH

x

ni

n

n1

=0.02049，s=0.1%<0.2%，则：

cNaOH

=

0.12020.672

=0.09675mol/L2、铵态氮的测定 测定铵态氮 0.01 30.87 30.86

0.13 31.07 30.94

0.04 30.89 30.85

30.77 30.77

0.01 30.86 30.85

x

V

n

i

xn

=30.854mL，s

cNaOHVNaOHM

m

ni

n1

=0.06025，s=0.2%<0.4%，则：

3

w

N

100%

=

0.0967530.85410

0.1600

14

100%=26.12%

空白滴定 初读数(mL)末读数(mL)V滴定(mL)

0.09 0.28 0.19

n

0.05 0.23 0.18 0.02 0.21 0.19

dV

=0.187，d



ni

dn

i

=

0.0030.0070.003

=0.0043，=2.3%>0.4%

讨论：经标定确定NaOH浓度为0.09675mol/L，后经滴定确定铵态氮含量为26.12%。配置的NaOH标准溶液浓度偏低，原因可能是因为3mol/L NaOH放

置久了，与空气中的CO2反应，造成溶液浓度降低，从从而影响NaOH标准溶液的浓度；而铵态氮的测定则有可能因为滴定不准确或者是由于NaOH溶液的标定有误差，造成结果的不准确。

感谢吴明君老师，感谢四川农业大学生命科学与理学院分析化学实验室！

第四篇：实验报告8-Excel_2010(四)

实验报告8 Excel 电子表格2010(四)

班级 091 学号 201509104 姓名 王晓博

【实验目的】

1.了解Excel的图表类型和图表功能； 2．掌握图表的创建与格式化；

3．理解图表的基本组成及一些选项的作用。

【实验内容和步骤】

完成实践教程第92页4.4.3中的实验并回答下列问题。如何选择不连续的两列数据？

按住ctrl键同时在表格中选中要创建的表格的不连续区域

2如何选择图例的位置以及添加数据标签。

1.右击图标中的图例，从快捷菜单中选择“设置图例格式”命令

2.探出‘设置图例格式对’话框，选择右侧的‘图例位置’区中的其他模式按钮。

3.选中图表，单击‘插入’选项卡/文本/文本框 按钮下方的下拉按钮，在弹出的下拉菜单中选择‘横排文本框’选项，在图表中拖入鼠标，插入文本框。在文本框中输入解释文本‘XX’然后在图表任意位置单击即可

3如何设置图表背景墙和地板格式？如何设置图表区域的渐变填充。

单击图表，点击“布局”中的“背景墙设置”进行设置即可。双击图表区域，出现“设置图表区格式”对话框，点击“填充”-“渐变填充”即可 如何修改图表边框的颜色和样式

右击鼠标，单击绘图模式，选择相应的颜色和样式即可 怎样改变图表的位置和大小。

右击图标中的图例，从弹出的快捷菜单中选择“设置图例样式”在探出的对话框右侧“图列位置”选项区中选择相应的位置和大小。

6、写出柱形图、饼图两种图表类型适用场合。

柱形图：显示一段时期内数据的变化或者描绘各项之间的比较时。饼图：只显示一个数据系列，需要突出某个重要数据项时。

【实验心得与体会】 学会了如何做图表，收获颇丰，感觉自己棒棒嗒。

第五篇：赌徒问题实验报告

赌徒问题实验报告

一、引言

赌徒问题是针对第四章动态规划的练习，同时也是对第三章介绍的贝尔曼方程和强化学习的基本知识的实际应用。两者紧密结合只有充分了解相关内容才能了解实验经过，才能对强化学习的基本问题有所了解。

二、相关知识介绍

1、马尔科夫性：能够保存此状态的来历的方式，称此方式是马尔科夫的。

也就是s',r，和历史的st,at,rt,st1,at1,...,r1,s0,a0来说，st1s',rt1r|st,at,rt,st1,at1,...r1，s0,a0}=Pr{st1s',rt1r|st,at}

Pr{在这种情况下，环境和任务是一体的，也都称为具有马尔可夫性质。

PS：每个状态都是有前一个可能的状态动作对和发生的各个概率计算得来的。

2、值函数：一个策略是每个状态sS以及动作aA(s)到状态s下采取动作a的概率(s,a)的一个映射。通俗地说，在策略下状态s的值记为V(s)，它是从状态s开始并遵循策略的期望回报。对MDP而言，我们可以形式化地定义V(s)为：

kV(s)E{Rt|sts}Ertk1|sts，（3.8）

k0其中E{}表示了agent在遵循策略之后的期望值。而终止状态的值总是0。我们把函数V称为策略的状态值函数（state－value function for policy π）。

类似地，我们定义在策略下状态s中采取动作a的值，记为Q(s,a)，作为在策略从状态s开始，采取动作a的期望回报:

kQ(s,a)E{Rt|sts,ata}Ertk1|sts,ata

（3.9）

k0我们将Q称为策略的动作值函数（action－value function for policy π）。

在强化学习和动态规划中，值函数的基本性质是它们满足一定的递归关系。对任意策略和状态s，在s的值和它可能的后继状态值之间，（3.10）的一致条件成立：

V(s)E{Rt|sts} k

Ertk1|sts

k0

Ert1k0rtk2|sts

k



(s,a)as'as'ak PRss'Ertk2|st1s'，（3.10）

k0ass'ass'ass'(s,a)PRV(s')

其中，动作a是从集合A(s)中得到的，下一状态s'从集合S中得到的，或者是从情节式任务中的S中得到的。等式（3.10）是V的Bellman方程。它表达了一个状态的值和它的后继状态值之间的关系。

公式（3.10）就是贝尔曼方程，而V值就是贝尔曼方程的唯一解。

3、计算值函数：利用动态规划去计算值函数。找到符合Bellman最优方程

的最优值函数V*或Q*，从而得到最优策略。对于所有sS，aA(s)，且s'S，Bellman最优方程如下：

V(s)maxE{rt1V(st1)|sts,ata}

a**

maxas'Pss'[Rss'V(s')]

（4.1）

aa*或

Q(s,a)E{rt1maxQ(st1,a')|sts,ata}

a'**

Ps'ass'[Rss'maxQ(s',a')]

a'a*（4.2）

PS：此方法就是修改贝尔曼方程从而得到V值的近似解。

三、实验过程简介

赌徒问题是一个典型的值迭代问题，值迭代是策略迭代的方法之一。

将贝尔曼最优方程转换成更新规则就可以得到值迭代。除了策略迭备份需要从所有的动作中选出最大动作以外，值迭代更新等同于策略评估更新。当每次扫描过后V的改动很小的时候就可以停止算法。认为V值已经解出。

以下是题目：

一个赌徒利用硬币投掷的反正面结果来赌博。假如投掷结果是硬币的正面朝上，那么他就赢得他所压的赌注，如果是反面朝上，那么他输掉他的赌注。当这个赌徒赢满100美元或者他输掉他所有的钱时，赌博结束。每一轮投掷，赌徒必须取出他资金的一部分作为赌注，赌注金额必须是整数。这个问题可以表述为一个无折扣的、情节式的有穷马尔可夫决策过程。状态就是赌徒所拥有的资金，s{1,2,,99}，动作就是下赌注，a{1,2,,min(s,100s)}。除了赌徒达到100美元的目标而奖赏为＋1以外，其他奖赏均为0。状态－值函数给出每个状态能够获胜的概率。策略就是如何决定每轮取出多少钱去下注。最优策略就是使取得最后胜利的概率最大化。令p代表硬币正面朝上的概率。假如p已知，那么整个问题也就知道了，并且可以得解，比如通过值迭代求解。图4.6就是当p0.4时，值迭代每一轮后值函数的变化情况和得到的最终策略。

以下是算法：

任意初始化V，比如：V(s)0，对于所有sS

Repeat 0



For each sS

vV(s)V(s)maxas'Pss'[Rss'V(s')]aa

max(,|vV(s)|)Until （一个极小的正数）

输出一个确定的策略 (s)argmaxas'Pss'[Rss'V(s')]

aa根据算法和题目的具体要求得到的C++代码如下：

#include //#include

using namespace std;//vector V(99,0);double V[100];

//将V值放在数组中存放，为了方便起见这里V[0]是不使用的！double AF(double S);

//a值的计算函数题目中a是a{1,2,,min(s,100s)} double Q(int S,int a);

//Q(S,a)动作值函数的计算

double RP(double S,double a);//这里P是加法的缩写M是减法的缩写赌徒赌钱可能的情况 double RM(double S,double a);// 为赢钱和输钱两种，+为赢概率0.4，同样输钱为-概率0.6； //=============================== void main(){

for(int i=0;i<100;i++)

//初始化V值为0； { V[i]=0;} double Delta=0.0;

//初始化△=0 double Cta=0.0000000001;

//初始化=0 double i;double K=0;do { for(int S=1;S<=99;S++)

//对于1~99个状态

{

} double v=V[S];

//将V值暂时保存下来

i=AF(S);

//i用来接收计算出来的a值 for(int a=0;a<=i;a++){ K+=Q(S,a);

//贝尔曼最优方程 } V[S]=K;Delta=max(Delta,fabs(v-V[S]));

//计算△

} while(Delta

//当V的变化一定小的时候结束

for(int i=1;i<=99;i++)

//输出最终的V值也就是贝尔曼方程的cout<<“V[”<

//最优解，赌徒问题的最优解。double AF(double S){

} double T;T=min(S,100-S);return T;

double Q(int S,int a){ double RESULT;RESULT=0.4*(RP(S,a)+V[S+a])+0.6*(RM(S,a)+V[S-a]);return RESULT;} //RP,RM判断汇报的值是1还是0.double RP(double S,double a){

} double C=S+a;if(C>=100)return 1.0;else return 0;

double RM(double S,double a){

} double C=S-a;if(C>=100)return 1.0;else return 0;结果显示:

就一个50是对的，我就无语了。。。

V(s)maxas'Pss'[Rss'V(s')]aa 其实这个程序就是实现这个公式，我晕啊检查了几遍

maxas'还没发现问题，还麻烦老师帮忙看看。我知道这样不好，但是真的没招了，感觉这里可能有问题。。。

总结：

通过实验让我更加理解贝尔曼方程，对值函数的计算有了进一步的认识。同时学会了用值迭代的方法求出贝尔曼方程的最优解，对V与Q的关系理解更加深刻。V[S]=S状态下对应不同动作a的所有Q的和。