精选优质文档-倾情为你奉上4名商人带4名随从安全过河一问题提出：4名商人带4名随从乘一条小船过河，小船每次自能承载至多两人。随从们密约, 在河的任一岸, 一旦随从的人数比商人多, 就杀人越货.乘船渡河的方案由商人决定，商人们如何才能安全渡河呢？二模型假设：商人和随从都会划船。三问题分析：商随过河问题可以视为一个多步决策过程，通过多次优化，最后获取一个全局最优的决策方案。对于每一步，即船由此岸驶向彼岸或由彼岸驶向此岸，都要对船上的人员作出决策，在保证两岸的商人数不少于随从数的前提下，在有限步内使全部人员过河。用状态变量表示某一岸的人员状况，决策变量表示船上的人员状况，可以找出状态随决策变化的规律，问题转化为在状态的允许变化范围内(即安全渡河条件)，确定每一步的决策，达到安全渡河的目标。四模型构成：xk第k次渡河前此岸的商人数，yk第k次渡河前此岸的随从数xk, yk=0,1,2,3,4; k=1,2, Sk=(xk, yk)过程的状态,S允许状态集合，S=(x,y)| x=0, y=0,1,2,3,4; x=4
