Людоедов и миссионеров проблема бесконечного цикла - PullRequest
Новая
       44

Людоедов и миссионеров проблема бесконечного цикла

0 голосов
/ 22 сентября 2019

Я пытаюсь использовать Итеративный Поиск Углубления, чтобы найти состояние цели для Задачи Миссионеров-Людоедов, но она не работает правильно, она зацикливается бесконечно, и я действительно не знаю, почему.Помощь будет оценена.

Вот мои фрагменты кода:

Я подозреваю, что проблема заключается в следующем фрагменте кода.Я не очень хорошо разбираюсь в рекурсии, особенно когда задействованы узлы.stateForPrinting является объектом State.Я использую его, чтобы узнать, какое состояние является целевым, поэтому я могу напечатать путь, который ведет к цели, ссылаясь на его родителя, а затем на его родителя и так далее.

Это часть кода Итеративного углубления поиска: 

private boolean DLS(State curState, State endState, int depth){
    if(curState.Equal(endState))
        return true;

    if(depth <= 0)
        return false;

    successorGen(curState);//Generates successors
    for(State successor : curState.getSuccessors()){
        if(DLS(successor, endState, depth - 1)){
            stateForPrinting = successor;
            return true;
        }
    }
    return false;
}

private boolean IDS(State rootState, State endState){

    for(int depth = 0; depth < 100; depth++){
        if(DLS(rootState, endState, depth)){
            return true;
        }
    }
    return false;
}

successorGen () генерирует ход.Два человека могут поместиться в лодке.В ход может быть вовлечено два людоеда, два миссионера, каждый из которых, один людоед или один миссионер.

Это метод successorGen (): 

    private void successorGen(State curState){
        int nCan, nMiss = 0;
        //Loop through available variations
        for(int i = 0; i <= 2; i++){
            for(int j = 0; j <= 2; j++){
                if(i==0 && j==0)
                    continue;
                //Only two persons can fit into the boat
                if(i + j > 2)
                    break;
                nMiss = i;
                nCan = j;
                addState(nMiss, nCan, curState);
            }
        }
    }

Когда метод successorGen () вызывает методaddState (), число миссионеров и каннибалов либо вычитается, либо добавляется (в зависимости от состояния лодки) к ошибке родительского состояния.и может.сосчитать.Позднее результат добавляется в новый объект State.

Метод создания объектов State: 

private void addState(int nMiss, int nCan, State parent){
    int BoatState = parent.getBoatState() ? 1 : -1;
    String name = parent.getName() + "_";
    name += Integer.toString(parent.howManySuccessors());

    State newState = new State(name,
                            parent.getStateMiss() + nMiss * BoatState,
                            parent.getStateCan() + nCan * BoatState,
                            !parent.getBoatState(), parent);
    if(!newState.ValidState()){//ValidState returns true if the State is valid
        parent.AddSuccessor(newState);
    }
}

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

...