Алгоритм лабиринта для нахождения всего пути (и кратчайшего пути)

Question

Привет всем в этом коде. Я хочу найти все пути для выхода из лабиринта, в некоторых случаях для одного выхода из дома у вас есть несколько путей. Я хочу выбрать кратчайший путь. Как мне добавить это будущее к приведенному ниже коду, приведенный ниже код мой алгоритм, чтобы найти путь, но он не находит все пути

public void searchPath(char[][] BW, int i , int j ){   // megdar avalie i = SX-1 ,megdar avalie j= SY-1

        if(i<0 || i>(N-1)) return;     // check out of bound
        if(j<0 || j>(N-1)) return;
        if(BW[i][j] == 'b') return;     // if cell is black return
        if(visit[i][j]== true) return;

        visit[i][j] = true;

        path.add(i+","+j);

        if( !(i==SX-1 && j==SY-1 )){
            if(i==0 || i==N-1 || j==0 || j==N-1) {

                    if(first){
                        //first = false;
                        drawWay(path);
                    }                       
            }
        } 
        searchPath(BW , i , j+1);          // right

        searchPath(BW , i-1 , j);          // search the up side of cell    

        searchPath(BW , i , j-1);          // left
        searchPath(BW , i+1 , j);           // search the down          

        path.remove(path.size()-1);        // remove the not necceccery path


    }

Answer 1

Я не уверен, правильно ли я понял - сначала вы сказали, что хотите найти все возможные пути выхода из лабиринта, но потом вы упомянули, что нашли самый короткий путь.

На самом деле обе ваши проблемы могут быть решены одним и тем же подходом. В настоящее время вы используете глубинный поиск в вашем алгоритме ( http://en.wikipedia.org/wiki/Depth-first_search). Он идет как можно глубже, и когда нет другого пути, он возвращается обратно - отсюда и название.

Вместо этого следует использовать поиск в ширину ( http://en.wikipedia.org/wiki/Breadth-first_search). Таким образом, вы пройдете лабиринт в слоях - в ith "круглый", вы будете посещать все позиции, которые i квадраты от домашней площади. Поэтому, когда вы сейчас доберетесь до пограничной площади, это должен быть кратчайший путь. BFS может быть реализована с использованием очереди.

Чтобы найти все возможные решения, вам нужно будет использовать дополнительное пространство, чтобы запомнить, с какой позиции вы попали на текущую. Затем, когда вы захотите найти путь домой из позиции i, j, вы напишите текущую позицию для вывода, а затем посмотрите массив предыдущих позиций для i, j. Теперь у вас есть предшественники i, j - k, l и вы делаете то же самое с ними - выведите k, l и посмотрите в массив для предшественников k, l. Повторяйте это, пока не вернетесь домой.

Я бы отправил вам немного кода, но я не знаю Java, поэтому не хочу вас смущать.;)