导读：王鹏道：选择论文题目、设计论文版面字体、分配成员任务、总结任利伟：一、问题提出、，为了求解3个商人和3个随从的过河问题，用数学分析方法，建立数学模型，获得过河问题的完整求解过程，随从们密约,在河的任一岸,一旦随从的人数比商人多,就杀人越货，但是乘船渡河的方案由商人决定.商人们怎样才能安全过河?，解决的关键集中在商人和随从的数量上，该问题就是考虑过河步骤的安排和数量上，在安全的前提下(两岸的随从
组长：王鹏道 110714
组员：任利伟110713、孙t110706 小组成员负责情况：
王鹏道：选择论文题目、设计论文版面字体、分配成员任务、总结 任利伟：一、问题提出、关键、分析。二、模型假设、三、模型建立 孙t：四、模型求解、五、模型的检验、拓展及延伸
为了求解3个商人和3个随从的过河问题，用数学分析方法，建立数学模型，并且加以求解，展示动态规划思想的应用步骤。最后利用计算机蝙程进行求解，获得过河问题的完整求解过程；有效地求解类似多步决策问题的作用。
关键词：多步决策 计算机求解 状态转移律 图解法
一、 问题的提出
随从们密约, 在河的任一岸, 一旦随从的人数比商人多, 就杀人越货，但是乘船渡河的方案由商人决定.商人们怎样才能安全过河?
二、 问题的关键
解决的关键集中在商人和随从的数量上，以及小船的容量上，该问题就是考虑过河步骤的安排和数量上。各个步骤对应的状态及决策的表示法也是关键。
问题的分析
在安全的前提下(两岸的随从数不比商人多),经有限步使全体人员过河。由于船上人数限制，这需要多步决策过程，必须考虑每一步船上的人员。动态规划法正是求解多步决策的有效方法。它要求把解的问题一层一层地分解成一级一级、规模逐步缩小的子问题。直到可以直接求出其解的子问题为止。分解成所有子问题按层次关系构成一棵子问题树．树根是原问题。原问题的解依赖于子问题树中所有子问题的解。
记第k次过河前A岸的商人数为XK，
随从数为YK
XK ,YK=0，1，2，3，将二维向量SK=(XK，YK)定义为状态．把满足安全渡河条件下的状态集合称为允许状态集合。记作S。则
S={(XK ,YK)|(XK =0,YK =0,1,2,3),(XK =3,YK =0,1,2,3),(XK =YK =1)(XK =YK =2)} 记第k次过河船上的商人数为UK
随从数为VK
将二维向量DK=(UK ,VK)定义为决策．由小船的容量可知允许决策集合（记作D)为
D={(UK ,VK)|UK +VK=l,2}={(O,1);(O,2);(1,O);(1,1);(2,O)}
模型建立：
动态规划法正是求解多步决策的有效方法。它要求把解的问题一层一层地分解成一级一级、规模逐步缩小的子问题。直到可以直接求出其解的子问题为止。分解成所有子问题按层次关系构成一棵子问题树．树根是原问题。原问题的解依赖于子问题树中所有子问题的解。
用动态规划法分析三名商人的过河问题。可得如下的递归树：
（注解：当K为奇数时，船在B岸；当K为偶数时，船在A岸。）
通过分析该递归树，知道求解关键在于正确地写出基本的状态转移关系式和恰当的边界条件。
因为k为奇数时，船是从A岸驶向B岸，k为偶数时。船是由B岸驶回A岸。所以状态SK随决策DK变化的规律是
SK+1=SK+(-1)K DK，k=l，2，?，
称之为状态转移律，这样，制定过河方案就归结为如下的多步决策问题：
每一步，船由A岸驶向B岸或B岸驶回A岸，都要对船上的人员(商人UK，随从VK各几人)作出决策，在保证安全的前提下即两岸的商人数XK都不比随从数YK少，用有限步使人员全部过河．用状态(变量)SK表示某一岸的人员状况，决策(变量)DK表示船上的人员状况，可以找出状态SK随决策DK变化的规律．这样安全过河问题就转化为：
求决策DK∈D(k=1,2，……，n)，使得状态SK∈S，按照状态转移律，由初始状态S1=(3，3)，经有限步n到达状态SK+1=(O,O)。
SK+1=SK+(-1)KDK，k=l,2，3，其中DK ∈D={(UK ,VK)|UK +VK=l，2}，{其中SK ∈(XK ,YK)|(XK=0，YK =1，2，3)；(XK =3，YK=0,1,2,3);(XK =YK =1,2)},Sn+1 =(0,0) 这就是三个商人的过河问题模型。
包含总结汇报、旅游景点、出国留学、外语学习、人文社科、IT计算机、计划方案、经管营销以及数学建模商人过河__论文等内容。本文共2页
相关内容搜索 上传我的文档
 下载
 收藏
该文档贡献者很忙，什么也没留下。
 下载此文档
正在努力加载中...
4-商人过河问题
下载积分：200
内容提示：4-商人过河问题
文档格式：PDF|
浏览次数：140|
上传日期： 21:50:00|
文档星级：
该用户还上传了这些文档
4-商人过河问题
官方公共微信var sogou_ad_id=731545;
var sogou_ad_height=90;
var sogou_ad_width=980;【数学模型】商人们怎样过河？
【数学模型】商人们怎样过河？
算法与数学
这篇博文中，同样是一个很简单的数学问题，但是解决起来比要复杂一些。在这次模型求解中，我会使用两种方法，一种是纯粹的数学方法，另一种是通过计算机程序来计算，通过计算机求解我们可以求解一些规模更大的问题。由于这篇文章篇幅我预计会比较长，为了不混淆，上一篇文章中的延伸问题我会再写一篇文章单独解答。
问题： 三名商人各带一个随从过河，一只小船只能容纳两个人，随从们约定，只要在河的任何一岸，一旦随从人数多于商人人数就杀人越货，但是商人们知道了他们的约定，并且如何过河的大权掌握在商人们手中，商人们该采取怎样的策略才能安全过河呢？
这次的问题是一个很经常遇到的过河问题，其实对于该类问题，我们经过逻辑思考就可以得到答案。但是通过数学模型的建立，我们可以得到一个通用的解答，并且通过计算机的计算我们可以大大扩大问题的规模。
因为这个问题已经理想化了，所以我们无需对模型进行假设，该问题可以看作一个多步决策问题。
每一步，船由此岸划到彼岸或者由彼岸划回此岸，都要对船上的人员进行决策（此次渡河船上可以有几名商人和几名随从），在保证安全（两岸的随从都不比商人多）的前提下，在有限次的决策中使得所有人都到对岸去。
因此，我们要做的就是要确定每一步的决策，达到渡河的目标。
记第 k 次过河前此岸的商人数为 xk , 随从数为 yk , k = 1, 2, 3…, xk ,yk = 0, 1, 2, 3
定义状态： 将二维向量
sk = ( xk ,
yk ) 定义为状态
将安全渡河状态下的状态集合定义为允许状态集合， 记为
S = {(x,y) | x=0,y=0,1,2,3; x=y=1; x=y=2; x=3,y=0,1,2,3}
记第 k 次渡河船上的商人数为 uk ， 随从数为 vk
定义决策： 将二维向量 dk = (uk , vk) 定义为决策
允许决策集合 记作
D = {(u,v) | 1 ≤ u+v ≤ 2, u,v = 0,1,2}
因为小船容量为2，所以船上人员不能超过2，而且至少要有一个人划船，由此得到上式。
由我们定义的状态 sk 和决策 dk ，我们可以发现它们之间是存在联系的：
k 为奇数是表示船由此岸划向彼岸，k 为偶数时表示船由彼岸划回此岸
状态 sk 是随着决策 dk 变化的，规律为：
sk+1 = sk + (-1)kdk
我们把上式称为状态转移律，因此渡河方案可以抽象为如下的多步决策模型：
求决策 dk ∈ D(k = 1,2,…,n) , 使状态 sk ∈ S 按照转移率，初始状态 s1 = (3,3) 经有限步 n 到达状态 sn+1 = (0,0)
到这里，整个数学模型就已经非常清晰了，接下来要做的就是求解模型得出结果。
在这个模型的求解中，我将会使用两种方法，一种是数学图解法，用于解决和当前题目一样的规模比较小的问题，优点是比较简便，但是对于规模比较大的问题就无能为力了，比如说有50个商人携带50个随从过河，第二种方法是通过计算机编程，使用程序来解决该问题，即使问题规模增大，我们也可以利用计算机强大的计算能力来解决。
数学图解法
我们首先在 xOy 平面坐标系中画出如下方格，方格中的点表示状态 s = (x,y)
起始状态（下图绿色点） s1 = (3,3) , 终止状态（下图红色点） sn+1 = (0,0)
允许决策 dk 表示的是在方格中的移动，根据允许决策 dk 的定义，它每次的移动范围为1~2格，并且 k 为奇数时向左或下方或左下方移动，k 位偶数时向右或上方或右上方移动。
于是，这个问题就变成了，根据允许决策 dk ，在方格中在状态（方格点）之间移动，找到一条路径，使得能从起始状态（上图绿色点） s1 = (3,3) ,到达终止状态（上图图红色点） sn+1 = (0,0)
在下图中，我们给出了一种方案，我们可以很清楚的看到该方案绝对不是最佳方案（渡河次数最少），它只是给出了一种方案，而且我们看来是一种极其不优化的方案，但是可以很清楚地看出图解法是如何工作的。
根据上图，我们得出的方案如下：
d1：两个随从划到对岸
d2：一个随从划回来
d3：两个随从划到对岸
d4：一个随从划回来
d5：两个商人划到对岸
d6：一个商人和一个随从划回来
d7：两个商人划到对岸
d8：一个随从划回来
d9：两个随从划到对岸
d10：一个商人划回来
d11：一个商人和随从划到对岸
最终商人们安全渡河
我们看到上面介绍的图解法对于小规模问题很直观也很简单，但是无法应对大规模的问题，于是我们采用编程的方法来再次解决上述问题，这次我使用的编程语言为Python.
创建允许状态集合
对于允许状态集合，我们要去使用算法对其进行计算，所谓允许状态无非就是，河岸两边的商人们都是安全的：
一种情况是：两岸的商人人数都比随从人数多（对于随从和商人人数相同的情况就是河的任一岸，商人人数等于随从人数）
另一情况为：所有商人都在河的任何一岸，此时另一岸没有任何商人，对于随从的人数在河的任一岸的数量不论是多少，此时都是安全的
按照以上方法编程如下：
'''创建允许状态集合'''
def allowset(self):
allowset = []
for i in range(self.merchants + 1):
for j in range(self.servants + 1):
if i == 0:
allowset.append([i,j])
elif i == self.merchants:
allowset.append([i,j])
elif (i &= j and ((self.merchants-i) &= (self.servants-j))):
allowset.append([i,j])
return allowset
创建允许决策集合
对于创建允许决策集合，它和船的容量是相关的，只要每次渡河的商人数量和随从数量小于等于船的容量即可，代码如下：
'''创建允许决策集合'''
def allowaction(self):
allowactionset = []
for i in range(self.capacity + 1):
for j in range(self.capacity + 1):
if (i+j) &= self.capacity and (i + j) != 0:
allowactionset.append([i,j])
return allowactionset
对于如何渡河问题我采取的是一种随机的方法，对于当前安全状态，随机选择一种决策进行试探，如果采取该决策可以到达安全状态，则采用，如此循环，直到到达目的地。如果采取该策略不能到达安全状态，则再次随机选择一种策略。
代码如下：
def solve(self,allowactionset,allowstate):
count = 1;
current = (self.merchants,self.servants)
while current != [0,0]:
move = allowactionset[random.randint(0,len(allowactionset)-1)]
temp = [current[0]+((-1)**count)*move[0],current[1]+((-1)**count)*move[1]]
if(temp in allowstate):
current = [current[0]+((-1)**count)*move[0],current[1]+((-1)**count)*move[1]]
if(count % 2 == 1):
print "[%d]个商人，[%d] 个随从从此岸划到对岸" %(move[0],move[1])
elif(count % 2 == 0):
print "[%d]个商人，[%d] 个随从从对岸划回此岸" %(move[0],move[1])
count = count + 1
有了以上算法之后，我们就可以使用计算机来解决一些较大规模的问题了，完整代码如下：
"""解决商人安全过河问题"""
import random
class Boat(object):
def __init__(self, merchants, servants, capacity):
self.merchants = merchants
self.servants = servants
self.capacity = capacity
print "Initialize: [%d] merchants and [%d] servants" %(merchants, servants)
'''创建允许状态集合'''
def allowset(self):
allowset = []
for i in range(self.merchants + 1):
for j in range(self.servants + 1):
if i == 0:
allowset.append([i,j])
elif i == self.merchants:
allowset.append([i,j])
elif (i &= j and ((self.merchants-i) &= (self.servants-j))):
allowset.append([i,j])
return allowset
'''创建允许决策集合'''
def allowaction(self):
allowactionset = []
for i in range(self.capacity + 1):
for j in range(self.capacity + 1):
if (i+j) &= self.capacity and (i + j) != 0:
allowactionset.append([i,j])
return allowactionset
'''渡河'''
def solve(self,allowactionset,allowstate):
count = 1;
current = (self.merchants,self.servants)
while current != [0,0]:
move = allowactionset[random.randint(0,len(allowactionset)-1)]
temp = [current[0]+((-1)**count)*move[0],current[1]+((-1)**count)*move[1]]
if(temp in allowstate):
current = [current[0]+((-1)**count)*move[0],current[1]+((-1)**count)*move[1]]
if(count % 2 == 1):
print "[%d]个商人，[%d] 个随从从此岸划到对岸" %(move[0],move[1])
elif(count % 2 == 0):
print "[%d]个商人，[%d] 个随从从对岸划回此岸" %(move[0],move[1])
count = count + 1
'''主方法'''
def main():
boat = Boat(3,3,2)
allowstate = boat.allowset()
print "允许状态集合为："
print allowstate
actionset = boat.allowaction()
print "允许决策集合为："
print actionset
boat.solve(actionset,allowstate)
if __name__ == '__main__':
为了缩短运行结果的篇幅，我们同样采取小规模问题来验证算法的正确性，这里还是采用原问题规模，运行结果如下：
允许状态集合为：
[[0, 0], [0, 1], [0, 2], [0, 3], [1, 1], [2, 2], [3, 0], [3, 1], [3, 2], [3, 3]]
允许决策集合为：
[[0, 1], [0, 2], [1, 0], [1, 1], [2, 0]]
[1]个商人，[1] 个随从从此岸划到对岸
[2]个商人，[0] 个随从从此岸划到对岸
[2]个商人，[0] 个随从从对岸划回此岸
[2]个商人，[0] 个随从从此岸划到对岸
[0]个商人，[2] 个随从从此岸划到对岸
该算法可以解决问题，但是有很多的不足，首先，由此算法得到的结果是随机的，它只是一个可行解，并不是最优解，并且其中很可能存在重复的步骤，对于一些超大规模的问题，它会产生许多重复的计算，其中会存在许多重复与环，还有许多可以改进的方法。这里我提出一种改进方法的思路，留待思考：我们可以借助图论中的深度优先算法来改进该问题从而得到最优解。如果不一定需要最优解的话，我们还可以在该算法上应用一个队列的数据结构，记录曾经在当前状态采取的策略，从而避免采取重复决策。
本文的版权归作者
所有，采用 。任何人可以进行转载、分享，但不可在未经允许的情况下用于商业用途；转载请注明出处。感谢配合！
我的热门文章
即使是一小步也想与你分享