问题分析:由已知得、人可以划船而其他都不能划船只能被运送,所以人始终都得在船上来回运输。由常识可知狼会吃羊而不吃菜、假设狼不能吃此商人,羊会吃菜。只有四者都安全渡过河而没有被吃掉才算成功渡河。
逻辑推理:首先人的在船上,而为了使得在岸上剩余之物能够安全相处,所以第一次:人就得把羊先运送到对岸,第二次空身返回到此岸,第三次把狼与羊中的任何一个(假设是狼)运送到对岸,为保对岸的安全就必须把第一次运到对岸的羊运送回去,即第四次人同狼一同回到此岸,第五次是把上次所剩的那一种(羊)运到对岸,因为此时对岸是安全的,第六次商人空身回到此岸,第七次再把羊运送到对岸则可以使得狼、羊、菜安全渡河,且符合船的限制条件。
有推理可以看出,河此岸与对岸的类别与数量都在随着运送次数的改变而改变。一次渡河即为一次决策。可以用状态表示某一岸的人员状况,决策量表示船上的运送状况。可以找出状态随决策的的变化规律,问题转化为:状态在允许的变化范围内(安全渡河)确定每一步的决策达到安全渡河的目的。
模型构成:记第次渡河后此岸的人狼羊菜的数量与种类为一四维向量=0、1、2、……0表示不在此岸,1表示在此岸。为整数且分别代表人狼羊菜。
则在此岸可以安全相处的状态量为
S={(1,1,1,1),(0,1,0,1),(1,0,1,0)(0,0,1,0),
(0,0,0,1),(0,1,0,0),(1,0,1,1),
(1,1,0,1),(1,1,1,0),(0,0,0,0)
其中初始量为=(1,1,1,1)最终经过n次安全渡河后的状态为最终状态=(0,0,0,0)。
决策量用四维向量=()表示第k次渡河时船上所载的个数及种类,其中
分别表示船上时的人、狼、羊、菜。有条件010表示无(不在船上)1表示有(在船上)
安全前提下允许的决策集合有:D={(1,1,0,0)(1,0,1,0)(1,0,0,1)(1,0,0,0)}有以上推理可以归纳出状态量与决策量的关系式为:
按照以上关系式确定的状态量经过n次转运可以使得初始量=(1,1,1,1)最终达到终止量=(0,0,0,0)且每次决策取自允许决策量D中,每次达到的状态量为安全状态量。
Wen08170