《商人过河问题ppt课件》由会员分享，可在线阅读，更多相关《商人过河问题ppt课件（13页珍藏版）》请在金锄头文库上搜索。
1、商人过河问题商人过河问题三名商人各带一个随从乘船渡河。现此岸有一小船只能包容两人，由他们本人划行。假设在河的任一岸随从人数比商人多，他们就能够抢劫财物。不过如何乘船渡河的大权由商人们掌握。商人们怎样才干平安过河呢?问题的提出的提出此类智力问题当然可以经过一番思索，拼凑出一个可行方案来。但是，我们如今希望能找到求解这类问题的规律性、建立数学模型，用以处理更为广泛的问题。分析分析此问题可视为一个多步决策问题，每一步就是一次渡河，每次渡河就是一次形状转移。用三维变量(x,y,z)表示形状：x-商人数，y-随从数x,y的取值范围：0，1，2，3z-船z的取值范围：0,1那么平安形状可表示为x=0,3,
2、y=0,1,2,3或x=1,2,y=x这就是此问题的数学模型。(3,3,1)(3,2,1)(3,1,1)(2,2,1)(3,0,1)(0,3,1)(0,2,1)(1,1,1)(0,1,1)(3,2,0)(3,1,0)(2,2,0)(3,0,0)(0,3,0)(0,2,0)(1,1,0)(0,1,0)(0,0,0)模型建立模型建立这样问题要求由(3，3，1)变到(0，0，0)的一条道路。根据题意，形状转移时要满足一定的规那么：1.Z从1变为0与从0变为1交替进展；2.当Z从1变为0时，即船从此岸到对岸，此岸人数减少1或2个；即(x,y,1)(u,v,0)时,ux,vy,u+v=x+y-1oru+
3、v=x+y-23.当Z从0变为1时，即船从对岸到此岸，此岸人数增加1或2个；即(x,y,0)(u,v,1)时,ux,vy,u+v=x+y+1oru+v=x+y+24.不反复已出现过的形状，如(3,3,1)(3,1,0)(3,3,1)；模型求解模型求解按照以上规那么，求解过程如下：从从(3(3，2 2，0)0)只能到达只能到达(3(3，3 3，1)/*1)/*不用思索不用思索*/*/从(3,3,1)出发(3,2,0)(3,1,0)如右图(2,2,0)(3,3,1)(3,2,0)(3,1,0)(2,2,0)从(3,1,0)出发(3,3,1) /*不用思索*/(3,2,1)/*可取*/从(2,2,0
4、)出发(3,3,1) /*不用思索*/(3,2,1)/*可取*/如以下图所示：如以下图所示：这样可得到一切答案这样可得到一切答案: : 由此可得到渡河战略由此可得到渡河战略: :(3,3,1) (3,2,1)(3,0,0)(3,1,1)(1,1,0)(3,3,1) (3,2,1)(3,0,0)(3,1,1)(1,1,0)(2,2,1)(0,2,0)(0,3,1)(0,1,0) (0,0,0)(2,2,1)(0,2,0)(0,3,1)(0,1,0) (0,0,0)(2,2,0)(2,2,0)(3,1,0)(3,1,0)(1,1,1)(1,1,1)(0,2,1)(0,2,1)形状平面分析法设x为商
5、人数，y为随从数，在xoy平面上作分析。先标出此岸的平安形状点。起始点-(3，3)，最终点-(0，0)模型求解就是求从形状(3，3)转移到形状(0，0)的方法。用di表示第i次形状转移，i为奇数时：船从此岸到对岸，x,y只能减少，不能添加(即移向左下方)且(x+y)至多减少2，即至多移两格)i为偶数时：船从对岸到此岸。模型求解法二模型求解法二例如：d1：(3,3)-(2,2)1个商人1个随从过对岸d1：(3,3)-(3,1)2个随从过对岸如下如下图图: :(1)假设船的情况不变，那么2名商人2个随从如何平安渡河？(2)m名商人m个随从(m4)能否平安渡河？思思 考考(1)(2,2)(1,1)o
6、r(2,0)(2,1)(0,1)(1,1)(0,0)如以下图：(2)m名商人m个随从(m4)无法平安渡河,如m=4时的图(如以下图)，d7就无法作不反复的转移。(1)夫妻夫妻过过河河问题问题有三有三对对夫妻要夫妻要过过河，船最多可河，船最多可载载两人。两人。约约束条件是根据法律，任一女子不得在其束条件是根据法律，任一女子不得在其丈夫不在丈夫不在场场的情况下与另外男子在一同，的情况下与另外男子在一同，问问此此时这时这三三对对夫妻能否夫妻能否过过河河?四四对对夫妻呢夫妻呢(2)人、狗、人、狗、鸡鸡、米、米过过河河问题问题某人要某人要带带一条狗、一只一条狗、一只鸡鸡、一、一箩箩米米过过河，河，但小船除需求人划外，最多只能但小船除需求人划外，最多只能载载一物一物过过河，河，而当人不在而当人不在场时场时，狗要咬，狗要咬鸡鸡、鸡鸡要吃米。要吃米。问问此人此人应应如何如何过过河河?探探 索索
