课件-夫妻过河模型讲述.ppt

夫妻过河模型 有3对夫妻过河，船最多可载两人，由他们自行划行。条件是任一女子不能当其丈夫不在场的情况下与另外的男子在一块，问如何安排这3对夫妻过河? 这是早期阿拉伯国的一道趣味数学题，经过一番逻辑思考可以找出解决的办法。 如果采用数学模型的方法求解，可以发现此类问题的规律，更容易推广从而解决更广泛的问题。 问题分析 此渡河问题的解决可以视为一个多步决策的过程，每一步，即船由此岸驶向彼岸，或由彼岸驶回此岸，都要对船上的人员做出决策，在保证满足条件的前提下，推断出使人员全部过河的最少步数。 用状态[二维向量]表示某一岸的人员状况，决策[二维向量]表示船上人员状况，来寻找状态随决策的变化规律。这样问题就转化为在状态允许的变化范围内，确定每一步的决策，最终达到渡河目标。 模型的建立 记第后次渡河前此岸的男子数为xk，女子数为yk： xk、yk =0，1，2，3 k=1，2，… Sk = (xk, yk)为状态。 满足条件下的状态集合，即允许的状态集合为： 记第k次渡船上的男人数为uk，女人数为vk，将二维向量dk=(uk,vk)定义为决策，允许决策集合记作： 因为k为奇数时船从此岸驶向彼岸，k为偶数时船由彼岸驶向此岸。所以有： 模型求解 允许状态集合S用圆点表示。允许决策dk是方格线移动1格或2格。k为奇数时向左下方移动，k为偶数时向右上方移动。下图给出了一种移动方案： 经过d1，d2，…，d11共11趟可达S12=(0，0)，具体步骤如下： 评估分析 从以上的模型和求解可知，当男、女人数增加或小船的容量加大时，单纯靠逻辑思考来获取结果就困难了，但是沿用上述的方法仍可以求解。 从所建的数学模型中也可以获知，依照上述的约束条件，4对夫妻就无法过河，如果船每次可载3人，则可以允许5对夫妻过河，但6对就不行，依此类推。 * 这样问题归结为求dk∈D，使Sk∈S按照转移规律，由初始状态S1=(3，3)经n步[奇数步]到达状态Sn+l=(0，0) *