java - 到达终点位置的所有可能方式

Question

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

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

2 名士兵跨过 5 block 垫脚石的方式数。

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

测试士兵.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 是士兵的数量。

Answer 1

Memoization可能会派上用场。

这个想法是运行深度优先搜索来计算从当前状态到结束的方法数，并存储这个结果，然后如果该状态重复，则查找已经计算的值。

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

存储这些的最简单(但远非最有效)的方法就是:

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

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

一种更有效的方法是使用一个位图，其中每个位对应某个给定位置是否有士兵。所以 -#-#- 将对应于 01010，它可以简单地存储在 int 中作为 10十进制 - 如果有超过 64 颗 gem (即适合 long 的 gem )，您可以使用 BitSet .