有3个容器(2个满的和1个空的)，并试图从其中创建x值
注意：--我遇到了下面的问题，我想概括这个问题并实现它，但是事实证明，这并不容易。这个问题让我发疯了。这不是家庭作业问题，只是好奇。
问题
有三个容器，大小分别为10品脱、7品脱和4品脱。7品脱和4品脱的容器开始充满了水，但10品脱的容器最初是空的。 由于容器上没有标记，您可以将一个容器的内容倒入另一个容器，并在以下条件下停止：
- 源容器为空。
- 目标容器已满。
如果你想准确地分离2品脱的水，你应该采取什么步骤？
资料来源:第102页，问题3.8。
解决方案
使用有向图数据结构很容易回答这个问题，其中节点包含tuples来表示特定的状态。
我们从初始状态(节点)开始，然后创建一个表示可能的下一个状态的节点，并将其连接到初始节点，然后运行BFS以找到最短路径。
- 每个状态(或节点)的模式：
<10-pint container, 7-pint container, 4-pint container> - 初始状态或节点：
<0, 7, 4>。
连接到初始状态(或节点)的节点：<7, 0, 4>，<4, 7, 0>，从图片中可以看到。
泛化问题
但是假设如果想推广这个问题，假设我们有三个容器，它们的大小分别是x、y和z品脱，因此
x >= y >= z。 Y-品脱和z-品脱容器开始充满了水，但x-品脱容器最初是空的。 如果你想准确地分离出一品脱的水，你应该采取什么步骤？
建议通用版本的解决方案
以下是主类中两个重要的方法。它们根据所有可能性填充图表，并确保没有重复节点。
public static void fillGraph(int x, int y, int z) {
TupleContainer initialState = new TupleContainer(x, y, z);
TupleContainer currentState = initialState;
Iterator<TupleContainer> it, it_1, it_2, it_3;
Graph.addNode(initialState);
it = addAdjacentEdgesToTuple(currentState).iterator();
while (it.hasNext()) {
it_1 = addAdjacentEdgesToTuple(it.next()).iterator();
while (it_1.hasNext()) {
it_2 = addAdjacentEdgesToTuple(it.next()).iterator();
while (it_2.hasNext()) {
it_3 = addAdjacentEdgesToTuple(it.next()).iterator();
while (it_3.hasNext()) {
addAdjacentEdgesToTuple(it.next()).iterator();
}
}
}
}
public static Collection<TupleContainer> addAdjacentEdgesToTuple(
TupleContainer currentState) {
TupleContainer tempTupleContainer;
Collection<TupleContainer> CollectionLevel;
Iterator<TupleContainer> it;
CollectionLevel = currentState.MixUpContainers();
it = CollectionLevel.iterator();
while (it.hasNext()) {
tempTupleContainer = it.next();
if (graphContains(tempTupleContainer) != null)
Graph.addNode(tempTupleContainer);
else
tempTupleContainer = graphContains(tempTupleContainer);
Graph.addEdge(currentState, tempTupleContainer);
}
return CollectionLevel;
}我的问题
我的代码只将图填充到4的深度，但如何设置深度并使其递归运行，或者如何使其运行，直到考虑到所有可能性而不进入无限循环。这个广义问题的算法是什么？
回答 2
Stack Overflow用户
发布于 2014-12-07 22:40:38
嗯..。可能有更好的算法，但是如果您只是想要任意深度的递归而不进入无穷无尽的循环，您可以使用宽度优先搜索，只访问每个节点一次，也就是说，如果还没有访问过它：
public class Test {
public static void main(String[] args) throws Exception {
State initialState = new State(null, 0, 7, 4);
Set<State> reached = new HashSet<>();
Queue<State> pending = new ArrayDeque<>();
pending.add(initialState);
while (!pending.isEmpty()) {
State state = pending.remove();
if (isGoal(state)) {
printPathTo(state);
return;
}
for (State s : state.adjacentStates()) {
if (!reached.contains(s)) {
reached.add(s);
pending.add(s);
}
}
}
System.out.println("There appears to be no solution.");
}
private static boolean isGoal(State state) {
for (int a : state.content) {
if (a == 2) {
return true;
}
}
return false;
}
private static void printPathTo(State state) {
if (state != null) {
printPathTo(state.previous);
System.out.println(state);
}
}
}
class State {
final static int[] capacity = { 10, 7, 4 };
final int[] content;
final State previous;
public State(State previous, int... content) {
this.content = content;
this.previous = previous;
}
Iterable<State> adjacentStates() {
List<State> result = new ArrayList<>();
for (int i = 0; i < content.length; i++) {
for (int j = 0; j < content.length; j++) {
if (i != j) {
int[] newContent = Arrays.copyOf(content, content.length);
int movedQuantity = Math.min(content[i], capacity[j] - content[j]);
newContent[i] -= movedQuantity;
newContent[j] += movedQuantity;
result.add(new State(this, newContent));
}
}
}
return result;
}
@Override
public int hashCode() {
return Arrays.hashCode(content);
}
@Override
public boolean equals(Object obj) {
return Arrays.equals(content, ((State) obj).content);
}
@Override
public String toString() {
return Arrays.toString(content);
}
}Stack Overflow用户
发布于 2016-07-16 14:49:37
您也可以尝试迭代深化搜索，我们得到了它在uni中处理相同问题的演示，它运行得很好。
https://stackoverflow.com/questions/27347915
复制相似问题
腾讯云开发者
Copyright © 2013 - 2026 Tencent Cloud. All Rights Reserved. 腾讯云 版权所有
深圳市腾讯计算机系统有限公司 ICP备案/许可证号：粤B2-20090059 
粤公网安备44030502008569号
腾讯云计算（北京）有限责任公司 京ICP证150476号 | 京ICP备11018762号