有3个容器(2个完整和1个空)并试图从它们创建x数量

Question

注意:我遇到了下面的问题,我想概括问题并实现它,但事实证明这并不容易.这个问题让我发疯了.这不是一个家庭作业问题只是好奇心.

题

有三个容器,其大小分别为10品脱,7品脱和4品脱.7品脱和4品脱的容器开始充满水,但10品脱的容器最初是空的.

由于容器上没有标记,您可以将一个容器的内容倒入另一个容器中,并在以下条件下停止:

1. 源容器为空
2. 目标容器已满

如果你想准确地分离出2品脱的水,你应该做出什么样的动作？

资料来源:第102页,问题3.8

解

使用有向图数据结构来回答该问题很容易,其中节点包含tuples以表示某个状态.

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

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

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

连接到初始状态(或节点)的节点:<7, 0, 4>,<4, 7, 0>,如可以从图中看到.

广义问题

但是假设如果想要概括问题,假设我们有三个容器,其大小分别是x,y和z品脱x >= y >= z.

y-pint和z-pint容器开始充满水,但x-pint容器最初是空的.

如果你想要准确地分离一品脱水,你应该做出什么样的动作？

建议广义版本的解决方案

到目前为止,这里(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,但是如何设置深度并使其以递归方式运行或如何使其运行直到考虑所有可能性而不进入无限循环.这个广义问题的算法是什么？

Answer 1

嗯...可能有更好的算法，但如果您只是想要任意深度递归而不进入无限循环，您可以使用广度优先搜索，仅访问每个节点一次，即如果尚未访问过该节点：

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