Идя в бесконечный цикл, пытаясь реализовать звезду в Java - PullRequest
Новая
       68

Идя в бесконечный цикл, пытаясь реализовать звезду в Java

0 голосов
/ 19 мая 2018

Я два дня пытался запустить это, но я не могу ради своей жизни.то, что я пытаюсь сделать, это решить 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 isпросто принимает состояние доски головоломки и преобразует в строку.чтобы немного прояснить ситуацию, рассмотрим некоторые другие части кода: 

              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 бесконечного цикла.перемещения пустой ячейки. Например, когда я пытаюсь найти путь для строки Str1 = "1 2 0 3 4 5 6 7 8 9 ABCDEF";ответ должен быть слева направо, но я получаю

налево налево

налево направо

налево вниз

налево налево

влево вправо

влево вниз

влево влево

и это будет продолжаться и продолжать бесконечно .. Любая помощь будет оценена .. ((Я использовал это - псевдокод )

...