4

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

クリックしたくない人のために説明すると、基本的に飛び石「-」と兵士「#」があり、兵士は右にしか移動できないと書かれています。兵士が別の兵士の後ろにいる場合、その兵士が先に動くのを待たなければなりません。終了条件は全兵士が終了した時。

2 人の兵士が 5 つの飛び石を移動できる回数。

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

私は幅優先検索を使用しています.5つの石では数秒以内に実行されますが、10の石では数時間かかり、時間は深さとともに指数関数的に増加します. どうすればこれに対処できますか？

私のコード:

States.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 のカウント) の整合性を維持しながら、各状態を 1 回だけ考慮するようにするにはどうすればよいですか?

パラメータを変更したい場合は、新しい State(n,k) です。ここで、n は石の数、k は兵士の数です。

4

3 に答える 3

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 に答える