《商人过河问题》PPT课件

1,商人过河问题,三名商人各带一个随从乘船渡河。现此岸有一小船只能容纳两人，由他们自己划行。若在河的任一岸随从人数比商人多，他们就可能抢劫财物。不过如何乘船渡河的大权由商人们掌握。商人们怎样才能安全过河呢?,问题的提出,2,此类智力问题当然可以通过一番思考，拼凑出一个可行方案来。但是，我们现在希望能找到求解这类问题的规律性、建立数学模型，用以解决更为广泛的问题。,分析,3,此问题可视为一个多步决策问题，每一步就是一次渡河，每次渡河就是一次状态转移。用三维变量(x,y,z)表示状态：x-商人数，y-随从数x,y的取值范围：0，1，2，3z-船z的取值范围：0,1那么安全状态可表示为x=0,3,y=0,1,2,3或x=1,2,y=x这就是此问题的数学模型。,模型建立,4,这样问题要求由(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+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)；,模型求解,5,按照以上规则，求解过程如下：,从(3，2，0)只能到达(3，3，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)出发,(3,3,1)/*不必考虑*/,(3,2,1)/*可取*/,6,如下图所示：,这样可得到所有答案:,7,由此可得到渡河策略:,(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,0),(3,1,0),(1,1,1),(0,2,1),8,状态平面分析法,设x为商人数，y为随从数，在xoy平面上作分析。先标出此岸的安全状态点。起始点-(3，3)，最终点-(0，0)模型求解就是求从状态(3，3)转移到状态(0，0)的方法。用di表示第i次状态转移，i为奇数时：船从此岸到对岸，x,y只能减少，不能增加(即移向左下方)且(x+y)至多减少2，（即至多移两格)i为偶数时：船从对岸到此岸。,模型求解法二,9,例如：d1：(3,3)-(2,2)1个商人1个随从过对岸d1：(3,3)-(3,1)2个随从过对岸,如图所示:,10,(1)若船的情况不变，则2名商人2个随从如何安全渡河？(2)m名商人m个随从(m4)能否安全渡河？,思考,11,(1)(2,2)(1,1)or(2,0)(2,1)(0,1)(1,1)(0,0)如下图：,12,(2)m名商人m个随从(m4)无法安全渡河,如m=4时的图(如下图)，d7就无法作不重复的转移。,13,(1)夫妻过河问题有三对夫妻要过河，船最多可载两人。约束条件是根据法律，任一女子不得在其丈夫不在场的情况下与另外男子在一起，问此时这三对夫妻能否过河?四对夫妻呢(2)人、狗、鸡、