Java: первый обход в ширину с возвратом в лабиринт - PullRequest
Новая
       29

Java: первый обход в ширину с возвратом в лабиринт

1 голос
/ 05 января 2012

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

    public boolean traverseBreadth(){
    //traverse the floor from entrance to exit
    //stepping only on red tiles
    steps = new LinkedList<Tile>();
    possibleSteps = new LinkedList<Tile>();
     //reset markings
     reset();
    //push the entrance onto the stack
    entrance.setVisited();
    steps.add(entrance);

    System.out.println("add " + entrance);
    nextMoves(entrance);
    //keep going as long as we have a possibility to move
    //and we haven't reached the end yet
    while (!possibleSteps.isEmpty()&& (!possibleSteps.getLast().equals(exit)))
    {   
        Tile x = possibleSteps.removeLast();

        x.setMarked();   //walked on that square
        steps.add(x);  //walk to that square
        System.out.println("Walked to the square  " + x);
        //now figure out where you can walk from this square
        nextMoves(x);
        try {
               Thread.currentThread().sleep(1000);
               }
             catch (InterruptedException e) {
               e.printStackTrace();
               }





    }
    if (possibleSteps.getLast().equals(exit)){
        steps.push(possibleSteps.removeLast());
        System.out.println("made it from entrance to exit");
        System.out.println(steps.toString());
        return true;
    }
    else 
    {   JOptionPane.showMessageDialog(null,"sorry can't reach the exit");
        return false;
    }

}

1 Ответ

0 голосов
/ 05 января 2012

Это не поиск в ширину - сначала глубина.

Есть 2 места, которые, очевидно, сначала глубины

  • вы удаляете с конца границы (возможных тайлов), а не с начала.
  • у вас нет иерархии обхода (от родительского к дочернему) для перестройки пути обхода, только один «путь» с плитками. Следовательно, сначала глубина.

Что нужно изменить:

  • вместо LinkedList, измените его на словарь. Ключом словаря будет плитка, а значением будет родительский элемент плитки. Используйте это, чтобы восстановить ваш последний путь.
  • Ваша функция "moveNext", вероятно, правильная. Убедитесь, что он выдвигается до конца списка.
  • не извлекайте (getLast ()) из возможных шагов. Возможные шаги должны быть в порядке очереди. Извлеките первую плитку возможных шагов (сначала будут исследованы плитки, ближайшие к началу).

Что нужно улучшить:

  • вместо использования плитки для отслеживания исследований, используйте набор (назовите его ExploredTile), куда вы кладете плитки, которые вы прошли)
  • использовать очередь вместо списка.

Некоторый C # / псевдокод (потому что я не в IDE) 

Dictionary<Tile,Tile> path = ...;
Queue<Tile> frontier = ...;
Set<Tile> explored = ...;

path[start] = null;

while(frontier.Count > 0){
    var tile = frontier.Dequeue();

    if(explored.Contains(tile)){
        continue;
    }
    explored.add(tile);

    if (Tile == Exit){
        rebuildPath(Exit);
    }else{
        for (Tile t in Tile.neighbours){
            if (!explored.Contains(t)){
                frontier.Enqueue(t);
                path[t] = tile; // Set the path hierarchy
            }
        }
    }
}

RebuildPath 

LinkedList<Tile> finalPath = ...;

Tile parent = path[exitTile];
finalPath.push(exitTile);

while(parent != null){
    finalPath.push(parent);
    parent = path[parent];
}

finalPath.reverse();

Надеюсь, я правильно понял ... :)

...