夫妻过河问题课件

夫妻过河问题 有3对夫妻要过河，船至多可载2 人，条件是任一女子不能在其丈 夫不在场的情况下与另外的男子 在一起，问如何安排这3对夫妻过 河？ 这是阿拉伯早期的一道趣味数学题，此问题虽然 与商人过河问题并不完全相同。不难验证，经过 11次渡河过程即可解决此问题，如下： 同样经过11步有些同学采用了如下步骤： 还有些同学采用了前次课提到的人狼羊菜 问题的状态转移法，设了一个6维的向量， 但由于数据比较冗长，容易出现错误，下 面仅给出可取状态及可取运载。 可取状态可取状态： 续可取状态：续可取状态： 共共2222个可取状态，还有其他可取状态吗？个可取状态，还有其他可取状态吗？ 可取运载：可取运载： 可取运算：可取运算： 采用二进制加法进行，一次渡河就是一个可取采用二进制加法进行，一次渡河就是一个可取 状态向量与一个可取运载向量相加，可取状态状态向量与一个可取运载向量相加，可取状态 经过加法运算后仍是可取状态，这种运算成为经过加法运算后仍是可取状态，这种运算成为 可取运算。以下尝试给出几个运算过程。可取运算。以下尝试给出几个运算过程。 （1 1） 以下部分略去，可以看到用手工的办法去以下部分略去，可以看到用手工的办法去 一步步的运算，十分的繁琐，但是将此做一步步的运算，十分的繁琐，但是将此做 法用抽象的语言描述出来，就显得简洁许法用抽象的语言描述出来，就显得简洁许 多。如下：多。如下： （1 1）可取状态：一共）可取状态：一共1010个，它们是个，它们是 (0,i),(i,i),(3,i) i=0,1,2,3(0,i),(i,i),(3,i) i=0,1,2,3 其中其中( (i,ii,i) )表示第表示第i i对夫妻。对夫妻。 （2 2）可取运载：取可取运载向量为）可取运载：取可取运载向量为 其中其中 当当 k k为奇数时负向量表示过河；当为奇数时负向量表示过河；当k k为为 偶数偶数 时正时正 向量表示由对岸返回。向量表示由对岸返回。 （3 3）可取运算：按普通向量加法运算，一）可取运算：按普通向量加法运算，一 次过河就相当于一个可取状态向量与一次过河就相当于一个可取状态向量与一 个可取运载向量相加。个可取运载向量相加。 于是问题就转化为：由初始状态（于是问题就转化为：由初始状态（3 3，3 3）经）经 过多少次（奇数）可取运算才能转化为状态过多少次（奇数）可取运算才能转化为状态 （0 0，0 0）。）。 可取状态：可取状态： 可取运载：可取运载： 分别表示分别表示1 1对和两对夫妻对和两对夫妻 （1 1） 为了便于计算机求解，记可取状态集合和可取为了便于计算机求解，记可取状态集合和可取 运载集合分别为：运载集合分别为： 并用并用 表示状态的变化表示状态的变化 过程，过程， 表示状态表示状态 下的过河方下的过河方 案，当案，当k k为奇数时，为奇数时， 表示从左岸到右岸，当为表示从左岸到右岸，当为 偶数时表示从右岸到左岸。则状态转移满足下列偶数时表示从右岸到左岸。则状态转移满足下列 关系：关系： x y 3 32 2 1 1 0 d1 d11 S1S1 图 解 法 状态s=(