商人过河问题.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,商人过河问题,三名商人各带一个随从乘船渡河。现此岸有一小船只能容纳两人，由他们自己划行。若在河的任一岸随从人数比商人多，他们就可能抢劫财物。不过如何乘船渡河的大权由商人们掌握。商人们怎样才能安全过河呢,?,问题的提出,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),时,u,x,v,y,u,+,v=x,+,y,-1 or,u,+,v,=,x,+,y,-23.,当,Z,从,0,变为,1,时，即船从对岸到此岸，此岸人数增,加,1,或,2,个；即,(,x,y,0)(,u,v,1),时,u,x,v,y,u,+,v,=,x,+,y,+1 or,u,+,v,=,x,+,y24.,不重复已出现过的状态，如,(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,例如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),人、狗、鸡、米过河问题某人要带一条狗、一只鸡、一箩米过河，但小船除需要人划外，最多只能载一物过河，而当人不在场时，狗要咬鸡、鸡要吃米。问此人应如何过河,?,探 索,13,