《4名商人带4名随从安全过河（9月11日）.pptx》由会员分享，可在线阅读，更多相关《4名商人带4名随从安全过河（9月11日）.pptx（7页珍藏版）》请在金锄头文库上搜索。
1、学 海 无 涯 4 名商人带 4 名随从安全过河 一问题提出： 4 名商人带 4 名随从乘一条小船过河，小船每次自能承载至多两人。 随从们密约, 在河的任一岸, 一旦随从的人数比商人多, 就杀人越货. 乘船渡河的方案由商人决定，商人们如何才能安全渡河呢？ 二模型假设： 商人和随从都会划船。 三问题分析： 商随过河问题可以视为一个多步决策过程，通过多次优化，最后获 取一个全局最优的决策方案。对于每一步，即船由此岸驶向彼岸或由彼 岸驶向此岸，都要对船上的人员作出决策，在保证两岸的商人数不少于 随从数的前提下，在有限步内使全部人员过河。用状态变量表示某一岸 的人员状况，决策变量表示船上的人员状况，可
2、以找出状态随决策变化 的规律，问题转化为在状态的允许变化范围内(即安全渡河条件)，确定 每一步的决策，达到安全渡河的目标。 四模型构成： 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 ,y=0,1,2,3,4; x=y=1,2,3 uk第 k 次渡船上的商人数 vk第 k 次渡船上的随从数,1,学 海 无 涯 dk=(uk, vk)决策，D=(u , v)| 1=u+v=2,uk, vk=0,1,2 允许 决策
3、集合 k=1,2, 因为k 为奇数时船从此岸驶向彼岸，k 为偶数时船从彼岸驶向此岸， 所以状态 Sk 随决策 dk 的变化规律是 Sk1=Sk+(-1)kdk状态转移律 求 dkD(k=1,2, n), 使 SkS, 并按转移律由 S1=(4,4)到达状 态 Sn1=(0,0)。 五模型求解： 1.图解法：对于人数不多的情况，可以利用图解法来求解。 在 xoy 平面坐标系上画出如图所示的方格， 方格点表示状态 s=(x,y)，允许状态集合 S 是圆点标出的 13 个格子点，允许决策 dk 是 沿方格线移动 1 格或 2 格，k 为奇数时向左、下方移动，k 为偶数时向 右、上方移动。要确定一系列
4、的 dk 使由 S1=(4,4)经过那些圆点最终移 动到原点(0,0)。 由初始状态(4,4)到原点(0,0)，无论怎样走，都要经过(2,2)，但是 无论怎样变化人数，也只能到达此点后不能继续走下去，只能循环走(由 d7 状态无法不重复循环地走下去)，达不到最终的目标(0,0)，因此该问 题无解。,2,学 海 无 涯,2.穷举法： 根据分析可以通过编程上机求解，所用的 c 程序如下所示： #include #define N 30 int xN,yN,u6,v6,k; /* x,y：状态值，分别表示此岸商人、随从数*/ /*u,v：决策值，分别表示船上商人、随从数*/ /* k：决策步数；k
5、的奇偶性标志着船在河的此岸或彼岸 */ next(int k,int i)/*计算下一状态*/ if(k%2) /* k+1 为偶数，船从此岸到彼岸 */ xk+1=xk-ui; yk+1=yk-vi; ,3,4,学 海 无 涯 else /* k+1 为奇数，船从彼岸到此岸 */ xk+1=xk+ui; yk+1=yk+vi; return; allow(int p,int q)/* 判定状态是否允许,是否重复 */ int ok,j; /* ok:标记状态是否允许,是否重复；j:循环变量 */ if(px1|p!=0 /* 此时状态属于允许集，且不重复 */,5,学 海 无 涯, retu
6、rn ok; void main() int i,j,mN,flag=1;/* m:采用的决策序号，flag:回溯标记 */ u1=2; v1=0; /* 给决策编号并赋值 */ u2=0; v2=2; u3=1; v3=0; u4=0; v4=1; u5=1; v5=1; k=1; /* 从初始状态出发 */ printf(请输入商人和随从的初始状态:n 商人数=); scanf(%d, /* 记录采用的决策序号 */,6,学 海 无 涯 if(xk+1=0 ,7,学 海 无 涯 else /* 未到达初始状态 */ k-; /* 回溯退回 1 步，寻找新路径 */ i=mk; if(flag) continue; /* 本步决策尚未遍历时 */ else break; /* 本步决策遍历时 */ 当商人数和随从数分别取(2，2)(3，3)(4，4)时， 程序输出结果如 下：,
