商人们怎样安全过河附MATLAB程序完整.doc

商人们怎样安全过河
　 随从们密约, 在河的任一岸, 一旦随从
的人数比商人多， 就***越货.　 　 但是乘船渡河的方案由商人决定．　　 　 　 商人们怎样才能安全过河？ 　 　　　　 　
问题分析:D多步决策过程
决策~　每一步(此岸到彼岸或彼岸到此岸）船上的人员
要求~在安全的前提下(两岸的随从数不比商人多），经有限步使全体人员过河.
建立模型
ｘk~第k次渡河前此岸的商人数 　 　 　 　　 　 　 　 xk， ｙｋ=０，1,2,３;
ｙｋ～第k次渡河前此岸的随从数 　　 　　 　　 　 k=1，2，｜.。。．¼ ¼
sk=（xk ，　yk）~过程的状态 　 　　 　　　 　　 　 　 S ～ 允许状态集合
S={(x　,　ｙ)| ｘ＝0, ｙ＝0，1，2，3；　x=3, ｙ＝0,1,2,３; ｘ=y=1，２｝
uk～第k次渡船上的商人数 　　 　 　 　　　 　 uk， vk=0，1，2；
vk～第k次渡船上的随从数 　　 　　　 　　 　 　 　　 　　　　 　k=1，2,．..．.¼ ¼
dk＝(ｕk　， vk）~决策　　 　 　 　 　 D＝{(u ， v)| u+v=１， 2} ~允许决策集合
　 　 　 　 　 ～状态转移律
多步决策问题 　 　 　求dkÎD(k=１,２,　¼n）, 使skÎＳ， 并按转移律由 s1＝（3，3）到达 ｓn+1＝（０，0）。
模型求解
穷举法 ~ 　编程上机 　 　 　 Ｓ=｛（ｘ ， y)|　ｘ＝0， ｙ=0，1，2，3；x=3，　ｙ＝０，1,2,3; ｘ＝ｙ=1，2｝
图解法
状态s=(x，ｙ)　～　16个格点允许状态～ １0个 点
允许决策　～ 移动1或２格； k奇，左下移；　k偶，右上移.
d1，。．．。。。。，ｄ11给出安全渡河方案
评注和思考
规格化方法，易于推广
考虑4名商人各带一随从的情况
程序
％％％％％％%％%%％％%％％％ 开始 %％％%％％％%％％％％％%％%%%％％%%
functiｏｎ ｊuｅcｈe=guohｅ
cｌｅａｒ all
ｃlc
％％％％%%％％％％程序开始需要知道商人和仆人数；％%％%％％％％％％%％%
sｈangreｎ=inpuｔ（＇输入商人数目: ')；
ｐuren=inpuｔ（＇输入仆人数目: '）;
ronglｉａng=inpｕt（'输入船的最大容量： ’);
ｉf ｐuｒen>shａｎgren
shangreｎ＝ｉｎｐut(＇输入商人数目:＇);
puｒeｎ＝inｐuｔ（'输入仆人数目：')；
ｒongliaｎg=input(’输入船的最大容量：’)；
enｄ
%％％％%%％%％%％%％%％％％%%%％％％％%％%％%％%％%％%％%%％%％％%％%%%％％％　 　决策生成
　　jc＝1；　　 ％决策向量放在矩阵d中,jc为插入新元素的行标初