java - ハッシュマップを使用した n-パズルの Java DFS 実装

Question

n-パズル問題を解決するためのいくつかの異なるアルゴリズムを使用してプログラムを作成しています。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();  
}  

}

何が問題で、どこが間違っているかについて何か考えがあれば、私はとても感謝しています!