文档介绍：该【4名商人带4名随从安全过河 】是由【布罗奇迹】上传分享，文档一共【9】页，该文档可以免费在线阅读，需要了解更多关于【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,y=0,1,2,3,4;x=y=1,2,3}uk~第k次渡船上的商人数vk~:根据分析可以通过编程上机求解,所用的c程序如下所示:#include<>#defineN30intx[N],y[N],u[6],v[6],k;/*x,y:状态值,分别表示此岸商人、随从数*//*u,v:决策值,分别表示船上商人、随从数*//*k:决策步数;k的奇偶性标志着船在河的此岸或彼岸*/next(intk,inti)/*计算下一状态*/{if(k%2)/*k+1为偶数,船从此岸到彼岸*/x[k+1]=x[k]-u[i];y[k+1]=y[k]-v[i];}else/*k+1为奇数,船从彼岸到此岸*/{x[k+1]=x[k]+u[i];y[k+1]=y[k]+v[i];}return;}allow(intp,intq)/*判定状态是否允许,是否重复*/{intok,j;/*ok:标记状态是否允许,是否重复;j:循环变量*/if(p<0||p>x[1]||p!=0&&q>p||(x[1]-p)!=0&&(y[1]-q)>(x[1]-p)||q<0||q>y[1])ok=0;/*此时状态不属于允许集*/else{for(j=k-1;j>0;j-=2)/*是否重复与船在河的哪一岸有关*/if(p==x[j]&&q==y[j]){ok=0;/*此时状态出现重复*/break;}if(j<=0)ok=1;/*此时状态属于允许集,且不重复*/}returnok;}voidmain(){inti,j,m[N],flag=1;/*m:采用的决策序号,flag:回溯标记*/u[1]=2;v[1]=0;/*给决策编号并赋值*/u[2]=0;v[2]=2;u[3]=1;v[3]=0;u[4]=0;v[4]=1;u[5]=1;v[5]=1;k=1;/*从初始状态出发*/printf("请输入商人和随从的初始状态:\n商人数=");scanf("%d",&x[k]);printf("随从数=");scanf("%d",&y[k]);while(flag)for(i=1;i<6;i++)/*遍历各种决策*/{next(k,i);/*计算下一状态*/if(allow(x[k+1],y[k+1]))/*若新状态允许且不重复*/{m[k]=i;/*记录采用的决策序号*/if(x[k+1]==0&&y[k+1]==0)/*若到达目标状态,输出结果*/{printf("初始值:商人%d随从%d\n",x[1],y[1]);for(j=1;j<=k;j++)printf("第%2d次%d%d\n",j,x[j+1],y[j+1]);flag=0;break;}else/*若未到达目标状态*/{k++;/*生成下一步的步数值*/break;/*遍历终止,进入下一步*/}}else/*若新状态不允许或重复*/{while(i==5)/*本步决策已经遍历时*/{if(k==1){printf("本题无解!\n");flag=0;break;}else/*未到达初始状态*/{k--;/*回溯——退回1步,寻找新路径*/i=m[k];}}if(flag)continue;/*本步决策尚未遍历时*/elsebreak;/*本步决策遍历时*/}}}}当商人数和随从数分别取(2,2)(3,3)(4,4)时,程序输出结果如下: