论文题目：过河问题
-
论文题目：过河问题及其扩展
姓名
朱本超
陈凯
张安龙
学号
2031
2004
2016
学院
数计学院
数计学院
数计学院
年级
09
级
09
级
09
级
缺勤记录
课程论文自检报告
请回答以下问题，并在每题后打√确认。
1
．
除作者外，是否请过同事（同学）对论文进行挑剔性阅读？
2
．
“问题提出”或前言部分中的文献回顾是否完备？
3
．
是否对照过提供的“论文格式”逐项检查论文的各个部分？
4
．
文后参考文献与文中的文献引用是否一一对应？
5
．
文后参
考文献的书写格式是否符合国家标准？
（尤其注意著录符号、外国人的姓和名、有无漏项
等）
6
．
参考文献是否以近
5
年的文献为主？<
/p>
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
-
第
1
页
共
6
页
过河问题
[
摘要
]
[
关键词
]
过河
允许
状态
决策
1
、问题的提出
人狗鸡米过河问题。人、狗、鸡、米乘船过河；人要划船，而船小，除人之外最多只能运一
< br>物，且没人时狗要吃鸡，鸡要吃米；试基于状态转移模型、图论方法或动态规划方法（至少
采用两种不同方法）编制
matlab
程序，设计一个
安全过河方案，并使渡河次数尽可能少。
进一步地，基于类似思想解决商人过河问题和夫
妻过河问题。
（
a
< br>）商人过河问题。三名商人各带一名随从过河，而河边只有一只能容纳两人的小船，随
从们密约，
在河的任一岸，
一旦随从人数比商人多，
他们就杀人越货。
如何乘船渡河的权利
掌握在
商人手上。试问商人的安全渡河策略。进一步地，
4
名商人能否
安全过河？
（
b
）夫妻过河问题，三对夫妻过河，船最多载
2
人，任一女子
不能在其丈夫不在时与其他
男子在一起。试求最佳安全渡河方案。若船最多载三人，五对
夫妻能否安全过河？
2
、问题分析
安全渡河问题可以视为一个多步决策过程。
每一步，
即船由此
岸驶向彼岸或从彼岸驶回此岸，
都要对船上的人和物做出决策，
在保证安全的前提下，
在有限布内使全部人和物过河。
用状
态（变量）表示某一岸的人和物的状况，决策（变量）表示船上的人和物的状况，可以找出<
/p>
状态随决策变化的规律。问题转化为在状态的允许变化范围内（即安全渡河条件）
，确定每
一步的决策，达到渡河的目标。
3
、模型假设
1
、人、狗、鸡、米乘船过河。人要划船，而船小，除人之外对多只能运载一物，且没
人时
狗要吃鸡、鸡要吃米。
2
、人、狗、鸡、米分别记为
i
=1
，
2
，
3
，
4
，当
i
< br>在此岸时记为
x
i
=1
，否则
x
i
=0
，则此岸的
状态的状态可用
s
=
（
x
1
，
x
2
，
x
3
，
x
4<
/p>
）表示。记
s
的反状态为
s
=(1
—
x
1
，
1
—
x
2
，
1
—
x
3
，
1<
/p>
—
x
4
)
。决策为乘船方案，记为
d
=
（
u
1
，
u
2
，
u
3
，
u
4
）<
/p>
，
当
i
在船上时
记为
u
i
=1
，否则记
'
u
i
=0
。
则问题变为系统如何在满足
上述条件下，实现从（
1
，
1
，
1
，
1
）到（
0
，
0
，
0
，
0
< br>）的状态转
移。
4
、模型构造
方案一：
允许状态集合
S={
（
1
，
1
，
1
，
< br>1
）
，
（
1
，
1
，
1
，
0
）
，
（
1
，
1
，
0
，
1
）
，
（
1
< br>，
0
，
1
，
1
）
，
（
1
，
0
，
1
，
0
）及他们的
5
个反状态
}
。
允许决策集合
D={
（
1
，
1
< br>，
0
，
0
）
，
（
1
，
0
，
1
，
0
）
，
（
1
，
0
，
0
，
1
）
< br>，
（
1
，
0
，
0
，
0
）
}
。
记地
k
次渡河前此岸的状态为
s
k
，第
k
次渡河决策为
-
2
-
第
2
页
共
6
页
d<
/p>
k
，则状态转移方程为
s
k+1
=
s
k
+
（
-1
< br>）
k
d
k
5
个允
许状态及其反状态表示
10
个点，当且仅当某个允许状态经过一
个允许决策后仍为允
许状态时，这两个状态之间存在连线。根据路径图很容易得到渡河方
案。
状态转移图
状态
反状态
（
1
，
1
，
1
，
1
）
（
0
，
0
，
0
，
0
）
1
（
1<
/p>
，
1
，
1
，
0
）
（
0
，
0
，
0
，
1
）
2
（<
/p>
1
，
1
，
0
，
1
）
（
0
，
0
，
1
，
0
）
（
1
< br>，
0
，
1
，
1
）
3
（
0
，
1
，
0
，
0
）
4 <
/p>
（
1
，
0
，
1
，
0
）
（
0
，
1
，
0
，
1
）
由图可知，至少需要
四次渡河（其中
3
个来回）
，才能成功
。
方案二：
建立（人、狗、鸡、米）的
4
维
0/
1
向量；如（
1010
）——表示狗、
米已过河，人、鸡没有
等；可取状态：
10
种——（
1111
）
（
1110
）
（
1101<
/p>
）
（
1011
）
（
1010
）
（
0000
）
（
0001
）
（
0010
）
（
0100
）
（
0101
）
。可取过河
方式：
4
种——（
1100
）
（
1010
）
（
1001
）
（
1000
）
。
按照计算机语言的位运算：
异或运算
（
xor
）
等。
运算
方式：
例
（
1111
< br>）
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
）
=
< br>（
1100
）
X
(1101)xor(1010<
/p>
）
=
（
0111
）
X
（
1000
）
（
1101
）
O
(1001)
（
0100
）
O
⑵
（
1010
）
（
1011
）
O
（
1100
）
（
0111
）
X
⑴
（
0
001
）
xor
（
1001
）
=
（
< br>1000
）
X
（
1011
）
xo
r
（
1001
）
=
（
0010
）
O
（
1000
）
（
1001
）
X
（
1000
）
（
0011
）
X
（
1010
）
（
1110
）
O
（
1100
）
（
0010
）
O
⑵
(0100) xor
（
1100
）
=
（<
/p>
1000
）
X
(1110) xor
（
1001
）
=
（
0111
）
X
（
1000
）
（
1100
）
X
（
1000
）
（
0110
）
X
（
1100
）
（
1110
）
O
①
（
1100
）
（
0110
）
X
（
0010
）
xor
（
1010
）
=
（
1000
）
X
②
（
101
0
）
xor
（
1010
）
=
（
0000
）
O
（
1000
）
（
1010
）
O
②
（
1001
）
（
0011
）
X
根据题目要求，最少步骤，有①
继续下去，步骤明显多于②
，所以过河方案即为上述所列。
两种：
（
1111
）—（
0101
）—
(1101)
—
(
0001)
—（
1011
）—（
0010
）—（
1010
）
（
111
1
）—（
0101
）—
(1101)
—
(0100)
—
(1110)
< br>—（
0010
）—（
1010<
/p>
）
5
、模型扩展
-
3
-
第
3
页
共
6
页