|
当使用类Dual的成员m表示商人人数，s表示随从人数时，则一个Dual对象就可以用来表示商人和随从的组成状态，也可以表示一次渡河方案。类Dual的方法add()和minus()实现了状态变迁的计算。
2．类结点
类Node表示整个渡河方案中的每个步骤，每个结点由结点状态(商人和随从的人数组成) 、渡河方向和渡河方案组成。其主要代码如下：
class Node implements Comparable<Node>{
Dual status; // 结点状态
int direction; // 渡河方向
int idx; // 索引，指向小船的载人方案carryingSchema[]
public Node(Dual status, int direction, int idx) {
this.status = status;
this.direction = direction;
this.idx = idx;
}
public static final int FORWARD = 0; // 渡河方向：前进
public static final int BACKWARD = 1; // 渡河方向：返回
…
}
在前面分析中，渡河问题其实归结为一个路径查找问题，因此，需要在类Node中实现一系列与路径查找问题有关的方法。
3．状态迁移
计算当前状态，执行指定的渡河方案后，所迁入的状态。当渡河方向为FORWARD时，调用Dual对象的minus()方法；当渡河方向为BACKWARD时，调用Dual对象的minus()方法。数组carryingSchema为渡河方案，idx为指向数组carryingSchema的索引。
Dual nextStatus() {
return direction == FORWARD ?
this.status.minus(carryingSchema[idx]) :
this.status.add(carryingSchema[idx]);
}
4．结点是否相等
类Node需要实现equals()，以覆盖继承Java基类Object的equals()方法，实现对结点是否相等进行比较。
public boolean equals(Object e) {
if( this == e ) return true;
if( !(e instanceof Node) ) return false;
Node o = (Node)e;
return this.status.equals(o.status) &&
this.direction == o.direction &&
this.idx == o.idx ;
}
5．结点是否有效
判断结点是否有效，根据实际问题，当向前渡河时，要求本岸商人和随从人数分别大于等于渡河方案指定的商人和随从人数；当小船返回时，要求对岸商人和随从人数分别大于等于渡河方案指定的商人和随从人数
public boolean isValid() {
return this.direction == FORWARD ?
status.greaterOrEqual(carryingSchema[idx]): initStatus.minus(status).greaterOrEqual(carryingSchema[idx]);
}
6．状态是否安全
判断结点的状态是否有效，这是实际问题的一具体约束，即要求结点状态中商人人数或者为0，或者不小于随从人数。
public boolean isSecure() {
Dual next = this.nextStatus();
return (next.m==0 || next.m >= next.s) &&
(initStatus.m-next.m==0 || initStatus.m-next.m >= initStatus.s-next.s );
}
7．结点是否重复
判断结点是否已经包含在路径中。在路径查找问题中，需要避免出现环路，因此，需要消除结点重复。在下面的方法中，变量path指定路径，contains()方法暗含对Node的equals()方法的调用，来判断两个结点是否相等。
public boolean isRepeat() {
return path.contains(this);
}
8．是否达到终点
判断结点的下一状态是否达到目标状态，如果是，则结束路径搜索。
public boolean isEnd() {
return this.nextStatus().equals(endStatus);
}
|
