|
9．是否达到孤立结点
孤立结点是指当路径进入该点后，无法继续前进，此时路径必须向后回退，同时标记该点为孤立结点。在路径搜索时，要避开已知的孤立结点。
public boolean isIsolated() {
int direction = this.nextDirection();
Dual status = this.nextStatus();
for(Node e: iNode) {
if(direction == e.direction && status.equals(e.status)){
return true;
}
}
return false;
}
10．实现Comparable接口
类Node实现Compareble接口，需要给出Compareble接口中的抽象方法compareTo()的具体实现。在程序中，使用集合(TreeSet)来保存孤立结点，Java集合(Set)调用方法compareTo()来判断元素是否重复，集合具有自动过滤重复元素的功能。需要指出的是，判断孤立结点时，需要考虑当前状态以及渡河方向。
public int compareTo(Node e) {
return this.toString2().compareTo(e.toString2());
}
private String toString2() {
return this.status
+ (direction == FORWARD ? " ---> " : " <--- ");
}
11．类路径
类Path使用穷举法，搜索一条路径，解决商人过河问题。为了通用地解决该类问题，类Path的构造方法允许指定商人人数、随从人数和小船的可载人数。路径结点的初始状态由给定的商人人数和随从人数构成的二元组；终止状态为渡河完成，即二元组（0，0）。
类Path使用数组carryingSchema来表示小船可提供的载人方案。
使用数组链表（ArrayList）对象path来保存渡河路径，ArrayList为有序的数据结构，而渡河路径也要求有序性。
使用集合（TreeSet）来储存在搜索过程中遇到的孤立结点，集合不允许重复元素，符合储存孤立结点的数据结构的要求。
类Path的构造方法，调用方法buildCarryingSchema()，构造小船的可行渡河方案后；再调用方法findPath()来搜索过河路径；最后，如果path不空，即存在过河路径，则输出结果。
class Path {
Dual carryingSchema[]; //小船可提供的载人方案
Dual initStatus; //初始状态
Dual endStatus; //终止状态
List<Node> path = new ArrayList<Node>(); //过河路径
Set<Node> iNode = new TreeSet(); //孤立结点
public Path(int merchant, int servant, 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);
}
}
…
}
12．构建渡河方案
方法buildCarryingSchema()，根据小船的最大可载人数且小船不能空计算出小船的所有可行的载人方案，每个方案表示为一个Dual对象，这些方案保存在数组carryingSchema中。在类Node中，通过数组下标来引用小船的载人方案。数组既可正向遍历，亦可反向遍历。所有的载人方案，按总人数进行降序排列。
public void buildCarryingSchema(int carrying) {
int size = (2 + carrying + 1) * carrying / 2; // 方案总数
carryingSchema = new Dual[size];
// 小船载人方案: 按人数降序排列
for(int i=0, total=carrying; total>0; total --) {
for(int m=total; m>=0; m--) {
carryingSchema[i++] = new Dual(m, total -m);
}
}
}
13．搜索过河路径
方法findPath()使用穷举法，搜索一条即初始状态initStatus至终止状态endStatus的迁移路径。
变量step表示渡河步骤，从0开始，step为偶数，表示小船前行；step为奇数，表示小船返回。当小船前行时，正向遍历carryingSchema，当小船返回时，反向遍历carryingSchema，搜索可行的渡河方案，以求最快的渡河路径。
在找到可行的方案后，则path中增加一个结点，步骤step递增。当状态将迁入endStatus时，则结束搜索，此时已找到一条路径。
如果无法找到可行的方案，则当前结点为孤立结点，则从path中删除，置入孤立结点集合中，同时step回退一步，继续搜索可行的渡河方案。当step<0时，则表示无法找到可行的渡河方案，path将为空。
public void findPath() {
Dual curStatus = initStatus; // 当前状态,初值为初始状态
int step = 0;
Node node = null, rnode=null;
// 穷举法,寻找渡河路径
while(step >=0) {
int direction = (step%2 == 0 ? Node.FORWARD : Node.BACKWARD);
int idx;
// 方向为FORWARD时,顺序搜索数组carryingSchema
if(direction == Node.FORWARD) {
idx = 0;
// rnode不空,表示发送路径回退,需要跳过该结点已尝试的方案
if(rnode != null) { idx = rnode.idx + 1; rnode = null;}
}
else {// 方向为BACKWARD时,逆序搜索数组carryingSchema
idx = carryingSchema.length -1;
// rnode不空,表示发送路径回退,需要跳过该结点已尝试的方案
if(rnode != null) { idx = rnode.idx - 1; rnode = null;}
}
boolean found = false;
while(!found && idx >= 0 && idx < carryingSchema.length) {
node = new Node(curStatus, direction, idx);
if( node.isValid() && // 渡河方案是否有效
node.isSecure() && // 状态是否安全
!node.isRepeat() && // 结点不能重复
!node.isIsolated()) // 非孤立结点
{
found = true;
}
else {
if(direction == Node.FORWARD) idx ++ ; // 顺序搜索
else idx --; // 逆序搜索
}
}
if(!found) { // 未找到可行的渡河方案
step --; // 回退一步, 并删除当前结点
if(step >= 0) {
rnode = path.remove(step);
iNode.add(rnode); // 孤立结点
}
continue;
}
path.add(node); // 把当前结点加入路径中
if(node.isEnd()) break; // 是否到达终止状态
curStatus = node.nextStatus(); // 当前状态变迁
step ++;
}
}
14．程序运行结果
最后给出程序运行结果：
(3, 3) ---> (1, 1)
(2, 2) <--- (1, 0)
(3, 2) ---> (0, 2)
(3, 0) <--- (0, 1)
(3, 1) ---> (2, 0)
(1, 1) <--- (1, 1)
(2, 2) ---> (2, 0)
(0, 2) <--- (0, 1)
(0, 3) ---> (0, 2)
(0, 1) <--- (0, 1)
(0, 2) ---> (0, 2)
|
