4

http://www.cstutoringcenter.com/problems/problems.php?id=103

不想点的人，基本上就是说有个垫脚石，“-”和士兵“#”，士兵只能向右移动。如果士兵在另一个士兵后面，他必须等待士兵先移动。结束条件是所有士兵都到达终点。

2 名士兵在 5 个垫脚石上移动的方式数。

1) ##---  #-#--  -##--  -#-#-  --##-  --#-#  ---##
2) ##---  #-#--  -##--  -#-#-  -#--#  --#-#  ---##
3) ##---  #-#--  #--#-  -#-#-  --##-  --#-#  ---##
4) ##---  #-#--  #--#-  -#-#-  -#--#  --#-#  ---##
5) ##---  #-#--  #--#-  #---#  -#--#  --#-#  ---##

我使用广度优先搜索，有 5 个石头，它在几秒钟内运行，但有 10 个石头，它需要几个小时，时间随着深度呈指数增长。我该如何处理？

我的代码：

状态.java

import java.util.ArrayList;


public class State {
    public int stones;
    public Soldiers[] soldiers;
    public String currentState =""; 
    public boolean visited = false;

    public State(int stones,int Numsoldiers){
        System.out.println(Numsoldiers);
        this.stones = stones;
        soldiers = new Soldiers[Numsoldiers];
        System.out.println("length" + soldiers.length);
        initState();
    }

    public State(int stones,Soldiers[] soldiers){
        this.stones = stones;
        this.soldiers = soldiers;
        paintState();
    }

    public void initState(){
        for(int i=0;i<soldiers.length;i++)
        {
            soldiers[i] = new Soldiers();
            soldiers[i].position =i;
            currentState+="#";
        }
        for(int j=soldiers.length;j<stones;j++)
        {
            currentState+="-";
        }
    }

    private void paintState(){
        for(int j=0;j<stones;j++)
        {
            currentState+="-";
        }
        char[] stateChar = currentState.toCharArray();
        currentState = "";
        for(int i=0;i<soldiers.length;i++){
            stateChar[soldiers[i].position] = '#';
        }
        for(int k=0; k<stateChar.length;k++){
            currentState += stateChar[k];
        }
    }

    public void printState(){
        System.out.println(currentState);
    }
    public ArrayList<State> getNextStates(){
        ArrayList<State> States = new ArrayList<State>();

        for(int i=0;i<soldiers.length;i++){
            Soldiers[] newSoldiers = new Soldiers[soldiers.length];
            for(int j=0;j<soldiers.length;j++){
                newSoldiers[j] = new Soldiers(soldiers[j].position);
            }
            if(!((newSoldiers[i].position+1)==stones))
            {
                if((currentState.charAt((newSoldiers[i].position+1))=='-'))
                {
                newSoldiers[i].move();
                States.add(new State(stones,newSoldiers));
                }
            }

        }
        if(States.size()==0)
        {
            TestSoldiers.count++;
        }
        return States;
    }

}

士兵.java

public class Soldiers {

    int position = 0;

    public Soldiers(){
        position =0;
    }

    public Soldiers(int pos){
        position = pos;
    }

    public void move(){
        position ++;
    }
}

TestSoldiers.java

import java.util.LinkedList;
import java.util.Queue;


public class TestSoldiers {



    public static int count=0;

    public static void main(String[] args){

        TestSoldiers t = new TestSoldiers();
    }
    public TestSoldiers()
    {
        State s = new State(10,3);
        breadthFirstTraversal(s);
        System.out.println(count);
    }

    public void breadthFirstTraversal(State rootNode){

        Queue<State> q = new LinkedList<State>();
        q.add(rootNode);
        while(!q.isEmpty()){
            State n = (State)q.poll();
            n.printState();
            for(State adj : n.getNextStates()){

                        q.add(adj);

                }

            }
        }



}

我怎样才能做到这一点，以便我只考虑每个状态一次，同时保持结束方式总数的完整性（在 TestSoldiers.java 中计数）？

对于那些想要修改参数的人来说，它是新的 State(n,k)，其中 n 是石头的数量，k 是士兵的数量。

4

3 回答 3

2

您可能会更好地使用组合学来计算路径的数量。

例如，假设有 2 个士兵和 5 个步骤。

表示第一个士兵移动了 y 的距离，第二个士兵移动了 x 的距离。

您正在尝试计算从 0,0 到 3,3 的单调路径的数量，以使 y 永远不会大于 x。

这是一个众所周知的问题，答案由加泰罗尼亚数字给出。在这种情况下，答案由 n=3 的加泰罗尼亚数给出，即 5。

当您有超过 2 名士兵时，您将需要使用多维加泰罗尼亚数字。可以在OEIS上找到有用的指南和公式：

T(m, n) = 0！* 1！* .. * (n-1)！* (m * n)！/ ( m!* (m+1)!* .. * (m+n-1)!)

于 2014-03-10T13:18:04.373 回答
2

记忆可能会派上用场。

想法是运行深度优先搜索以计算从当前状态到结束的方式数量，并存储此结果，然后在该状态重复时查找已计算的值。

例如，有一些2方法可以从 到达终点-#-#-，因此，当我们通过 到达那里时存储这个结果，当我们到达那里时-##--，我们可以简单地查找2via #--#-。

存储这些的最简单（但远非最有效）的方法就是拥有：

Map<Pair<Integer (Position1), Integer (Position2)>, Integer (Count)>

更一般地说，您也许可以将其Pair设为List.

更有效的方法是有一个位图，其中每个位对应于某个给定位置是否有士兵。So-#-#-对应于01010，它可以简单地以十进制存储在intas10中 - 如果有超过 64 块石头（即适合 a 的石头long），您可以使用 a BitSet。

于 2014-03-10T09:29:41.507 回答
0

我的解决方案在不到 1 秒的时间内运行 10 个位置。解决方案又快又脏，但算法才是你应该感兴趣的，对吧？

我的算法的想法是：

  1. 管理一组计算路径。从两个士兵都在最左边位置的路径开始。
  2. 如果要计算的路径集合不为空，则选择任何路径并将其从集合中删除。
  3. 如果路径终止（两个士兵都在最右边的位置）打印路径。继续 2。
  4. 如果可能，通过移动头部士兵来扩展路径并将其放入布景中。
  5. 如果可能，通过移动尾兵来延长路径并将其放入布景中。

而已。

public static void main(String[] args) {
    List<Node> nodes = Node.newRootNode(10);
    while (!nodes.isEmpty()) {
        Node node = nodes.remove(0);
        if (node.isLeaf()) node.printPath();
        else {
            if (node.headSoldierCanMove()) nodes.add(node.moveHeadSoldier());
            if (node.tailSoldierCanMove()) nodes.add(node.moveTailSoldier());
        }
    }
}

static final class Node {

    static List<Node> newRootNode(final int maxPos) {
        return new ArrayList<Node>() {{
            add(new Node(1, 2, maxPos, ""));
        }};
    }

    private final int maxPos;
    private final String path;
    private int tailPos = 1;
    private int headPos = tailPos + 1;

    private Node(int tailPos, int headPos, int maxPos, String path) {
        this.maxPos = maxPos;
        this.tailPos = tailPos;
        this.headPos = headPos;
        this.path = addPath(path);
    }

    boolean tailSoldierCanMove() {
        return tailPos < headPos - 1;
    }

    Node moveTailSoldier() {
        return new Node(tailPos + 1, headPos, maxPos, path);
    }

    boolean headSoldierCanMove() {
        return headPos < maxPos;
    }

    Node moveHeadSoldier() {
        return new Node(tailPos, headPos + 1, maxPos, path);
    }

    void printPath() {
        System.out.println(path);
    }

    boolean isLeaf() {
        return headPos == maxPos && tailPos == headPos - 1;
    }

    private String addPath(String prefix) {
        StringBuilder builder = new StringBuilder(prefix);
        for (int pos = 1; pos <= maxPos; pos++) {
            builder.append(tailPos == pos || headPos == pos ? "#" : "-");
        }
        return builder.append("  ").toString();
    }
}
于 2014-03-10T09:51:57.937 回答