java - 进入一个无限循环，试图在 java 中实现 A 星

Question

我已经尝试了两天来让它运行，但我不能为我的生活。我想做的是使用 A 星算法和曼哈顿启发式解决一个 8 难题。

这是 A 星代码的一部分：

                        public void solve(){

    State s = duplicateState(stateToSolve);
    StringState ss = new StringState(s);
    makeQ(ss.getStringState(),null,s);//add the first State to queue
    //s.setG(0);
    //s.setF(s.gettG()+heuristicTwo(ss.getStringState(),goal));
    s.setF(heuristicTwo(ss.toString(),goal));
    while(!states.isEmpty()){
        LinkedList<State>child=new LinkedList<State>();
        State state = lowestF(states);
        StringState pre = new StringState(state);
        if (goalReached(state)&&!solved){
            s = state;
            solved=true;
            System.out.println("#########\n# Solved #\n#########");
            break;
        }
        //explore(state);
        child=neighbours(child,state);
        for(int i=0;i<child.size();i++)
        {
            child.get(i).setTotalCost(state.gettG()+findDistance(state,child.get(i)));
            if(open.containsKey(child.get(i)))
            {
                if(child.get(i).gettG()<=child.get(i).getTotalCost())
                    System.out.println(child.get(i).getSolution());
                    continue;
            }
            else if(close.containsKey(child.get(i)))
            {
                if(child.get(i).gettG()<=child.get(i).getTotalCost())
                    continue;
                System.out.println(child.get(i).getSolution());
                StringState next = new StringState(child.get(i));
                makeQ(next.getStringState(),pre.getStringState(),child.get(i));
                close.remove(child.get(i));
            }
            else
            {
                System.out.println(child.get(i).getSolution());
                StringState next = new StringState(child.get(i));
                makeQ(next.getStringState(),pre.getStringState(),child.get(i));
                child.get(i).setH(heuristicTwo(next.getStringState(),goal));
            }
            child.get(i).setG(child.get(i).getTotalCost());

        }
        close.put(ss.getStringState(),ss.getStringState());



    }
    solution = s.getSolution();
    if (solution.equals("")||solution.equals(null))
        System.out.println("no solution");
    else{
    System.out.println("Astar");
    System.out.println(solution);
    }
}

StringState 只是获取拼图板的状态并转换为字符串。为了让代码的其他部分在这里更清楚一点：

              private Queue<State> states;
private State stateToSolve;
boolean solved=false;
private final String goal = "0123456789ABCDEF";
private final String goal2 = "123456789ABCDEF0";

private Map<String,String> close;//to keep track of previous checked status
private Map<String, String> open;
private String solution;

//-1,-1 for decrement of coordinates
private final int up = -4;
private final int down = 4;
private final int left = -1;
private final int right = 1;

//CONSTRUCTOR
public Astar(State s){
    solution = "";
    states = new LinkedList<State>();
    stateToSolve = duplicateState(s);
    close = new HashMap<String, String>();
    open = new HashMap<String, String>();
    solve();

}

所有邻居函数所做的就是获取棋盘的状态并返回棋盘的邻居——这意味着将空白图块向左/右/上/下移动（如果可能）并在完成后返回棋盘状态。所以邻居是新的国家。

我面临的问题（我在运行程序并尝试在某些时候打印它的状态后才意识到）是它进入了一个无限循环 apter 2 move of the blank tile.For example,当我尝试找到字符串 str1 = "1 2 0 3 4 5 6 7 8 9 ABCDE F" 的路径；答案应该在左边，但我得到了

左左

左右

左下

左左

左右

左下

左左

它只是无限地继续下去..任何帮助将不胜感激..（（我正在使用这个 -伪代码）

标签： javainfinite-loopa-starheuristicssliding-tile-puzzle