程序设计基础课件第13章－状态建模－人鬼渡河

课前思考题你认为如下四个例题的求解有共同之处吗？第13章多步决策与状态建模

——人鬼渡河6A0172013.12.09人鬼渡河的规则目标是将东岸的3人3鬼通过一只小船安全转移到西岸，希望以尽可能少的摆渡次数。船的容量有限，一次最多只能坐2人（或2鬼或1人1鬼）。无论是在河的东岸还是在河的西岸，一旦鬼数多于人数，则人被鬼扔到河中。怎样渡河的大权掌握在人的手中。只求一种渡河方案。这类问题如何思考？先看演示发现哪些特点或规律？目标：找一种“方案”，能将人鬼安全摆渡至对岸。方案：一系列“指令”。指令：？？？？？？？

AB

将一个事物，转变成另一个事物。考虑到“计算机”的能力（与特长），指令必须是对“数”的运算（即将一个数转变成为另一个数）。因此，确定“指令”之前，需要确定是哪些“数”在被计算！它们是什么？在“谁做的好事”和“谁是嫌疑犯”这两个问题中，解题的关键是：将自然语言描述的意思，用可以被计算的数学概念表示出来，通过逻辑运算、关系运算等，求解问题的答案。求解过程是采用一种简单的暴力穷举（枚举）法。在“跳马”和“皇后”这两个问题中，解题的关键是：将棋子移动过程转变成坐标平面上运动点的坐标变化，将棋子摆放过程转变为平面上直线的属性变化。求解过程又变成在所有可能的变化中，分步寻找满足要求的变化。这仍然是一种特殊的枚举。对于上面的摆渡过程，可被计算的到底是什么呢？或者说，玩游戏过程中的“操作”，对应的数学上的描述是什么？再或者说：操作过程中所改变的，能用什么数学概念来刻画？归根结底，问题的数学模型是什么？左岸的数量在变化右岸的数量在变化船中的数量在变化船行方向在变化考察变化的量，寻找可算的量争渡，争渡，惊起……两岸人鬼数量的变化是由渡船上的人鬼数量与船的运动方向决定的！A+B+C=

D(3,3)(3,3)(0,0)[0,2]SK+1=SK+∆k人鬼渡河的安全方案记R----人；G----鬼。则每一个渡河中的“右岸场景”都与一个数对（R，G）相对应。右岸所有可能场景（人鬼数），会组成平面上的一个网格。如下所示：

东岸状态图

G30,31,32,33,320,21,22,23,210,11,12,13,10,01,02,03,00123R出发点终点渡河前东岸状态定义用2维向量SK=（RK,GK）定义为第k次渡河前东岸的渡河状态。允许渡河东岸状态集合

S={（R,G）|R=0,G=0,1,2,3;R=3,G=0,1,2,3;R=1,G=1;R=2,G=2;}人鬼渡河的安全方案设K为摆渡行船的次数（序号），从东岸到西岸或从西岸到东岸记1次。显然，船从东到西，K为奇数；船从西到东，K为偶数。摆渡决策定义2维向量dk为第k次行船的摆渡策略。dk=(uk,vk)。其中uk为上船人数，vk为上船鬼数。允许的摆渡策略集合为D

D={（u,v）|u=2,v=0;u=1,v=0;u=1,v=1;u=0,v=1;u=0,v=2;}多步决策问题安全渡河方案为多步决策问题目标：求决策dk

∈D(k=1,2,…n),使状态

Sk

∈S，按照状态转移公式

SK+1=SK+(-1)kdk

由初始状态S1=(3,3)经有限步骤n到达

Sn+1

=(0,0)状态转移公式

SK+1=SK+(-1)kdk

k为偶数

+dkSKSK+1-dkk为奇数编程思路：多步决策，使用状态转移方程（3,3）d1d2d3s1s2s3

从东往西从西往东从东往西

dn-1dnsn-1snsn+1（0,0）从西往东从东往西从东岸状态图分析有3类点是安全的：第1类：3个人在东岸未动，有4个点第2类：3个人已不在东岸，有4个点第3类：人数和鬼数相等，只有两个点

(1,1)-----1人1鬼

(2,2)-----2人2鬼安全渡河要从第1类的4个点转到第2类的4个点，必须经过第3类的2个点。下图画出了这10个点。3个人都在东岸的4个点

G30,31,32,33,33

个

20,21,22,23,2人都

10,11,12,13,1在东

0,01,02,03,0岸

0123R3个人都在西岸的4个点

G330,31,32,33,3

个人20,21,22,23,2

都在10,11,12,13,1

西岸0,01,02,03,00123R人数与鬼数相等的2个点

G30,31,32,33,3

20,21,22,23,2

10,11,12,13,1

0,01,02,03,00123R

不安全的6个点：人数为1或2时与鬼数不等

G30,31,32,33,3

20,21,22,23,2

10,11,12,13,1

0,01,02,03,00123R将安全条件形式化

AQ=(R==3第1类安全点

||R==0第2类安全点

||(R==1)&&(G==1)||(R==2)&&(G==2));

第3类安全点

(人数==鬼数)

安全渡河的关键点

G330,31,32,33,33

个个人20,21,22,23,2人都都在10,11,12,13,1在西东岸0,01,02,03,0岸

0123R为了避免出现重复，让(1,1)与(2,2)各出现一次，

编程时要考虑这一点。

东岸状态图中的安全点与不安全点

G30,31,32,33,320,21,22,23,210,11,12,13,10,01,02,03,00123R

东岸状态图多步决策的出发点

G30,31,32,33,3

多步

20,21,22,23,2决策的结

10,11,12,13,1束点

0,01,02,03,00123R

第1步：2鬼上船西渡，东岸留3人1鬼

G30,31,32,33,3120,21,22,23,210,11,12,13,1

0,01,02,03,00123R

第2步:1鬼返回，东岸有3人2鬼

G230,31,32,33,3120,21,22,23,210,11,12,13,1

0,01,02,03,00123R第3步：2鬼上船西渡，东岸有3人

G230,31,32,33,3120,21,22,23,210,11,12,13,13

0,01,02,03,00123R第4步：1鬼上船东渡，东岸有3人1鬼

G230,31,32,33,3120,21,22,23,210,11,12,13,13

0,01,02,03,001243R第5步：2人上船西渡，东岸有1人1鬼

G230,31,32,33,3120,21,22,23,210,11,12,13,13

0,03,0015243R第6步：1人1鬼上船东渡，东岸有2人2鬼

G6230,31,32,33,3120,21,22,23,210,11,12,13,13

0,03,0015243R第7步：2人上船西渡，东岸有2鬼

G76230,31,32,33,3121,22,23,210,11,12,13,13

0,03,0015243R第8步：1鬼上船东渡，东岸有3鬼

8G76230,31,32,33,3121,22,23,210,11,12,13,13

0,03,0015243R第9步：2鬼上船西渡，东岸有1鬼

8G762930,31,32,33,3121,22,23,210,11,12,13,13

0,03,0015243R第10步：1鬼上船东渡，东岸有2鬼

8G762930,31,32,33,3121,22,23,210,11,12,13,13100,03,0015243R第11步：2鬼上船西渡，东岸空起始状态

8G762930,31,32,33,3121,22,23,210,11,12,13,13104113,0

终止015243R状态：用结构数组来描述structstate//定义名为state的结构{intr;//人数

intg;//鬼数};states[15];//定义结构数组s[1].r=3;

//初始状态东岸有3人s[1].g=3;//初始状态东岸有3鬼摆渡决策用结构数组来描述

stated[7]={{0,0},{0,-2},{-1,-1},{-2,0},

{0,1},{1,1},{1,0}};

i-------决策号

从东往西从西往东

i0123456d[i].r00-1-2011人数

d[i].g0-2-10110鬼数参考程序

#include<iostream>usingnamespacestd;//定义布尔变量，描述状态安全和重复

boolAQ,CHF;voiddisplay(intk);//声明有输出渡河状态函数

//定义描述渡河状态东岸人数与鬼数的结构变量

structstate{ intr;//状态中的人数

intg;//状态中的鬼数

};states[15];//结构数组记录渡河时的状态转移过程//渡河策略stated[7]={{0,0},{0,-2},{-1,-1},{-2,0},{0,1},{1,1},{1,0}};intflag1=0;//东岸尚未达1人1鬼状态标志，预置0

intflag2=0;//东岸尚未达2人2鬼状态标志，预置0intk=0;//初始状态编号：预置为0

intmain()//主函数{//主函数开始

s[1].r=3;//初始状态东岸有3人

s[1].g=3;//初始状态东岸有3鬼

intu=3,v=3;//初始状态东岸有3人3鬼

inta,mu,mv;//临时变量

//目标是东岸无人无鬼，未达目标则循环不已while(!(u==0&&v==0)){

k++;//状态号加1

if(k%2==0)

a=4;//k为偶数表示船东渡，策略号从4开始

else

a=1;//k为奇数表示船西渡，策略号从1开始

//枚举各种渡河决策，看哪个安全for(inti=a;i<=a+2;i++){

//按第i号策略走1步东岸的人数

mu=u