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