注意:遇到下面这个问题，想把问题归纳并实现，结果发现并不容易。这个问题让我发疯。这不是家庭作业问题，只是出于好奇。

问题

There are three containers whose sizes are 10 pints, 7 pints and 4 pints respectively. The 7-pint and 4-pint containers start out full of water, but the 10-pint container is initially empty.

Since there are no marks on the containers, you can pour the contents of one container into another and stop under the following conditions:

1. the source container is empty
2. the destination container is full

What sequence of moves should you make if you want to isolate exactly 2 pints of water?

Source: page 102, Question 3.8

解决方案

使用 directed graph data structure 很容易回答这个问题其中节点包含 tuples代表某种状态。

我们从初始状态(节点)开始，然后我们创建一个代表可能的下一个状态的节点，我们将它连接到初始节点，然后运行 ​​BFS寻找最短路径。

• 每个状态(或节点)的模式:<10-pint container, 7-pint container, 4-pint container>

• 初始状态或节点:<0, 7, 4> .

连接到初始状态(或节点)的节点:<7, 0, 4> , <4, 7, 0> , 正如您从图片中看到的那样。

一般性问题

But suppose if want to generalized the problem, suppose we have three containers whose sizes are x, y and z pints respectively such that x >= y >= z.

The y-pint and z-pint containers start out full of water but the x-pint container is initially empty.

What sequence of moves should you make if you want to isolate exactly a pints of water?

建议通用版本的解决方案

这里 ( DropBox , GitHub ) 是我目前的源代码。

这是主类中的两个重要方法。他们根据所有可能性填充图形，并且还确保没有重复节点。

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 的深度，但我如何设置深度并使其递归运行，或者如何使其运行直到考虑所有可能性而不进入无限循环。这个通用问题的算法是什么？

最佳答案

嗯...可能有更好的算法，但如果你只是想任意深度递归而不进入无限循环，你可以使用广度优先搜索只访问每个节点一次，即如果它还没有被访问过:

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);
    }
}

关于java - 有 3 个容器(2 个满的和 1 个空的)并尝试从中创建 x 数量，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/27347915/