商人过河问题.pptx

1此类智力问题当然可以通过一番思考，此类智力问题当然可以通过一番思考，拼凑出一个可行方案来。拼凑出一个可行方案来。但是，我们现在希望能找到求解这类问但是，我们现在希望能找到求解这类问题的规律性、建立数学模型，用以解决更题的规律性、建立数学模型，用以解决更为广泛的问题。为广泛的问题。分析分析2此问题可视为一个此问题可视为一个多步决策多步决策问题，每一步就是一问题，每一步就是一次渡河，每次渡河就是一次状态转移。次渡河，每次渡河就是一次状态转移。用三维变量用三维变量(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这就是此问题的数学模型。(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个；个；即即(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)；模型求解模型求解4按照以上规则，求解过程如下：从从(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)出发(3,3,1)/*/*不必考虑不必考虑*/(3,2,1)/*可取*/5如下图所示：如下图所示：这样可得到所有答案这样可得到所有答案:6由此可得到渡河策略由此可得到渡河策略:(3,3,1)(3,2,1)(3,3,1)(3,2,1)(3,0,0)(3,0,0)(3,1,1)(3,1,1)(1,1,0)(1,1,0)(2,2,1)(2,2,1)(0,2,0)(0,2,0)(0,3,1)(0,3,1)(0,1,0)(0,0,0)(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)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个随从(m4)能否安全渡河？思思 考考10(1)(2,2)(1,1)or(2,0)(2,1)(0,1)(1,1)(0,0)如下图：11(2)m名商人m个随从(m4)无法安全渡河,如m=4时的图(如下图)，d7就无法作不重复的转移。12(1)夫妻过河问题夫妻过河问题有三对夫妻要过河，船最多可载两人。有三对夫妻要过河，船最多可载两人。约束条件是根据法律，任一女子不得在其约束条件是根据法律，任一女子不得在其丈夫不在场的情况下与另外男子在一起，问丈夫不在场的情况下与另外男子在一起，问此时这三对夫妻能否过河此时这三对夫妻能否过河?四对夫妻呢四对夫妻呢(2)人、狗、鸡、米过河问题人、狗、鸡、米过河问题某人要带一条狗、一只鸡、一箩米过河，某人要带一条狗、一只鸡、一箩米过河，但小船除需要人划外，最多只能载一物过河，但小船除需要人划外，最多只能载一物过河，而当人不在场时，狗要咬鸡、鸡要吃米。问而当人不在场时，狗要咬鸡、鸡要吃米。问此人应如何过河此人应如何过河?探探 索索