传教士和野人问题实验报告（大全五篇）

第一篇：传教士和野人问题实验报告

1.上机内容 传教士与野人问题求解（宽度搜索算法）

二 二 问题背景：

从前有一条河，河的左岸有 m 个传教士(Missionary)和 m 个野人(Cannibal)，和一艘最多可乘 n 人的小船。约定左岸，右岸和船上或者没有传教士，或者野人数量少于传教士，否则野人会把传教士吃掉。

三 三 实验内容：

编程，接收 m 和 n，搜索一条可让所有的野人和传教士安全渡到右岸的方案，例如下图:（M 表示传教士(Missionary)，C 表示野人(Cannibal)）

初

态

目

标 Left Bank River Right bank

Left Bank River Right bank M….M….C….C….注：本实验的举例均以 3 个传教士和 3 个野人同在左岸作为初始状态。

四 四 实验方案和算法：．数据结构：

本实验需要用到的数据结构主要是队列和堆栈，其实现均包含于 dso.h 头文件中，分别命名为 class stack 和 class queue。2 ． 宽 度搜索算法：

(1)结点结构 ：

class Move {

public:

int missionary;

//要移动的传教士数量

int cannibal;

//野人

};class ElemType : Move {

//继承 Move 类，获得传教士，野人数据成员。

private:

bool boat;

//船是否在左岸？

public:

ElemType* flag;

// 标示前一状态即扩展出本结点的父结点信息

ElemType(int MAX_PEOPLE){

//创建初始状态

missionary = cannibal = MAX_PEOPLE;

boat = true;

flag = NULL;

} ……

在这里，Elemtype 集成了 Move，从而获得 Move 类的传教士和野人数据成员。以上两个类的数据成员用于保存所有扩展生成的结点。其中 missionary 表示表示左岸上传教士的树目，cannibal 表示左岸上野人的树目，boat 表示船在哪个岸上（其中 true 表示在左岸，这是船的初始状态，表示 false 在右岸），flag用于标示前一状态即扩展出本结点的父结点信息，以便最后回搜找出解的 路径。

举例说明：假设左岸有 3 个传教士和 3 个野人，小船最多可乘 2 人。把当前左岸的状态抽象为：(3,3,1)，前两个“3”代表左岸有 3 个传教士和 3 个野人，1 代表船在左岸。很明显，目标状态为(0,0,0),表示左岸的传教士和也人数目都是 0，而船在右岸。

(2)船的行动规则（successor function）: :

把每一次可行的渡船方案作为行动规则，用 Move 类的（m,c）表示。行动规则的两位数分别代表要移动的传教士，野人的数量。对于固定大小的船，其装载能力是一定的，所以它的行动规则空间也是一定的。在这里，用 MoveGroup 类的构造函数构造出所有的行动规则。

注意，这里 MoveGroup 类中的 Move 对象只有 500 的可用空间，所以，输入的传教士和野人数目构成的行动规则不能超过 500 种。

(3)宽度优先算法：

实验的主要搜索算法由 ANSWER 类的构造函数实现，这里主要用到了 OPEN 和 CLOSED 队列，以及一个临时的 TEMP 堆栈。其中，OPEN 表用于存放扩展结点，CLOSED 表用于存放被扩展结点，TEMP 则用于用于记录成功搜索的路径。

搜索过程大致如下描述：先构造初始结点以及船的行动规则，初始结点入 OPEN 队列，以宽度优先依次搜索 OPEN 队列头结点的子结点，同时保存受访问结点的父结点信息，知道搜索到目标结点或者无解为止。

算法框图如下所示：

开始 初始接结点并入 OPEN 队列 OPEN 为空？ OPEN 队列头结点 n 出列，并入 CLOSED 队列 返回 Y N

程序界面 和功能 说明：

程序运行环境为 DOS 控制台，运行开始以后，程序提示输入需要坐船的传教士和野人数目，例如输入 3 表示有 3 个传教士和 3 个野人。

用户按回车键以后，程序继续提示输入船的装载能力，例如输入 2 表示这个船依次最多可以坐 2 人。注：一般情况下，船的装载能力应该少于传教士或野人的数量，而且一般为偶数。

程序 开始运行时的 界面截图：

程序 运行结束时的 界面截图：

把结点的子结点并入 OPEN队列，保存父结点 被扩展结点还有子结点吗？ 返回

Y N

输出文件示例：

Left(3, 3)|(0, 0)Right [Step 1]

Move 0 missionaries and 2 cannibals to the right side.Left(3, 1)|(0, 2)Right [Step 2]

Move 0 missionaries and 1 cannibals to the left side.Left(3, 2)|(0, 1)Right [Step 3]

Move 0 missionaries and 2 cannibals to the right side.Left(3, 0)|(0, 3)Right [Step 4]

Move 0 missionaries and 1 cannibals to the left side.Left(3, 1)|(0, 2)Right [Step 5]

Move 2 missionaries and 0 cannibals to the right side.Left(1, 1)|(2, 2)Right [Step 6]

Move 1 missionaries and 1 cannibals to the left side.Left(2, 2)|(1, 1)Right [Step 7]

Move 2 missionaries and 0 cannibals to the right side.Left(0, 2)|(3, 1)Right [Step 8]

Move 0 missionaries and 1 cannibals to the left side.Left(0, 3)|(3, 0)Right [Step 9]

Move 0 missionaries and 2 cannibals to the right side.Left(0, 1)|(3, 2)Right [Step 10]

Move 0 missionaries and 1 cannibals to the left side.Left(0, 2)|(3, 1)Right [Step 11]

Move 0 missionaries and 2 cannibals to the right side.Left(0, 0)|(3, 3)Right OK!错误说明：

（1）

关于有没有解的问题：由于传教士和野人问题是一个真实的问题，来到岸边的传教士和野人数目与船的装载能力都是随机的，所以某些特定情况下，要以一定规则把人都运到船的对岸是没有解的，例如假设有 10 个传教士和 10 个野人，船一次最多能够装 2 人，这时候是不能把人都运到对岸的，这时候程序会提示：There may not be any way to transport these guys.（2）

关于运行时间的问题：本实验使用宽度优先搜索算法，但并没有进行优化，所以有时候程序虽然确实有解，但是由于算法的效率确实很低，造成的时间上的开销有时候可能会比起喝一杯咖啡的时间还要长，这时候程序会提示：

Please wait patiently。Working...六 六 心得体会：

这个是我们小组的第一个实验，由于经验以及能力有限，所以算法上比较简单，只用了一个宽度优先搜索算法，但毕竟能够成功找出解，虽然效率较低。经过一些测试数据的测试以后，发现了宽度优先搜索算法虽然必能找到最优解（有时候无解），但效率真的很低，如我们提供的那个测试数据（50 个传教士，50 个野人，船最多能坐 4 人），虽然能解，但也花费了 75 秒多的时间才能找出解，可见优化算法的必要。

第二篇：实验报告五 生产者和消费者问题

实验报告五

——生产者和消费者问题

姓名：丛菲 学号：20100830205 班级：信息安全二班

一、实习内容

• •

1、模拟操作系统中进程同步和互斥

2、实现生产者和消费者问题的算法实现

二、实习目的

• • • • •

1、熟悉临界资源、信号量及PV操作的定义与物理意义

2、了解进程通信的方法

3、掌握进程互斥与进程同步的相关知识

4、掌握用信号量机制解决进程之间的同步与互斥问题

5、实现生产者－消费者问题，深刻理解进程同步问题

三、实习题目

• 在Linux操作系统下用C实现经典同步问题：生产者—消费者，具体要求如下：

(1)一个大小为10的缓冲区，初始状态为空。

(2)2个生产者，随机等待一段时间，往缓冲区中添加数据，若缓冲区已满，等待消费者取走数据之后再添加，重复10次。

(3)2个消费者，随机等待一段时间，从缓冲区中读取数据，若缓冲区为空，等待生产者添加数据之后再读取，重复10次。• 提示

本实验的主要目的是模拟操作系统中进程同步和互斥。在系统进程并发执行异步推进的过程中，由于资源共享和进程间合作而造成进程间相互制约。进程间的相互制约有两种不同的方式。

（1）间接制约。这是由于多个进程共享同一资源（如CPU、共享输入/输出设备）而引起的，即共享资源的多个进程因系统协调使用资源而相互制约。

（2）直接制约。只是由于进程合作中各个进程为完成同一任务而造成的，即并发进程各自的执行结果互为对方的执行条件，从而限制各个进程的执行速度。

生产者和消费者是经典的进程同步问题，在这个问题中，生产者不断的向缓冲区中写入数据，而消费者则从缓冲区中读取数据。生产者进程和消费者对缓冲区的操作是互斥，即当前只能有一个进程对这个缓冲区进行操作，生产者进入操作缓冲区之前，先要看缓冲区是否已满，如果缓冲区已满，则它必须等待消费者进程将数据取出才能写入数据，同样的，消费者进程从缓冲区读取数据之前，也要判断缓冲区是否为空，如果为空，则必须等待生产者进程写入数据才能读取数据。

在本实验中，进程之间要进行通信来操作同一缓冲区。一般来说，进程间的通信根据通信内容可以划分为两种：即控制信息的传送与大批量数据传送。有时，也把进程间控制在本实验中，进程之间要进行通信来操作同一缓冲区。一般来说，进程间的通信根据通信内容可以划分为两种：即控制信息的传送与大批量数据传送。有时，也把进程间控制信息的交换称为低级通信，而把进程间大批量数据的交换称为高级通信。

目前，计算机系统中用得比较普遍的高级通信机制可分为3大类：共享存储器系统、消息传递系统及管道通信系统。

• 共享存储器系统

共享存储器系统为了传送大量数据，在存储器中划出一块共享存储区，诸进程可通过对共享存储区进行读数据或写数据以实现通信。进程在通信之前，向系统申请共享存储区中的一个分区，并为它指定一个分区关键字。信息的交换称为低级通信，而把进程间大批量数据的交换称为高级通信。

目前，计算机系统中用得比较普遍的高级通信机制可分为3大类：共享存储器系统、消息传递系统及管道通信系统。

• 消息传递系统

在消息传递系统中，进程间的数据交换以消息为单位，在计算机网络中被称为报文。消息传递系统的实现方式又可以分为以下两种：(1)直接通信方式

发送进程可将消息直接发送给接收进程，即将消息挂在接收进程的消息缓冲队列上，而接收进程可从自己的消息缓冲队列中取得消息。(2)间接通信方式

发送进程将消息发送到指定的信箱中，而接收进程从信箱中取得消息。这种通信方式又称信箱通信方式，被广泛地应用于计算机网络中。相应地，该消息传递系统被称为电子邮件系统。

• 管道通信系统

向管道提供输入的发送进程，以字符流方式将大量的数据送入管道，而接收进程从管道中接收数据。由于发送进程和接收进程是利用管道进行通信的，故称为管道通信。为了协调发送和接收双方的通信，管道通信机制必须提供以下3方面的协调功能。（1）互斥

当一个进程正在对pipe文件进行读或写操作时，另一个进程必须等待。（2）同步

当写进程把一定数量的数据写入pipe文件后，便阻塞等待，直到读进程取走数据后，再把写进程唤醒。

（3）确认对方是否存在 只有确定对方已存在时，才能进行管道通信，否则会造成因对方不存在而无限制地等待。在这个问题当中，我们采用信号量机制进行进程之间的通信，设置两个信号量，空的信号量和满的信号量。在Linux系统中，一个或多个信号量构成一个信号量集合。使用信号量机制可以实现进程之间的同步和互斥，允许并发进程一次对一组信号量进行相同或不同的操作。每个P、V操作不限于减1或加1，而是可以加减任何整数。在进程终止时，系统可根据需要自动消除所有被进程操作过的信号量的影响

1．缓冲区采用循环队列表示，利用头、尾指针来存放、读取数据，以及判断队列是否为空。缓冲区中数组大小为10；

2．利用随机函数rand()得到A～Z的一个随机字符，作为生产者每次生产的数据，存放到缓冲区中；

3.使用shmget()系统调用实现共享主存段的创建，shmget()返回共享内存区的ID。对于已经申请到的共享段，进程需把它附加到自己的虚拟空间中才能对其进行读写。

4.信号量的建立采用semget()函数，同时建立信号量的数量。在信号量建立后，调用semctl()对信号量进行初始化，例如本实习中，可以建立两个信号量SEM_EMPTY、SEM_FULL，初始化时设置SEM_EMPTY为10，SEM_FULL为0。使用操 作信号的函数semop()做排除式操作，使用这个函数防止对共享内存的同时操作。对共享内存操作完毕后采用shmctl()函数撤销共享内存段。

5.使用循环，创建2个生产者以及2个消费者，采用函数fork()创建一个新的进程。6．一个进程的一次操作完成后，采用函数fflush()刷新缓冲区。7．程序最后使用semctl()函数释放内存。模拟程序的程序流程图如下所示： 1.主程序流程图：

2.生产者进程流程图

3.消费者进程流程图

4.P操作流程图

5.V操作流程图

四、实现代码为：

// exet5.cpp //#include “stdafx.h” #include #include #define mSIZE 3 #define pSIZE 20 staticintmemery[mSIZE] = {0};staticint process[pSIZE] = {0};//static int process[pSIZE] = {2,3,2,1,5,2,4,5,3,2,5,2};//static int process[pSIZE]

= {7,10,1,2,10,3,10,4,2,3,10,3,2,1,2,10,1,7,10,1};void build();void LRU();

int main(intargc, char *argv[]){ printf(“Random sequence is as follows:n”);build();printf(“nInvoking LRU Algorithn: n”);LRU();return 0;}

void build(){ inti = 0;for(i=0;i

{ process[i] =(int)(10.0*rand()/(RAND_MAX));printf(“%d ”,process[i]);

} printf(“n”);}

void LRU(){ int flag[mSIZE] = {0};inti = 0, j = 0;int m =-1, n =-1;int max =-1,maxflag = 0;int count = 0;for(i = 0;i

//Find the first free Physical Block

for(j=0;j

{

if(memery[j] == 0)

{

m = j;break;

}

}

//Find if there are same processes for(j = 0;j

{

if(memery[j] == process[i])

{

n = j;

}

}

//Find free PB for(j = 0;j

{

if(flag[j]>maxflag)

{

maxflag = flag[j];max = j;

}

}

if(n ==-1)// Find no same process

{

if(m!=-1)// find free PB

{

memery[m] = process[i];flag[m] = 0;for(j = 0;j <= m;j++)

{ flag[j]++;

}

m =-1;

}

else //NO find free PB

{

memery[max] = process[i];flag[max] = 0;

for(j = 0;j

{ flag[j]++;

} max =-1;maxflag = 0;count++;

}

} else // Find same process

{ memery[n] = process[i];flag[n] = 0;if(m!=-1)//find free PB

{ flag[m] = 0;

} for(j = 0;j

{ flag[j]++;

} max =-1;maxflag = 0;

n =-1;

}

for(j = 0;j

{

printf(“%d ”,memery[j]);

} printf(“n”);}

printf(“nThe is: %dn”,count);}

times

of

page

conversion

五、在虚拟机上的具体操作及结果

执行exe5.c文件

选择ApplicationsAcecessoriesTerminal,执行文件：

依次预处理编译汇编连接执行用文件，编译通过之后-o执行。报错！！错误显示为很多头文件没有预定义。连续查找之后得知原因是链接不上pthread库

在执行命令后面加上-pthread，即新命令格式为：gcc-oexe5exe5.c–lpthread，重新执行后的结果显示如下截图：

其中1表示缓冲区被生产者producer1或者二producer2写入了Item，0表示没有写入数据或者被消费者consumer1或者consumer2消耗掉

六、实验总结及思考

1、本次实验是关于生产者与消费者之间互斥和同步的问题。问题的是指是P、V操作，实验设一个共享缓冲区，生产者和消费者互斥的使用，当一个线程使用缓冲区的时候，另一个让其等待直到前一个线程释放缓冲区为止。

2、实验中包含的知识点很多，包括临界区资源共享问题、信号量定义、PV操作流程、进程间的通信方式（消息传递和共享内存）、进程同步和互斥、信号量机制解决进程之间的同步与互斥问题等等。加深了对于本部分内容的理解

通过本实验设计，我们对操作系统的P、V进一步的认识，深入的了解P、V操作的实质和其重要性。课本的理论知识进一步阐述了现实中的实际问题。

第三篇：新教传教士和近代术语的传播

新教传教士和近代术语的传播

作者：余冬林 《光明日报》（2015年09月05日 04版）

近代术语是中国各学科赖以构建的基石。它既是鸦片战争以来西学东渐的产物，又为中国学术从传统四部之学向近代七科之学演进奠定了基础。1807年9月，英国传教士马礼逊抵达广州，由此揭开以新教传教士为主角的新一轮西学东渐的序幕。此后，西方诸国新教传教士相继来华，在近代术语的生成和传播中发挥了重要作用。从近代术语的变迁中，我们也不难窥见近代以来中西文化冲突与融合的历史状貌。

马礼逊初抵广州时，由于清政府厉行禁教政策，使其不敢公开露面，更不用说进行宗教布道和文化传播。“广州高度警惕的清朝官员在禁止中国人信仰这一外来宗教方面做得要比禁止鸦片流入成功得多。显然，他们认为宣扬外国教义远比单纯售卖药物危险。”（费正清：《新教传教士著作在中国文化史上的地位》）第二次鸦片战争后，禁教令虽然被解除，但新教传教士很快发现传教依然步履维艰，不仅因为儒释道文化与基督教文化的不相容，而且人们往往把传教士与殖民侵略联系起来。要改变这种状况和中国人心目中的“蛮夷”形象，新教传教士开始了近一个世纪的文化传播活动。需要指出的是，不仅当时的中国人不理解这些新教传教士，甚至一些西方人对他们也颇有微词，如扬州教案发生后，时任英国驻上海领事麦华佗认为传教士是“一群不切实际、惹事生非的神经质”。

当时，曾有西方人云：“中国语言文字最难为西人所通，即通之亦难将西书之精奥译至中国。盖中国文字最古最生而最硬，若以之译泰西格致（物理、化学等自然科学的总称）与制造等事，几成笑谈。”（傅兰雅：《江南制造总局翻译西书事略》）。英国传教士傅兰雅虽然对此不以为然，但是依然要面对中西语言文化的巨大鸿沟。此外，近代西方自然科学门类和名目繁多，而在中国其学其名几乎都没有，因此，此类术语的翻译更为困难。对于术语的翻译，傅兰雅等提出了著名的译名三原则：“沿用中文已有之名、设立新名、编辑中西名词字汇”。其中创设新名采用三种方法：一是以平常字加偏旁作为新字，仍读本音，如镁、矽等，或以不常用字释以新义为新名，如铂、钾、锌等；二是数个字解释某物作为新名，并以字数少为妙，如“养气”“轻气”“火轮船”等；三是音译，以官音为主，凡以前译书已惯用者则袭之（参见傅兰雅：《江南制造总局翻译西书事略》）。

受到中国上层敌视的新教传教士转而致力于在普通民众和下层知识分子中开展活动。“那些在1842年前被禁止布道并因此而总要躲避一段时间的新教先驱们不得不借助于书面文字。这与相信铅印经典只要能到达普通民众的手里就具有巨大效力这一最早的传道信念相契合。中国的现实条件则强化了这种写作偏好。”（费正清：《新教传教士著作在中国文化史上的地位》）因此，新教传教士主要通过编纂英汉字典、编写教科书、创办报刊、译述汉文西书等渠道来传播西学和近代术语亦在情理之中。

编纂英汉字典。为解决语言障碍问题，19世纪20年代以来，入华新教传教士相继编纂、出版了多种英汉字典，如马礼逊的《英华字典》、卫三畏的《英华韵府历阶》等。这些字典大都问世于西学大规模涌入之前，一批政治类新术语如自由、国会、内阁等，自然知识类如阳极、蛋白质、分子等应运而生。马礼逊及后继者在英华字典中厘定的术语，“不仅在中国传播开来，构成中国近代新词的重要组成部分，而且麦都思、罗存德等的辞典东传幕末、明治间的日本，被日本各种英和、和英辞典所借鉴。”（冯天瑜：《新语探源——中西日文化互动与近代汉字术语生成》）

编写教科书。新教传教士为拓展传教事业，纷纷以兴办学校作为主要手段。因中西知识体系的差异，新式学校往往会面临教科书匮乏的困境。为解决这一问题，1895年之前，新教传教士充当了教科书编写者的角色。早期来华的传教士几乎都有过单独编写教科书的经历，如英国传教士理雅各为英华书院编写了《智环启蒙塾课初步》等教科书。为克服编辑教科书中的困难而加强合作，他们于1877年组建了“益智书会”，专门负责编辑、出版教科书。益智书会总计出版数学、天文、地理、化学、心理、历史、哲学等各科教科书共98种，20余万册，销往全国各地。此外，还有墨海书馆、美华书馆、上海土山湾印书馆等传教士出版机构与团体参与了清末教科书的编辑。教科书因其权威性和受众的广泛性，在近代术语的厘定和传播中发挥了重要作用，很多术语因出现在教科书中更容易获得人们的认可。

创办报刊。由于清政府的限制，传教士入华之初只能在广州、澳门以及东南亚一带进行传教活动。近代第一份中文报刊《察世俗每月统记传》，就是由英国伦敦布道会传教士米怜于1815年8月在马六甲创办刊行的。该刊以传播基督教教义为主，兼及介绍西方地理、历史、天文等知识。其中宗教术语的厘定，多沿用早期汉文西书中的译词，如圣经、灵魂、耶稣等，但一些天文学术语的翻译如行星等已有不同。中国境内出现的第一份中文刊物，是普鲁士传教士郭实腊在广州创办的《东西洋考每月统记传》（1833—1835年在广州，1837—1838年迁往新加坡）。该刊沿用和创译了一批近代以来具有重要影响的学科术语，如赤道、经纬线、国会、文艺复兴等。此外，新教传教士创办的报刊还有《遐迩贯珍》《中外新报》《六合丛谈》《万国公报》等。传教士创办的中文报刊为吸引中国读者也兼载部分非宗教性的内容，有的在后来的发展中演变为传播西学的综合性报刊如《六合丛谈》等，或成为知识性专刊如《格致汇编》等，其中厘定的学科术语甚多，涉及地理、政法、经济、教育诸领域。

译述汉文西书。新教传教士还与中国士人合作，进行了规模空前的西学译介工作。明清之际由耶稣会士与中国士人合作著译介绍西学的汉文书籍称为“早期汉文西书”；清末入华新教传教士著译或传教士与中国士人合作著译的介绍西学的汉文书籍称“晚期汉文西书”。概而言之，晚期汉文西书涉及“神理之学”（哲学）、“人生当然之理”（社会科学）、“物理之学”（自然科学）诸部类。（冯天瑜：《新语探源：中西日文化互动与近代汉字术语生成》）据1886年艾约瑟的《西学略述》，可大致得知当时西学所涵盖的具体学科和门类，主要包括婴幼儿教育、方言（包括印度、欧洲各国方言等）、教会、文学、理学等。据初步统计，自1811年英国传教士马礼逊出版第一本汉文西书，至1911年辛亥革命结束清政府统治，译出的西学书籍至少在2000种以上（熊月之：《西学东渐与晚清社会》）。在这些汉文西书中，新教传教士和中国士人共同努力借用或创制了涵盖各学科领域的大批术语。这些汉文西书术语对近代中国的维新运动等产生了深远影响。

在清政府学部编订名词馆出现以前，推动清末术语统一的主要机构是益智书会与博医会等民间机构。1890年益智书会在术语统一上已有较大进展，最突出的成果就是由傅兰雅负责的《译者手册》全部完成。1904年，狄考文、赫士等负责编纂的《术语辞汇》正式出版，这是对益智书会自成立以来在统一术语方面所做工作的一个全面总结。《术语辞汇》共收录1.2万个英文术语和大约1.8万个相对应的中文术语，涉及微积分、地质学、地理学、天文学、心理学、国际法、神学等50余种门类。博医会则编纂出版了《英汉医学词典》和《医学字典》等多种医学术语词典。这些机构编辑的术语译名表、术语辞典以及术语命名的原则等，对后来中国术语统一工作的开展有重要的借鉴与参考价值，其中的一些术语译名也一直沿用至今。不过，虽然傅兰雅等制定了术语翻译的三原则，但遗憾的是当时新教传教士在从事译介活动时大都并未遵循这些原则，如合信、玛高温、伟烈亚力等都按照各自原则译制新术语，使术语混乱问题并未真正解决。同时文化传播自有其规律，不以传播者的主观意志为转移，新教传教士所译介的政治、经济、科技等术语及相关知识观念，不但没有成为近代中国人膜拜上帝的心理依据和根基，反而成了他们抨击西方侵略的武器，开眼看世界的中国人在接受西学新知的基础上开始以更为宏阔的眼光勾勒中国的未来蓝图。

（作者单位：武汉轻工大学艺术与传媒学院）

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

赌徒问题实验报告

一、引言

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

二、相关知识介绍

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的和。

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

人工智能——四皇后问题

一、问题描述

四皇后问题

一个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皇后如何求解），更引起我对学习人工智能这门课程的积极性。