夫妻过河问题.ppt

《夫妻过河问题.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、夫妻过河问题有3对夫妻要过河，船至多可载2人，条件是任一女子不能在其丈夫不在场的情况下与另外的男子在一起，问如何安排这3对夫妻过河？这是阿拉伯早期的一道趣味数学题，此问题虽然与商人过河问题并不完全相同。不难验证，经过11次渡河过程即可解决此问题，如下：如果采用前次课提到的人狼羊菜问题的状态转移法，设一个6维的向量，但由于数据比较冗长，容易出现错误，下面仅给出可取状态及可取运载。可取状态：续可取状态：共22个可取状态，还有其他可取状态吗？可取运载：可取运算：采用二进制加法进行，一次渡河就是一个可取状态向量与一个可取

2、运载向量相加，可取状态经过加法运算后仍是可取状态，这种运算成为可取运算。以下尝试给出几个运算过程。（1）以下部分略去，可以看到用手工的办法去一步步的运算，十分的繁琐，但是将此做法用抽象的语言描述出来，就显得简洁许多。如下：（1）可取状态：一共10个，它们是(0,i),(i,i),(3,i)i=0,1,2,3其中(i,i)表示第i对夫妻。（2）可取运载：取可取运载向量为其中当k为奇数时负向量表示过河；当k为偶数时正向量表示由对岸返回。（3）可取运算：按普通向量加法运算，一次过河就相当于一个可取状态向量与一个可取

3、运载向量相加。于是问题就转化为：由初始状态（3，3）经过多少次（奇数）可取运算才能转化为状态（0，0）。可取状态：可取运载：分别表示1对和两对夫妻（1）为了便于计算机求解，记可取状态集合和可取运载集合分别为：并用表示状态的变化过程，表示状态下的过河方案，当k为奇数时，表示从左岸到右岸，当为偶数时表示从右岸到左岸。则状态转移满足下列关系：xy3322110d1d11S1图解法状态s=(x,y)~16个格点允许状态S~10个点允许决策D~移动1或2格;k奇,左下移;k偶,右上移.d1,d11给出安全渡河方案