java - n-puzzle 的 Java DFS 实现，带有 hashmap

Question

我正在用几种不同的算法编写程序来解决 n-puzzle 问题。我对 DFS 算法有疑问，因为它只能找到深度 1 到 4 的最简单组合的解决方案，然后显示堆栈溢出错误。此外，对于深度 4，它显示长度为 2147 的解，这显然是错误的。我没有想法有什么问题。

我HashMap用来保持探索的节点和回溯路径。这是我的 DFS 代码：

public class DFS extends Path{

    Node initial;
Node goal;
String order;
boolean isRandom = false;
ArrayList<Node> Visited = new ArrayList<Node>();
boolean goalFound=false;
public DFS(Node initial, String order, byte [][] goal_state){
    this.initial=initial;
    goal=new Node(goal_state);
    this.order=order;
    if(order.equals("Random"))isRandom=true;
    Visited.add(initial);
    path.put(this.initial, "");
    runDFS(initial);
}

public void runDFS(Node current){


    if(current.equals(goal))
    {
        goalFound=true;
        System.out.println("Goal");
        retracePath(current,true);
        return;
    }

    if(!current.equals(goal) && goalFound==false)
    {

        Node child;
        Moves m = new Moves(current);

        if(isRandom)order=randomOrder("LRUD");

        for (int i=0; i<4; i++)
        {
            String s = order.substring(i,i+1);
            if(m.CanMove(s)==true)
            {
                child=m.move();
                if(Visited.contains(child))
                    {
                        continue;
                    }
                    else
                    {
                        path.put(child,s);
                        Visited.add(child);
                        runDFS(child);
                    }
                }
            }
        }

    }
}

节点：

 public class Node {

    public byte[][] status;

    private int pathcost;

    public int getPathcost() {
        return pathcost;
    }

    public void setPathcost(int pathcost) {
        this.pathcost = pathcost;
    }

    public Node(byte[][] status)
    {


        this.status=new byte[status.length][status[0].length];
        for(int i=0;i<status.length;i++){
            for(int j=0;j<status[0].length;j++){

            this.status[i][j]=status[i][j];

            }       }           

    }

    @Override
    public boolean equals(Object other)
    {
        if (!(other instanceof Node))
        {
            return false;
        }
        return Arrays.deepEquals(status, ((Node)other).status);
    }

    @Override
    public int hashCode()
    {
        return Arrays.deepHashCode(status);
    }



}

和路径：

   public class Path {

    public HashMap<Node,String> path;


    public Path(){      
    path=new HashMap<Node, String>(100);
    }


public void retracePath(Node nstate, boolean print){


    String dir=path.get(nstate);
    String textPath="";
    int i=0;
        while(!dir.equals("")){

            textPath+=dir + ", ";
            boolean changed=false;
            if(dir.equals("L")) {dir="R"; changed=true;}
            if(dir.equals("R") && changed==false) {dir="L";}
            if(dir.equals("U")) {dir="D"; changed=true;}
            if(dir.equals("D") && changed==false) {dir="U";}


            Moves m=new Moves(nstate);
            m.CanMove(dir);
            nstate=new Node(m.move().status);


            dir=path.get(nstate);

            i++;


        }

        if(print==true) {textPath=textPath.substring(0,(textPath.length()-2));
        System.out.println(i);
        System.out.print(new StringBuffer(textPath).reverse().toString());}
}


public Node getParent(Node n){
    String dir=path.get(n);
    boolean changed=false;
    if(dir.equals("L")) {dir="R"; changed=true;}
    if(dir.equals("R") && changed==false) {dir="L";}
    if(dir.equals("U")) {dir="D"; changed=true;}
    if(dir.equals("D") && changed==false) {dir="U";}

    Moves m=new Moves(n);
    m.CanMove(dir);
    n=new Node(m.move().status);
    return n;
}

public String randomOrder(String order) {  
    ArrayList<Character> neworder = new ArrayList<Character>();  
    for(char c : order.toCharArray()) {  
        neworder.add(c);  
    }  
    Collections.shuffle(neworder);        
    StringBuilder newstring = new StringBuilder();  
    for(char c : neworder) {  
        newstring.append(c);  
    }  
    return newstring.toString();  
}  

}

如果您有任何想法是什么问题，哪里是错误，我将非常感激！