2022年商人过河问题的Java编程解决 .pdf

《2022年商人过河问题的Java编程解决 .pdf》由会员分享，可在线阅读，更多相关《2022年商人过河问题的Java编程解决 .pdf（7页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、商人过河问题的Java编程解决转自：“电脑编程技巧与维护”http:/ 要为商人过河问题建立数学模型，归结为路径搜索问题，并给出一个通用的 Jav 程序来解决此类问题。关键词商人过河，二元组，链表，集合一、描述商人过河问题是一个传统的智力问题。其描述如下：三名商人各带一名随从乘船渡河， 只小船只能容纳二人， 由他们自己划行。 随从们密约， 在河的任一岸，一旦随从的人数比商人多， 就杀人越货。 但是如何乘船渡河的大权掌握在商人们手中，商人们怎样才能安全渡河呢？商人过河问题可以看作一个多步决策过程，通过一系列决策步骤逼近决策目标，并最终达到决策目标。 对于该问题的每一步决策， 就是要对船由此岸驶向

2、彼岸或由彼岸驶回此岸的人员 （包括商人和随从） 作出规划， 在保证商人安全的前提下，通过有限的步骤，实现人员全部过河的目标。二、分析针对这一具体问题，可以经过一番精心安排，找到一个解决方案。不过，本文希望对这一问题进行发展和延伸，建立起数学模型， 发现其中蕴含的规律， 并借助计算机的运算能力，找到一个通用的一般解法。在商人过河问题中，用一个二元组来表示岸上商人和随从的组成(m，s) ，其中 m表示商人人数， s 表示随从人数，每个组合可以视为一种状态。所有可能的状态可以表示为集合：S0=(m, s)0m 3; 0 s3 安全状态要求商人人数为0，或者大于等于随从人数，因此，所有的安全状态可以表

3、示为集合：S1=(m, s) m=0, s=0,1,2,3; m=3, s=0,1,2,3; m=s=1,2 二元组 (m，s) 也可以表示一次渡河方案，其中m表示船载的商人人数， s 表示船载的随从人数。则所有的渡河方案可以表示为集合：S2=(m , s)0m ；0s；0m+s 2 一次渡河决策可以表示为：(m, s)K+1 = (m , s)K - (-1)K(u, v)K K = 0,1,2,3,(m , s)K为第 K次渡河时，岸上的商人和随从的组成，(u, v)K为第 K次渡河方案，K从 0 开始。整个决策方案就是要找到有限步渡河决策，使商人和随从的人数组成从原始状态（3，3），经由

4、一系列中间的安全状态，迁移到最终状态（0，0）的过程。三、编程建立前面的数学模型后，即找到一条从状态（3，3）到（ 0，0）的路径，可以编写程序，利用计算机的计算能力，通过穷举法找到一条状态迁移路径。1类二元组类 Dual 实现问题分析中提到的二元组，其主要代码如下：class Dual int m , s;名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 1 页，共 7 页 - - - - - - - - - public Dual( int m, int s) this . m =

5、 m; this . s = s;/ 加法Dual add(Dual e) returnnew Dual( this . m + e. m , this . s + e. s ); / 减法Dual minus(Dual e) returnnew Dual( this . m - e.m , this . s - e.s ); , 当使用类 Dual 的成员 m表示商人人数， s 表示随从人数时，则一个Dual 对象就可以用来表示商人和随从的组成状态，也可以表示一次渡河方案。类Dual的方法 add() 和 minus() 实现了状态变迁的计算。2类结点类 Node表示整个渡河方案中的每个步骤

6、，每个结点由结点状态 (商人和随从的人数组成 ) 、渡河方向和渡河方案组成。其主要代码如下：class Node implements ComparableDual status ; / 结点状态int direction; / 渡河方向int idx ; / 索引，指向小船的载人方案carryingSchemapublic Node(Dual status, int direction, int idx) this . status = status;this . direction = direction;this . idx = idx; publicstaticfinalintFORW

7、ARD = 0; / 渡河方向：前进publicstaticfinalintBACKWARD = 1; / 渡河方向：返回, 在前面分析中，渡河问题其实归结为一个路径查找问题，因此， 需要在类 Node中实现一系列与路径查找问题有关的方法。3状态迁移计算当前状态，执行指定的渡河方案后，所迁入的状态。当渡河方向为FORWARD时，调用 Dual 对象的 minus() 方法；当渡河方向为BACKWARD时，调用Dual 对象的 minus() 方法。数组 carryingSchema 为渡河方案， idx 为指向数组carryingSchema 的索引。Dual nextStatus() 名师资

8、料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 2 页，共 7 页 - - - - - - - - - return direction = FORWARD ? this . status .minus( carryingSchema idx ) : this . status .add( carryingSchema idx ); 4结点是否相等类 Node需要实现 equals() ， 以覆盖继承 Java 基类 Object 的 equals() 方法，实现对结点是否相等进行比较。p

9、ublicboolean equals(Object e) if (this = e ) returntrue;if ( !(e instanceof Node) ) returnfalse;Node o = (Node)e;returnthis. status .equals(o.status ) &this . direction = o. direction&this . idx = o. idx ;5结点是否有效判断结点是否有效，根据实际问题，当向前渡河时，要求本岸商人和随从人数分别大于等于渡河方案指定的商人和随从人数；当小船返回时， 要求对岸商人和随从人数分别大于等于渡河方案指定的商

10、人和随从人数publicbooleanisValid() returnthis. direction = FORWARD ?status .greaterOrEqual(carryingSchema idx ): initStatus.minus( status ).greaterOrEqual(carryingSchema idx );6状态是否安全判断结点的状态是否有效，这是实际问题的一具体约束，即要求结点状态中商人人数或者为 0，或者不小于随从人数。publicbooleanisSecure() Dual next = this .nextStatus();return (next.m

11、=0 | next.m = next. s) &( initStatus. m -next. m =0 | initStatus. m -next. m = initStatus. s-next. s ); 7结点是否重复判断结点是否已经包含在路径中。在路径查找问题中，需要避免出现环路，因此，需要消除结点重复。在下面的方法中，变量path 指定路径， contains()方法暗含对 Node的 equals() 方法的调用，来判断两个结点是否相等。publicbooleanisRepeat() return path .contains(this );8是否达到终点判断结点的下一状态是否达到目

12、标状态，如果是，则结束路径搜索。publicbooleanisEnd() returnthis.nextStatus().equals(endStatus ); 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 3 页，共 7 页 - - - - - - - - - 9是否达到孤立结点孤立结点是指当路径进入该点后，无法继续前进，此时路径必须向后回退，同时标记该点为孤立结点。在路径搜索时，要避开已知的孤立结点。publicbooleanisIsolated() int direction

13、 = this .nextDirection();Dual status = this .nextStatus();for (Node e: iNode) if (direction = e.direction&status.equals(e.status )returntrue;returnfalse; 10实现 Comparable接口类 Node实现 Compareble接口，需要给出Compareble接口中的抽象方法compareTo() 的具体实现。 在程序中， 使用集合 (TreeSet) 来保存孤立结点， Java集合(Set) 调用方法 compareTo()来判断元素是否重

14、复，集合具有自动过滤重复元素的功能。需要指出的是，判断孤立结点时，需要考虑当前状态以及渡河方向。publicint compareTo(Node e) returnthis.toString2().compareTo(e.toString2();private String toString2() returnthis. status+ ( direction = FORWARD ? - : - ); 11类路径类 Path 使用穷举法，搜索一条路径，解决商人过河问题。为了通用地解决该类问题，类 Path 的构造方法允许指定商人人数、 随从人数和小船的可载人数。路径结点的初始状态由给定的商人人

15、数和随从人数构成的二元组；终止状态为渡河完成，即二元组（ 0，0）。类 Path 使用数组 carryingSchema 来表示小船可提供的载人方案。使用数组链表（ ArrayList）对象 path 来保存渡河路径， ArrayList为有序的数据结构，而渡河路径也要求有序性。使用集合（ TreeSet ）来储存在搜索过程中遇到的孤立结点，集合不允许重复元素，符合储存孤立结点的数据结构的要求。类 Path 的构造方法， 调用方法 buildCarryingSchema()，构造小船的可行渡河方案后；再调用方法findPath()来搜索过河路径；最后，如果path 不空，即存在过河路径，则输出

16、结果。class Path Dual carryingSchema ; / 小船可提供的载人方案Dual initStatus; / 初始状态名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 4 页，共 7 页 - - - - - - - - - Dual endStatus ; / 终止状态List path = newArrayList(); / 过河路径Set iNode = newTreeSet(); / 孤立结点public Path( int merchant, int s

17、ervant, int carrying ) initStatus = new Dual(merchant, servant); / 初始状态endStatus = new Dual(0, 0); / 终止状态/ 构建小船可提供的载人方案buildCarryingSchema(carrying);/ 搜索过河路径findPath();if (path .isEmpty() / 过河路径不存在System.out .println (Cannot solve the provlem.);else / 输出过河路径for (Node e: path ) System. out .println(e

18、); ,12构建渡河方案方法 buildCarryingSchema()，根据小船的最大可载人数且小船不能空计算出小船的所有可行的载人方案，每个方案表示为一个Dual 对象，这些方案保存在数组 carryingSchema 中。 在类 Node中， 通过数组下标来引用小船的载人方案。数组既可正向遍历，亦可反向遍历。所有的载人方案，按总人数进行降序排列。publicvoidbuildCarryingSchema( int carrying) int size = (2 + carrying + 1) * carrying / 2; / 方案总数carryingSchema = new Duals

19、ize;/ 小船载人方案 : 按人数降序排列for (int i=0, total=carrying; total0; total -) for (int m=total; m=0; m-) carryingSchema i+ = new Dual(m, total -m); 13搜索过河路径方法 findPath()使用穷举法，搜索一条即初始状态initStatus至终止状态endStatus 的迁移路径。变量 step 表示渡河步骤，从0 开始，step 为偶数，表示小船前行； step 为奇数，表示小船返回。当小船前行时，正向遍历carryingSchema ，当小船返回时，反向遍历 c

20、arryingSchema ，搜索可行的渡河方案，以求最快的渡河路径。在找到可行的方案后，则path 中增加一个结点，步骤step 递增。当状态将迁入 endStatus 时，则结束搜索，此时已找到一条路径。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 5 页，共 7 页 - - - - - - - - - 如果无法找到可行的方案，则当前结点为孤立结点，则从path 中删除，置入孤立结点集合中，同时step 回退一步，继续搜索可行的渡河方案。当step=0) int directi

21、on = (step%2 = 0 ? Node.FORWARD :Node. BACKWARD);int idx; / 方向为 FORWARD时, 顺序搜索数组 carryingSchemaif (direction = Node.FORWARD) idx = 0;/ rnode不空, 表示发送路径回退 , 需要跳过该结点已尝试的方案if (rnode != null ) idx = rnode.idx + 1; rnode = null ;else / 方向为 BACKWARD时, 逆序搜索数组 carryingSchemaidx = carryingSchema . length -1;/

22、 rnode不空, 表示发送路径回退 , 需要跳过该结点已尝试的方案if (rnode != null ) idx = rnode.idx - 1; rnode = null ;boolean found = false ;while (!found &idx= 0 &idx= 0) rnode = path .remove(step);iNode.add(rnode); / 孤立结点名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 6 页，共 7 页 - - - - - - - -

23、- continue ;path .add(node); / 把当前结点加入路径中if (node.isEnd() break ; / 是否到达终止状态curStatus = node.nextStatus(); / 当前状态变迁step +;14程序运行结果最后给出程序运行结果：(3, 3) - (1, 1)(2, 2) (0, 2)(3, 0) (2, 0)(1, 1) (2, 0)(0, 2) (0, 2)(0, 1) (0, 2) 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 7 页，共 7 页 - - - - - - - - -