实验1__怎样安全过河问题

1、实验1 怎样安全过河问题,一、问题,二、实验目的,三、预备知识,四、实验内容与要求,五、思考问题,一、问题 3名商人各带1名随从乘船渡河，一只小船只能容纳2人，由他们自己划行。随从们密约，在河的任一岸，一旦随从人数比商人多，就杀商人。此密约被商人知道，如何乘船渡河的大权掌握在商人们手中，商人们怎样安排每次乘船方案，才能安全渡河呢,二、实验目的 1、使学生进一步巩固和理解向量的定义、运算规则、多步决策理论、状态空间图及其应用。 2、增强编程知识和数学软件的应用,三、预备知识 1、向量定义及运算，多步决策理论，状态空间图。 2、熟悉Mathematica、 Matlab等数学工具,四、实验内容与要

2、求 建立起商人安全渡河的数学模型，并给出商人们如何安全渡河的一个或多个方案，使得渡河的次数尽量少,五、思考问题 在上述的约束条件下，若商人有4名时，问商人们是否能实现安全渡河？更一般地，若商人数是m，小船最多 只能坐n（1nm人，m和n有何关系时，商人们才能实现安全渡河,解题思路,2、状态空间,1、多步决策,一、问题分析与建立模型 由于这个问题已经理想化了，所以不必再作假设。这个问题可以看作一个多步决策的过程。设第k次渡河前此岸的商人数为XK，随从数为YK，k=1,2,。XK，YK=0,1,2,3。将二维向量SK=( XK,YK)定义为状态。安全渡河条件下的状态集合称为允许状态集合，记为S，则

3、 S=(x,y)|x=0或3,y=0,1,2,3;x=y=1,2 (1) 又设第k次渡船上的商人数为UK，随从数为VK，将二维向量DK=(UK,VK)定义为决策,则允许决策集合为: D=(u,v)|u+v=1,2 （2,因为k为奇数时船从此岸驶向彼岸，k为偶数时船由彼岸驶回此岸，所以状态SK随着决策DK变化的规律即状态转移规律是： SK+1=SK+（1）KDK （3） 这样，制定安全渡河方案归结为如下的多步决策问题： 求决策DKD（k=1，2，n），使SKS按照转移律（3），由初始状态S1=（3，3）经有限步（设为n）到达状态Sn+1=（0，0,二、计算过程 下面通过Mathematica的程

4、序给出这个多步决策问题的一个解，同时满足了渡河次数尽量少的条件。 a1=0,0;a2=0,1;a3=0,2;a4=0,3;a5=3,0; a6=3,1;a7=3,2;a8=3,3;a9=1,1;a10=2,2; (*以上两行表示给出十个允许的状态.而1,0,1,2,1,3,2,0,2,1,2,3六种状态是不可能出现的。*) d1=0,2;d2=2,0;d3=1,1;d4=0,1; d5=1,0; (*此行表示给出五个允许的状态，而0,0,1,2,2,1,2,2是不可能出现的*,i=1;j=1;k=1;s0=s1=3,3;Print“此岸船上对岸”； DO DOsi+1=si+(-1)idj;

5、t=0; DOifsi+1=ak;t=1k,1,10; ift=0,Continue; （*以上三行是保证状态属于允许的状态*） l=Modi+1,2;m=l;u=0; ifi+1=3, DOIfsi+1=sm,u=1,Break,m,l,i-1,2 ; ifu=0,ci+1=dj;Break （*以上五行是保证状态不重复以满足渡河的次数尽量少*） ,j,1,5; Ift=0,PrintNo Result;Break; bi+1=3,3si+1; Printsi,”,ci+1,”,bi+1; Ifsi+1=0,0,Break ,i,1,12,j,1,5; Ift=0,PrintNo Resul

6、t;Break; bi+1=3,3si+1; Printsi,”,ci+1,”,bi+1; Ifsi+1=0,0,Break ,i,1,12,程序运算结果如下： 此岸 船上 对岸 3,3 0,2 0,2 3,1 0,1 0,1 3,2 0,2 0,3 3,0 0,1 0,2 3,1 2,0 2,2 1,1 1,1 1,1 2,2 2,0 3,1 0,2 0,1 3,0 0,3 0,2 3,2 0,1 0,1 3,1 0,2 0,2 3,3,三、结果分析 1 上述程序中五个允许的决策或十个允许的状态顺序进行整时，可以得到不同的结果。例如把d1=0，2，d3=1，1调整成d1=1，1，d3=0，2

7、就会得到安全渡河的另一个方案。需要注意的是进行调整时也可能得不到安全渡河的方案。 2该模型求解方法有多种，例如可以利用动态规划的方法来求解，也可以利用图解的方法来求解。 3 这种适当设置状态和决策，并确定状态转移规律是有效地解决很广泛的一类问题的建模方法。 4. 不易找到所有的解,可以得出经过11步的渡河就能达到安全渡河的目标及满足渡河次数尽量少的条件。这11步的渡河方案就是上面程序运行结果中船上下面的那一列。渡河的整个过程如下所示,设N和K分别表示商人数目和随从数目，如下图所示，图中L和R表示左岸和右岸,B,有船 无船,ST. MC M+C2,1、三维向量表示，即 （ML，CL，BL），其中

8、 0ML，CL3 ，BL0,1 此时问题描述简化为 （3，3，1） （0，0，0） 状态空间的总状态数为442=32，根据约束条件的要求，可以看出只有20个合法状态。再进一步分析后,又发现有4个合法状态是不可能达到的。因此实际的状态空间仅由16个状态构成。下表列出分析结果： （0，0，1）达不到 （0，1，1） （0，2，1） （0，3，1） （1，0，1）不合法 （1，1，1） （1，2，1）不合法 （1，3，1）不合法 （2，0，1）不合法 （2，1，1）不合法 （2，2，1） （2，3，1）不合法 （3，0，1）达不到 （3，1，1） （3，2，1） （3，3，1） （0，0，0） （0

9、，1，0） （0，2，0） （0，3，0）达不到 （1，0，0）不合法 （1，1，0） （1，2，0）不合法 （1，3，0）不合法 （2，0，0）不合法 （2，1，0）不合法 （2，2，0） （2，3，0）不合法 （3，0，0） （3，1，0） （3，2，0） （3，3，0）达不到,2、规则集合：由摆渡操作组成。该问题主要有两种操作：pmc操作（规定为从左岸划向右岸）和qmc操作（从右岸划向左岸）。每次摆渡操作，船上人数有五种组合，因而组成有10条规则的集合。 if（ML，CL，BL=1） then （ML-1，CL，BL-1） P10操作 if（ML，CL，BL=1） then （ML，CL

10、-1，BL-1） P01操作 if（ML，CL，BL=1） then （ML-1，CL-1，BL-1）P11操作 if（ML，CL，BL=1） then （ML-2，CL，BL-1） P20操作 if（ML，CL，BL=1） then （ML，CL-2，BL-1） P02操作 if（ML，CL，BL=0） then （ML+1，CL，BL+1） q10操作 if（ML，CL，BL=0） then （ML，CL+1，BL+1） q01操作 if（ML，CL，BL=0） then （ML+1，CL+1，BL+1）q11操作 if（ML，CL，BL=0） then （ML+2，CL，BL+1） q20操作 if（ML，CL，BL=0） then （ML，CL+2，BL+1） q02操作,3、状态空间图求解,3，3，1,2，2，0,3，1，0,3，2，0,3，2，1,3，0，0,3，1，1,1，1，0,2，2，1,0，2，0,0，3，1,0，1，0,3，3，1,0，0，0,3，3，1,0，1，1,4、结果分析 状态空间图是一个有向图，其节点可表示问题的各种状态，节点之间的弧线代表一些操作，它们可把一种状态导向另一种状态。这样建立起来的状态空间图描述了问题所有可能出现