《商人过河问题》.ppt

该【《商人过河问题》 】是由【相惜】上传分享，文档一共【13】页，该文档可以免费在线阅读，需要了解更多关于【《商人过河问题》 】的内容，可以使用淘豆网的站内搜索功能，选择自己适合的文档，以下文字是截取该文章内的部分文字，如需要获得完整电子版，请下载此文档到您的设备，方便您编辑和打印。商人过河问题三名商人各带一个随从乘船渡河。现此岸有一小船只能容纳两人,由他们自己划行。假设在河的任一岸随从人数比商人多,他们就可能抢劫财物。不过如何乘船渡河的大权由商人们掌握。商人们怎样才能平安过河呢?问题的提出1精选课件此类智力问题当然可以通过一番思考,拼凑出一个可行方案来。????但是,我们现在希望能找到求解这类问题的规律性、建立数学模型,用以解决更为广泛的问题。分析2精选课件此问题可视为一个多步决策问题,每一步就是一次渡河,每次渡河就是一次状态转移。???用三维变量(x,y,z)表示状态:???x?------商人数,?y------随从数x,y的取值范围:{0,1,2,3}???z------船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或2个;???即(x,y,1)→(u,v,0)时,u≤x,v≤y,u+v=x+y-1oru+v=x+y-2?,即船从对岸到此岸,此岸人数增加1或2个;???即(x,y,0)→(u,v,1)时,u≥x,v≥y,u+v=x+y+1oru+v=x+y+2?,如(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)/*不必考虑*/(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)的方法。????用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精选课件