JAVA DFS 没有打印出所需的行

Question

我正在 java 中针对 n-puzzle 问题编写 DFS 问题。我有以下代码：

public class Dfssolution
{
    public static int cost=0;

    public static String goal;
    public static int n=3;
    public static HashSet<String> closedlist= new HashSet<String>();
    public static boolean solved = false;
    public static String current;
    public static int spc;
    public static String temp;
    public static LinkedHashSet<String> openlist = new LinkedHashSet<String>();
    public Dfssolution()
    {    
    }
    public static void main(String args []){
        String start= "103256789";
        goal = "130256789";
        String temp;
        openlist.add(start);
        while (openlist.isEmpty() == false && solved == false){
            current= openlist.iterator().next();
            openlist.remove(current);
            cost++;
            if(current.equals(goal)){
                System.out.println(cost);
                solved=true;
                break;
            }
            else{

                closedlist.add(current);
                if(checkRight(current)==true && openlist.contains(current) == false && closedlist.contains(current) == false){
                    temp= right(current);
                    openlist.add(temp);


                }
                if(checkUp(current)==true && openlist.contains(current) == false && closedlist.contains(current) == false){
                temp= up(current);
                    openlist.add(temp);

                }
                if(checkDown(current)==true && openlist.contains(current) == false && closedlist.contains(current) == false){
                temp= down(current);
                    openlist.add(temp);

                }
                if(checkLeft(current)==true && openlist.contains(current) == false && closedlist.contains(current) == false){
                temp= left(current);
                    openlist.add(temp);

                }

            }
        }
    }

    public static String left(String s){
        String tem = s;
        spc=tem.indexOf("0");

        char [] x = tem.toCharArray();
        char a = x[spc];
        x[spc] = x[spc-1];
        x[spc-1] = a;
        tem= new String(x);
        return tem;


    }
    public static String right(String s){
        String tem = s;
        spc=tem.indexOf("0");

        char [] x = tem.toCharArray();
        char a = x[spc];
        x[spc] = x[spc+1];
        x[spc+1] = a;
        tem= new String(x);
        return tem;


    }
    public static String up(String s){
        String tem = s;
        spc=tem.indexOf("0");

        char [] x = tem.toCharArray();
        char a = x[spc];
        x[spc] = x[spc-n];
        x[spc-n] = a;
        tem= new String(x);
        return tem;


    }
    public static String down(String s){
        String tem = s;
        spc=tem.indexOf("0");

        char [] x = tem.toCharArray();
        char a = x[spc];
        x[spc] = x[spc+n];
        x[spc+n] = a;
        tem= new String(x);
        return tem;

    }
    public static boolean checkUp(String s){
        spc=s.indexOf("0");
        if(spc > n-1){
            return true;
        }
        else{
            return false;
        }
    }
    public static boolean checkDown(String s){

        spc=s.indexOf("0");
        if(spc < n*(n-1)){
            return true;
        }
        else{
            return false;
        }
    }
    public static boolean checkLeft(String s){
        spc=s.indexOf("0");
        if(spc !=0 &&(spc % n) !=0){
            return true;
        }
        else{
            return false;
        }
    }
    public static boolean checkRight(String s){
        spc=s.indexOf("0");
        if(spc !=n-1 && spc % n !=n-1){
            return true;
        }
        else{
            return false;
        }
    }
}

我正在测试它是否会 return 扩展节点数（称为 'cost'）以达到代码中的目标状态。我在一个简单的问题上测试了它

103
256
789

作为 start 状态和

130
256
789

作为 goal 状态该程序不会打印出应该为 2 的 cost（展开的节点数）。

注意 n 在 3x3 拼图问题中代表 3

Answer 1

您需要将语句 closedlist.add(current); 移动到 else 块的末尾。否则，每个条件都会检查 closedlist 是否包含 current（它包含，你只是把它放在这里），并且什么都不会放在 openlist.

中

此更改后分两步找到解决方案，但还有另一个错误需要解决 — 您在全局计算 cost，而如果您想找到最小值，则应为每个分支单独计算移动量。

JAVA DFS 没有打印出所需的行

JAVA DFS does not print out required line

java

algorithm

depth-first-search