论文题目：过河问题及其扩展姓名学号学院年级缺勤记录朱本超2009221104120031 数计学院09级陈凯2009221104120004 数计学院09级张安龙2009221104120016 数计学院09级课程论文自检报告请回答以下问题，并在每题后打√确认。
1．除作者外，是否请过同事（同学）对论文进行挑剔性阅读？2．“问题提出”或前言部分中的文献回顾是否完备？3．是否对照过提供的“论文格式”逐项检查论文的各个部分？4．文后参考文献与文中的文献引用是否一一对应？5．文后参考文献的书写格式是否符合国家标准？（尤其注意著录符号、外国人的姓和名、有无漏项等）6．参考文献是否以近5年的文献为主？7．作者信息是否完整？包括word文档属性中的作者与单位、学号等。
课程论文质量评价标准评阅点评分标准分值得分摘要基本写出论文大意且语言简练、文字组织合理20 基本写出论文大意且语言简练15 基本写出论文大意10 套话、虚话较多或字数不够或文不对题0-5正文论证严谨、思路清晰、逻辑性强、有较强说服力，引文准确25 论证较严谨、思路较清晰、符合逻辑、有一定说服力，引文准确20 思路较清晰、引文较恰当15 有一定的说服力但论文紊乱、自相矛盾、大段抄袭他人文章0-10结构结构严谨、逻辑严密、层次清晰20 结构合理、符合逻辑、层次分明18 结构基本合理、层次比较清楚、文理通顺15 有不合理部分，逻辑性不强0-10深度和广度见解独特，对问题分析透彻，且非常全面25 有自主的见解，对问题的分析比较深入全面20 能提出自己的见解，分析的深度、广度一般15 分析比较深入全面10 对问题的分析既无深度，又无广度0-5规范化格式完全符合规范，字数完全符合要求10 格式比较规范，字数偏少8格式基本符合规范，但有个别地方不合规，字数较少 5格式规范性尚可，但不足之处较多，字数太少0-3 备注：以上评分标准仅供参考。
总分过河问题[摘要][关键词] 过河允许状态决策1、问题的提出人狗鸡米过河问题。
人、狗、鸡、米乘船过河；人要划船，而船小，除人之外最多只能运一物，且没人时狗要吃鸡，鸡要吃米；试基于状态转移模型、图论方法或动态规划方法（至少采用两种不同方法）编制matlab程序，设计一个安全过河方案，并使渡河次数尽可能少。
进一步地，基于类似思想解决商人过河问题和夫妻过河问题。
（a）商人过河问题。
三名商人各带一名随从过河，而河边只有一只能容纳两人的小船，随从们密约，在河的任一岸，一旦随从人数比商人多，他们就杀人越货。
如何乘船渡河的权利掌握在商人手上。
试问商人的安全渡河策略。
进一步地，4名商人能否安全过河？（b）夫妻过河问题，三对夫妻过河，船最多载2人，任一女子不能在其丈夫不在时与其他男子在一起。
试求最佳安全渡河方案。
若船最多载三人，五对夫妻能否安全过河？2、问题分析安全渡河问题可以视为一个多步决策过程。
每一步，即船由此岸驶向彼岸或从彼岸驶回此岸，都要对船上的人和物做出决策，在保证安全的前提下，在有限布内使全部人和物过河。
用状态（变量）表示某一岸的人和物的状况，决策（变量）表示船上的人和物的状况，可以找出状态随决策变化的规律。
问题转化为在状态的允许变化范围内（即安全渡河条件），确定每一步的决策，达到渡河的目标。
3、模型假设1、人、狗、鸡、米乘船过河。
人要划船，而船小，除人之外对多只能运载一物，且没人时狗要吃鸡、鸡要吃米。
2、人、狗、鸡、米分别记为i=1，2，3，4，当i在此岸时记为x i=1，否则x i=0，则此岸的状态的状态可用s=（x1，x2，x3，x4）表示。
记s的反状态为s'=(1—x1，1—x2，1—x3，1—x4)。
决策为乘船方案，记为d=（u1，u2，u3，u4），当i在船上时记为u i=1，否则记u i=0。
则问题变为系统如何在满足上述条件下，实现从（1，1，1，1）到（0，0，0，0）的状态转移。
4、模型构造方案一：允许状态集合S={（1，1，1，1），（1，1，1，0），（1，1，0，1），（1，0，1，1），（1，0，1，0）及他们的5个反状态}。
允许决策集合D={（1，1，0，0），（1，0，1，0），（1，0，0，1），（1，0，0，0）}。
记地k次渡河前此岸的状态为s k，第k次渡河决策为d k，则状态转移方程为s k+1=s k+（-1）k d k5个允许状态及其反状态表示10个点，当且仅当某个允许状态经过一个允许决策后仍为允许状态时，这两个状态之间存在连线。
根据路径图很容易得到渡河方案。
状态转移图状态反状态（1，1，1，1）（0，0，0，0）1（1，1，1，0）（0，0，0，1）2（1，1，0，1）（0，0，1，0）（1，0，1，1） 3 （0，1，0，0）4（1，0，1，0）（0，1，0，1）由图可知，至少需要四次渡河（其中3个来回），才能成功。
方案二：建立（人、狗、鸡、米）的4维0/1向量；如（1010）——表示狗、米已过河，人、鸡没有等；可取状态：10种——（1111）（1110）（1101）（1011）（1010）（0000）（0001）（0010）（0100）（0101）。
可取过河方式：4种——（1100）（1010）（1001）（1000）。
按照计算机语言的位运算：异或运算（xor）等。
运算方式：例（1111）xor（1100）=（0011）。
（1100）（0011）X （判断是否为可取状态，下同）开始状态（1111）xor（1010）（4种过河方式）=（0101）O（1001）（0110）X（1000）（0111）X取上一步异或运算后的可取状态，再做异或。
（去掉上一种过河方式）（下同）（1100）（1001）X (1100) （0001）O ⑴（0101）xor（1001）=（1100）X (1101)xor(1010）=（0111）X（1000）（1101）O (1001) （0100）O ⑵（1010）（1011）O （1100）（0111）X⑴（0001）xor（1001）=（1000）X （1011）xor（1001）=（0010）O（1000）（1001）X （1000）（0011）X（1010）（1110）O （1100）（0010）O⑵ (0100) xor（1100）=（1000）X (1110) xor（1001）=（0111）X（1000）（1100）X （1000）（0110）X（1100）（1110）O ①（1100）（0110）X（0010）xor（1010）=（1000）X ②（1010）xor（1010）=（0000）O（1000）（1010）O ②（1001）（0011）X根据题目要求，最少步骤，有①继续下去，步骤明显多于②，所以过河方案即为上述所列。
两种：（1111）—（0101）—(1101) —(0001)—（1011）—（0010）—（1010）（1111）—（0101）—(1101) —(0100) —(1110) —（0010）—（1010）5、模型扩展（a）商人过河问题设第k次渡河前此岸的商人数为x k，随从数为y k。
将二维向量s k=（x k，y k）定义为系统的状态，则安全渡河的允许状态集合为S={（0,0）（0,1）（0,2）（0,3）（1,1）（2,2）（3,3）（3,0）（3,1）（3,2）}。
设第k次船上的商人数为u k，随从数为v k。
将二维向量d k=（u k，v k）定义为商人的决策，则相应的允许决策集合为D={（2,0）（0,2）（1,0）（1,1）（0,1）}由于当k为奇数时船从此岸驶向彼岸，当k为偶数时船由彼岸驶回此岸，故状态转移方程即为s k+1=s k+（-1）k d k。
Matlab程序见附件二。
进一步的，对4名商人能否安全过河。
思想与三人过河类似，所以类似Matlab程序见附件三。
所以，4名商人不能安全过河。
（b）夫妻过河问题。
AaBbCc分别表示三对夫妻，ABC表示丈夫，abc表示妻子。
决策方案如下：此岸船上（去）对岸船上（回）ABCabc ab ab bABCbc bc abc cABCc AB ABab BbBCbc BC ABCa aabc ab ABCab bbc bc ABCabc进一步扩展五对夫妻过河，船能载三人。
ABCDEabcde表示五对夫妻，ABCDE表示丈夫，abcde表示妻子。
决策方案如下：此岸船上（去）对岸船上（回）ABCDEabcde abc abc aABCDEade ad abcd aABCDEae BCD BCDbcd BbABEabe ABE ABCDEcd cabce abc ABCDEabcd aae ae ABCDEabcde附件清单1、附件一：人、狗、鸡、米过河问题。
2、附件二：3、附件三：附件二：clear all; clca=[0,0; 0,1; 0,2; 0,3; 1,1; 2,2; 3,3; 3,0; 3,1; 3,2; ];d=[2,0; 0,2; 1,0; 1,1; 0,1];s(1,:)=[3,3];i=1; j=1; k=1; disp(' 此岸-- 船上-- 对岸')for i=1:12for j=1:5u=0;r=mod(i,2); m=r;for k=1:10if s(i,:)+(-1)^i*d(j,:)==a(k,:) t=1; endendif i+1>=3for m=(1+r):2:(i-1)if s(i,:)+(-1)^i*d(j,:)==s(m,:) u=1;endendendif t==1if u==0s(i+1,:)=s(i,:)+(-1)^i*d(j,:);c(i+1,:)=d(j,:); breakelseif u==1 continueendelse continueendendif t==0 disp('No Result'); break; endb(i+1,:)=[3,3]-s(i+1,:);play=sprintf('{%d, %d}--{%d, %d}--{%d, %d}', ...s(i,1),s(i,2), ...c(i+1,1),c(i+1,2), ...b(i+1,1),b(i+1,2));disp(play)if s(i+1,:)==[0,0] breakendend运行结果为：此岸- 船上- 对岸{3, 3}--{0, 2}--{0, 2}{3, 1}--{0, 1}--{0, 1}{3, 2}--{0, 2}--{0, 3}{3, 0}--{0, 1}--{0, 2}{3, 1}--{2, 0}--{2, 2}{1, 1}--{1, 1}--{1, 1}{2, 2}--{2, 0}--{3, 1}{0, 2}--{0, 1}--{3, 0}{0, 3}--{0, 2}--{3, 2}{0, 1}--{1, 0}--{2, 2}{1, 1}--{1, 1}--{3, 3}附件三：clear all; clca=[0,0; 0,1; 0,2; 0,3; 0,4; 1,1; 2,2; 3,3; 4,0; 4,1; 4,2; 4,3; 4,4]; d=[2,0; 0,2; 1,0; 1,1; 0,1];s(1,:)=[4,4];i=1; j=1; k=1; disp(' 此岸-- 船上-- 对岸')for i=1:12for j=1:5t=0;u=0;r=mod(i,2); m=r;for k=1:13if s(i,:)+(-1)^i*d(j,:)==a(k,:) t=1; endendif i+1>=4for m=(1+r):2:(i-1)if s(i,:)+(-1)^i*d(j,:)==s(m,:) u=1;endendif t==1if u==0s(i+1,:)=s(i,:)+(-1)^i*d(j,:);c(i+1,:)=d(j,:); breakelseif u==1 continueendelse continueendendif t==0 disp('No Result'); break; endb(i+1,:)=[4,4]-s(i+1,:);play=sprintf('{%d, %d}--{%d, %d}--{%d, %d}', ...s(i,1),s(i,2), ...c(i+1,1),c(i+1,2), ...b(i+1,1),b(i+1,2));disp(play)if s(i+1,:)==[0,0] breakendend运行结果为：此岸-- 船上-- 对岸{4, 4}--{0, 2}--{0, 2}{4, 2}--{0, 2}--{0, 0}{4, 4}--{1, 1}--{1, 1}{3, 3}--{1, 0}--{0, 1}{4, 3}--{0, 2}--{0, 3}{4, 1}--{0, 1}--{0, 2}{4, 2}--{2, 0}--{2, 2}{2, 2}--{1, 1}--{1, 1}No Result。