商人过河.doc

商人们怎样安全过河摘要：四名商人各带一名随从乘船渡河，一只小船至多容纳两人，由他们自己制定，随从约定，在河的任一岸，一旦随从的人数比商人多，就杀了越货。但是如何乘船渡河的大权掌握在商人们手中，另外，当船的的容量增大为3，最多可以有几对商人安全过河。商人们怎么才安全渡河，那将再此文中分析过河问题。模型主要通图表法对过河的方案进行举例，然后根据小船的容量和商人们要安全过河为前提对各种方案进行层层筛选，最终得到商人安全过河方案。关键词：多步决策图解法商人过河一、问题重述 四名商人各带一名随从乘船渡河，一只小船至多容纳俩人，由他们自己划行，随从约，在河的任一岸，一旦随从的人数比商人多，就杀了越货。另外，当船的的容量增大为3最多可以有几对商人安全过河但是如何乘船渡河的大权掌握在商人们手中。 现在需要解决的问题如下： 1.四名商人在不被随从谋杀和小船最多能为2人的情况下，商人们将如何安全过河？ 2.如果有m名商人m名随从，小船的容量为3时，最多可以有多少商人各带一名随从过河。二、模型的假设 1.假设过河的过程中不会发生以外事故。 2.假设当随从人数多国商人时，不会改变杀人越货计划。 3.假设所有人最终都必须到达河对岸。三、符号说明第k次渡河前此岸的商人数 , =0,1,2,3,4; 第k次渡河前此岸的随从数 k=1,2, =( ,) 过程的状态 S 允许状态集合S=(x , y)| x=0, y=0,1,2,3,.; x=m, y=0,1,2,3,.; x=y=1,2,3. 第k次渡船上的商人数,=0, 1, 2.; 第k次渡船上的随从数 k=1,2, =( , ) 过程的决策 D 允许决策集合D=(u , v)| u+v=1, 2, .，u, v=0, 1, 2, 状态因决策而改变 状态转移律四、模型分析针对商人们能否安全过河问题，需要选择一种合理的过河方案，对该问题可将看为一个多步决策模型，通过对每一次过河的方案的筛选优化，最终得到商人们全部安全过河。对于每一次的过河过程都看成一个随机决策状态量，通过对允许的状态量的层层5、 模型建立和求解模型构成问题一：四对商仆，一只船最多载两个人 求*D(k=1,2, .n), 使*S, 并按转移律=+(-1)k 由 s1=(4,4)到达 s(n+1)=(0,0).模型求解 图解法状态s=(x,y) , 25个格点 允许状态13个点y允许决策 移动1或2格; k奇,左下移; k偶,右上移x因为至多装2人，所以从（4,4）出发有意义的走法只有（4,4）到（4,2）和（4,4）到（3,3）两法。当为第一种时，回来一个仆人下一步只能到（3,3）此时和第二种一样。这时，若从对岸回来回来一仆人则此岸仆人多于商人不可，若回来一商人则到（4,3）陷于循环如此下去一定过（2,2）此时无论商人或仆人再到此岸都不行。所以无法安全渡河。问题二 ：求解当一只船最多载三个人时，最多可以使多少对商仆平安到达河对岸。当有4个商人和4个仆人的情况第一种解法：d8d7d6d2d5d4y4 3d12d9d31x43210 第一次第二次第三次第四次第五次第六次第七次第八次第九次本岸4商人1仆人4商人2仆人4商人0仆人4商人1仆人1商人1仆人2商人2仆人0商人2仆人0商人3仆人0商人0仆人船上0商人3仆人0商人1仆人0商人3仆人0商人1仆人3商人0仆人1商人1仆人2商人0仆人0商人1仆人0商人3仆人对岸0商人3仆人0商人2仆人0商人4仆人0商人3仆人3商人3仆人2商人2仆人4商人2仆人4商人1仆人4商人4仆人6第一次第二次第三次第四次第五次第六次第七次第八次第九次本岸4商人1仆人4商人2仆人4商人0仆人4商人1仆人1商人1仆人2商人2仆人0商人1仆人0商人2仆人0商人0仆人船上0商人3仆人0商人1仆人0商人3仆人0商人1仆人3商人0仆人1商人1仆人2商人1仆人0商人1仆人0商人2仆人对岸0商人3仆人0商人2仆人0商人4仆人0商人3仆人3商人3仆人2商人2仆人4商人3仆人4商人2仆人4商人4仆人 .当有5个商人各带一名随从过河时的情况：d8d7d6d2d10d5d445y5xd3d1432d913210d113个商人过去，1个商人，1个仆人回来2个仆人过去，1个仆人回来3个仆人过去，1个仆人回来以本岸情况为例：过去3个仆人，回来1个仆人3个商人过去，1个仆人回来（5商人，5仆人）（5商人，3仆人）（5个商人，2个仆人）过去2仆人（3商人，3仆人）(0商人，4仆人）（0商人，2仆人）（0商人，0仆人）经验证，6个商人的情况一定会经过（3,3）此时无论商人还是仆人回来都无法成功。所以在原有条件下最多有5个商人可以满足条件。六、模型推广通过以上模型的建立，若商人和随从人数增加或小船容量加大，考虑n名商人各带一随从的情况。 七 参考文献： 1./link?url=9X84BQnKBALTUjaJqije-QKlF_4TXX5ij4_6qdCrDHJU6NFbGV_jT4pazFhDAEdh9Z0DRoTeoXGPBec4za29CR_7cfQBBTC-3KWnEiD6ke2 ./link?url=9X84BQnKBALTUjaJqije-QKlF_4TXX5ij4_6qdCrDHJU6NFbGnV_jT4pazFhDAEdh9Z0DRoTeoXGPBec4za29CR_7cfQBBTC-3KWnEiD6ke问题三：斗地主摘要： 已知地主手中牌2、K、Q、J、10、9、8、8、6、6、5、5、3、3、3、3、7、7、7、7 长工甲手中牌大王、小王、2、A、K、Q、J、10、Q、J、10、9、8、5、5、4、4 长工乙手中牌2、2、A、A、A、K、K、Q、J、10、9、9、8、6、6、4、4 三家都是明手，互知底牌。要求是：在三家都不打错牌的情况下，地主必须要么输要么赢。 问：哪方会赢？ 提出问题 地主，长工甲和长工乙进行斗地主，已知三人均知道对方手中的牌，三个人都擅长玩斗地主纸牌游戏，不会有打错牌的失误，并且不会出现平局的情况，分析哪方会赢？分析问题 在已知对方和自己手牌的情况下，按照斗地主规则开始出牌。在小组讨论中，一直就是地主输，长工赢，所以在这篇文章中只讨论地主有可能会赢的情况。以坐标和箭头表示出牌的过程，由演示结果判断哪方赢模型假设：1 地主首先发牌2 依次按照地主，甲，乙的出牌顺序 3 没有外界的干扰条件，只有三人在打牌。4三人都会打牌不会乱打。符号说明 以pi表示地主第i次出的牌; 以qi表示长工甲第i次出的牌;以ri表示长工乙第i次出的牌（i=1,2,3，）i=0时表示不出牌。建立模型 p1(55,66,77,88),q0,r0 p2(9,10,11,12,13),q2(10,11,12,13,1),r0p3(3