学校代码： 10128 学 号： [1**********]6
选修课结业论文
（
题 目：人狗鸡米过河问题 学生姓名：武彩 学 院：理学院 系 别：数学系
专 业：信息与计算科学 班 级：信计08-1
二 〇一二 年 5月
人狗鸡米过河问题
一. 摘要
本文主要对数学建模的基础模型跟“商人过河”类似简单问题的人 狗鸡米过河问题 ，在图论和数学游戏问题中，有不少渡河问题。渡河问题是在一定的限制条件下，要求给出最好解，反映在图论中就是求最短路线问题。对于这类问题，有多种解决方法，其中Dijkstra 递推算法是最常用的方法。50年代中期，由于计算机科学技术迅猛发展，出现了一门新兴的学科，叫做“人工智能”。人工智能研究的是如何使计算机具有人类的智能，使计算机像人类那样智能地工作，去完成那些需要人的智能才可以完成的工作。从另一个角度来说，人工智能研究如何使人的智能用计算机来实现。例如，本题中从初始状态(1，1，1，1) 到目标状态(0，0，0，0) 的搜索过程都可以用人工智能的方法——由计算机来实现。利用人工智能的方法还能证明定理(例如，平面几何中的定理) 。机器证明定理就是把人证明定理的过程通过一套符号体系，变成一系列能在计算机上实现的符号运算过程，从而把人的推理演绎过程机械化。这对我们所求的问题方便了很多。
关键词：最短路问题 Dijkstra递推算法 渡河问题
二 问题重述
人、狗、鸡、米均要过河，船需要人划，另外至多还能载一物，而当人 不在时，狗要吃鸡，鸡要吃米。请设计一个安全渡河方案，并使渡河次 数尽量少？
三 模型假设
问题的初始状态是人、狗、鸡、米均在本岸，要求经过一系列的过河运载(每次运载只能一人一物，而且不能把狗和鸡留在一起，也不能把鸡和米留在一起) ，最后达到目标状态，即人、狗、鸡、米均在对岸。为了将问题数学化，我们用四元数组(即由4个数所组成的数组来表示初始状态，目标状态以 及中间的各种可取状态。
假设一物在本岸时，用数字“1”表示；在对岸时，用数字“0”表示。于是，人、狗、鸡、米的状态可以用每个数取0或1的四元数组来表示。例如，(1，0，1，0) 表示人在本岸，狗在对岸，鸡在本岸，米在对岸，每个数取0或 1的四组数组共有16个：
(1，1，1，1) (0，0，0，0) (1，1，1，0) (0，0，0，1)
(1，1，0，1) (0，0，1，0) (1，0，1，1) (0，1，0，0) (1，1，0，0) (0，0，1，1) (1，0，1，0) (0，1，0，1) (1，0，0，1) (0，1，1，0) (1，0，0，0) (0，1，1，1)
四 模型建立与求解
由于鸡和米或者狗和鸡不能留在一起，所以(1，1，0，0) ，(0，0，1，1) ，(1，0，0，1) ，(0，1，1，0)(1，0，0，0) ，(0，1，1，1) 所表示的状态都是不允许的，而其他10个状态都是允许存在的，也就是说，是可取状态，它们分别是
(1，1，1，1) (0，0，0，0) (1，1，1，0) (0，0，0，1) (1，1，0，1) (0，0，1，0) (1，0，1，1) (0，1，0，0) (1，0，1，0) (0，1，0，1)
我们用10个顶点分别表示以上10个可取状态。如果一个可取状态可以经过一次过河运载转移到另一个可取状态，那么在表示这两个可取状态的顶点之间联结一条边，从而构成一个图(图29-1) 。例如，(1，0，1，1) 和(0，0，1，0) 之间联结一条边表示如果人把米从本岸运到对岸，那么可取状态(1，0，1，1) 就转移到可取状态(0，0，1，0) ；反过来，如果人把米从对岸运到本岸，那么可取状态(0，0，1，0) 就转移到可取状态(1，0，1，1) 。现在问题变为在图29-1中找一条从顶点(1，1，1，1) 通过相联结的边到顶点(0，0，0，0) 的路径，每条路径就是一个解。
解：从图29-1可以找到两条从顶点(1，1，1，1) 到顶点(0，0，0，0)
的路径(如图29-2所示) ，其中一条所表示的解为
(1)人把鸡运到对岸； (2)留下鸡，人返回； (3)人把狗运到对岸；
(4)留下狗，人把鸡带回；
(5)人把米运到对岸；
(6)人独自返回，留下米(还有狗) ； (7)人把鸡运到对岸。
只要把(3)，(4)，(5)分别改为 (3)人把米运到对岸；
(4)留下米，人把鸡带回； (5)人把狗运到对岸 就得到另一解。
这二解所需的运载次数相等，所以是等优的。
五 结果分析
以上我们采用图作数学模型，直观明了地解决了问题。由于人狗鸡米过
河问题比较简单，也可以用递推方法来解，这方法基于逻辑推理。 为了直观起见，我们可以如表29-1所示边画边思考。
由于狗鸡或鸡米不能留在一起，第1次过河只能是人把鸡运到对岸；第2次过河只能考虑留下鸡，人返回，否则人与鸡都返回，那么又恢复原状；第3次过河可以考虑人把狗运到对岸(如果考虑人把米运到对岸，那么可能得到另一解) ；第4次过河人不能把狗带回(否则又恢复第3次过河前的状态) ，也不能人独自返回(否则狗鸡留在一起) ，所以只能考虑人把鸡带回；同样，第5次过河也只能人把米运到对岸；第6次过河将是人独自返回；最后，只有人与鸡在本岸；于是，第7次过河只要人把鸡运到对岸，就完成了过河问题。
在第3次过河时，如果人把米运到对岸，则将得到另一解。
六 模型评价
第一种方法得到的解为最优解，并且运载的次数最少。
七 参考文献
[1]王金山 王雪琴 陈之宁. 《数学建模竞赛的做法与体会》. 大学数学,2004
[2]严忠权. 数学建模竞赛研究. 黔南民族师范学院学报,2005
学校代码： 10128 学 号： [1**********]6
选修课结业论文
（
题 目：人狗鸡米过河问题 学生姓名：武彩 学 院：理学院 系 别：数学系
专 业：信息与计算科学 班 级：信计08-1
二 〇一二 年 5月
人狗鸡米过河问题
一. 摘要
本文主要对数学建模的基础模型跟“商人过河”类似简单问题的人 狗鸡米过河问题 ，在图论和数学游戏问题中，有不少渡河问题。渡河问题是在一定的限制条件下，要求给出最好解，反映在图论中就是求最短路线问题。对于这类问题，有多种解决方法，其中Dijkstra 递推算法是最常用的方法。50年代中期，由于计算机科学技术迅猛发展，出现了一门新兴的学科，叫做“人工智能”。人工智能研究的是如何使计算机具有人类的智能，使计算机像人类那样智能地工作，去完成那些需要人的智能才可以完成的工作。从另一个角度来说，人工智能研究如何使人的智能用计算机来实现。例如，本题中从初始状态(1，1，1，1) 到目标状态(0，0，0，0) 的搜索过程都可以用人工智能的方法——由计算机来实现。利用人工智能的方法还能证明定理(例如，平面几何中的定理) 。机器证明定理就是把人证明定理的过程通过一套符号体系，变成一系列能在计算机上实现的符号运算过程，从而把人的推理演绎过程机械化。这对我们所求的问题方便了很多。
关键词：最短路问题 Dijkstra递推算法 渡河问题
二 问题重述
人、狗、鸡、米均要过河，船需要人划，另外至多还能载一物，而当人 不在时，狗要吃鸡，鸡要吃米。请设计一个安全渡河方案，并使渡河次 数尽量少？
三 模型假设
问题的初始状态是人、狗、鸡、米均在本岸，要求经过一系列的过河运载(每次运载只能一人一物，而且不能把狗和鸡留在一起，也不能把鸡和米留在一起) ，最后达到目标状态，即人、狗、鸡、米均在对岸。为了将问题数学化，我们用四元数组(即由4个数所组成的数组来表示初始状态，目标状态以 及中间的各种可取状态。
假设一物在本岸时，用数字“1”表示；在对岸时，用数字“0”表示。于是，人、狗、鸡、米的状态可以用每个数取0或1的四元数组来表示。例如，(1，0，1，0) 表示人在本岸，狗在对岸，鸡在本岸，米在对岸，每个数取0或 1的四组数组共有16个：
(1，1，1，1) (0，0，0，0) (1，1，1，0) (0，0，0，1)
(1，1，0，1) (0，0，1，0) (1，0，1，1) (0，1，0，0) (1，1，0，0) (0，0，1，1) (1，0，1，0) (0，1，0，1) (1，0，0，1) (0，1，1，0) (1，0，0，0) (0，1，1，1)
四 模型建立与求解
由于鸡和米或者狗和鸡不能留在一起，所以(1，1，0，0) ，(0，0，1，1) ，(1，0，0，1) ，(0，1，1，0)(1，0，0，0) ，(0，1，1，1) 所表示的状态都是不允许的，而其他10个状态都是允许存在的，也就是说，是可取状态，它们分别是
(1，1，1，1) (0，0，0，0) (1，1，1，0) (0，0，0，1) (1，1，0，1) (0，0，1，0) (1，0，1，1) (0，1，0，0) (1，0，1，0) (0，1，0，1)
我们用10个顶点分别表示以上10个可取状态。如果一个可取状态可以经过一次过河运载转移到另一个可取状态，那么在表示这两个可取状态的顶点之间联结一条边，从而构成一个图(图29-1) 。例如，(1，0，1，1) 和(0，0，1，0) 之间联结一条边表示如果人把米从本岸运到对岸，那么可取状态(1，0，1，1) 就转移到可取状态(0，0，1，0) ；反过来，如果人把米从对岸运到本岸，那么可取状态(0，0，1，0) 就转移到可取状态(1，0，1，1) 。现在问题变为在图29-1中找一条从顶点(1，1，1，1) 通过相联结的边到顶点(0，0，0，0) 的路径，每条路径就是一个解。
解：从图29-1可以找到两条从顶点(1，1，1，1) 到顶点(0，0，0，0)
的路径(如图29-2所示) ，其中一条所表示的解为
(1)人把鸡运到对岸； (2)留下鸡，人返回； (3)人把狗运到对岸；
(4)留下狗，人把鸡带回；
(5)人把米运到对岸；
(6)人独自返回，留下米(还有狗) ； (7)人把鸡运到对岸。
只要把(3)，(4)，(5)分别改为 (3)人把米运到对岸；
(4)留下米，人把鸡带回； (5)人把狗运到对岸 就得到另一解。
这二解所需的运载次数相等，所以是等优的。
五 结果分析
以上我们采用图作数学模型，直观明了地解决了问题。由于人狗鸡米过
河问题比较简单，也可以用递推方法来解，这方法基于逻辑推理。 为了直观起见，我们可以如表29-1所示边画边思考。
由于狗鸡或鸡米不能留在一起，第1次过河只能是人把鸡运到对岸；第2次过河只能考虑留下鸡，人返回，否则人与鸡都返回，那么又恢复原状；第3次过河可以考虑人把狗运到对岸(如果考虑人把米运到对岸，那么可能得到另一解) ；第4次过河人不能把狗带回(否则又恢复第3次过河前的状态) ，也不能人独自返回(否则狗鸡留在一起) ，所以只能考虑人把鸡带回；同样，第5次过河也只能人把米运到对岸；第6次过河将是人独自返回；最后，只有人与鸡在本岸；于是，第7次过河只要人把鸡运到对岸，就完成了过河问题。
在第3次过河时，如果人把米运到对岸，则将得到另一解。
六 模型评价
第一种方法得到的解为最优解，并且运载的次数最少。
七 参考文献
[1]王金山 王雪琴 陈之宁. 《数学建模竞赛的做法与体会》. 大学数学,2004
[2]严忠权. 数学建模竞赛研究. 黔南民族师范学院学报,2005