我正在用 java 编写一个 DFS 问题来解决 n-puzzle 问题。我有以下代码:
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;
}
}
}
我正在测试它是否会返回扩展的节点数(称为“成本”)以达到代码中的目标状态。我在一个简单的问题上测试了它
103
256
789
作为开始状态和
130
256
789
作为目标状态
该程序不会打印出应为 2 的 cost(展开的节点数)。
注意 n 在 3x3 拼图问题中代表 3
最佳答案
您需要将语句 closedlist.add(current); 移动到 else block 的末尾。否则，每个条件都会检查 closedlist 是否包含 current(它包含，你只是把它放在这里)，并且不会将任何内容放入 openlist。
此更改解决方案分两步找到，但还有另一个错误需要解决 — 您正在全局计算 cost，而如果要查找，则应为每个分支单独计算最少的移动量。
关于JAVA DFS 不打印出所需的行，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/33896908/