maze solving algo

Hi,

gegeben: Labyrinth (eine zwei dimensionales Feld), wobei die Werte Wand, Frei, Besucht, Start und Ausgang haben kann.

problem: Finde einen einen Pfad vom Start zum Ausgang zu finden. von Position (x,y) darf man nur 1 Schritt nach: Link, Rechts, Rrauf, Runter gehen...

Warum findet DFS immer einen Pfad von Start zum Ausgang und BFS nicht?
Wie finde ich den kürzesten Pfad zum Ausgang?

Manuel Neuer schrieb:

Warum findet DFS immer einen Pfad von Start zum Ausgang und BFS nicht?

Weil Du was falsch gemacht hast.

Manuel Neuer schrieb:

Wie finde ich den kürzesten Pfad zum Ausgang?

Breitensuche sollte hier ausreichen, da Du hier quasi konstante Kantengewichte hast. Und sonst gibt's ja noch sowas wie den A*, der ganz gut bei Wegsuchen funktioniert, wenn man relativ einfach eine untere Schranke für eine Entfernung zwischen zwei Punkten angeben kann. Bei Dir bietet sich da die Manhatten-Distanz als Metrik an. Allerdings sind Irrgärten ja eigentlich absichtlich schwierig mit Sackgassen und "umständlichen Wegen" von A nach B. Deswegen verhält sich der A* hier wahrscheinlich nicht viel besser als eine einfache Breitensuche -- kommt natürlich auf den Irrgarten an.

warum BFS? ...geht doch auch mit DFS...

nightwish schrieb:

warum BFS? ...geht doch auch mit DFS...

Bei einer Breitensuche in einem Graphen, wo die Kantengewichte konstant sind, findest du den kürzesten Weg zuerst. Bei einer Tiefensuche nicht unbedingt.

oenone

Irgendein Weg -> DFS, z.B. zum Überprüfen ob überhaupt eine Verbindung zwischen zwei Punkte besteht.
Kürzester Weg -> BFS

Hi,
ich habe den solving algo recursive implementiert...
kann man das cleanup irgendwie besser loesen?

void cleanup(vector<pos> &path, pos curr) {
    for (auto it = path.rbegin(); it != path.rend(); it++) {
      if(*it == curr) {
        continue;
      }

      bool canDelete = true;

      vector<Direction> moveVec = {UP, DOWN, LEFT, RIGHT};
      for (auto m : moveVec) { 
        if (*it == (curr + getNextStep(m))) {
          canDelete = false;
        }
      }

      if (canDelete) {
        auto it2 = it++;
        path.erase(it.base());
        it = it2;
      } else {
        curr = *it;
      }
    }
  }

  bool findPathDFSRecur(const pos &startPos, const pos &endPos, vector<pos> &path) {
    pos currPos = startPos;
    return findPathDFSRecurInternal(startPos, endPos, currPos, path);
  }

  bool findPathDFSRecurInternal(const pos &startPos, const pos &endPos, pos &currPos, vector<pos> &path) {
    path.push_back(currPos);

    if (currPos == endPos) {
      cleanup(path, currPos);
      return true;
    }

    setVisited(currPos);

    vector<Direction> moveVec = {UP, DOWN, LEFT, RIGHT};
    for (auto m : moveVec) {
      if(canMove(currPos, m)) {
        pos newPos = move(currPos, m);
        if(!isVisited(newPos)) {
          return findPathDFSRecurInternal(startPos, endPos, newPos, path);
        }
      }
    }
  }

kleinen bug gefunden und gefixt:
wie kann ich BFS recursive implementieren?

bool findPathDFSRecur(const pos &startPos, const pos &endPos, vector<pos> &path) { 
    pos currPos = startPos; 
    return findPathDFSRecurInternal(startPos, endPos, currPos, path); 
  } 

  bool findPathDFSRecurInternal(const pos &startPos, const pos &endPos, pos &currPos, vector<pos> &path) { 
    path.push_back(currPos); 

    if (currPos == endPos) {
      return true; 
    } 

    setVisited(currPos); 

    vector<Direction> moveVec = {UP, DOWN, LEFT, RIGHT}; 
    for (auto m : moveVec) { 
      if(canMove(currPos, m)) { 
        pos newPos = move(currPos, m); 
        if(!isVisited(newPos)) { 
          return findPathDFSRecurInternal(startPos, endPos, newPos, path); 
        } 
      } 
    } 

    path.pop_back();
    return false;
  }

volkard

Manuel Neuer schrieb:

wie kann ich BFS recursive implementieren?

Ich dächte an ungefähr sowas (und gar nicht rekursiv):

//visited weggelassen, das muss noch rein, wenn der graf kreise haben kann.
queue<Pos> küste;//mit stack statt queue wirds zur tiefensuche
//mit heap statt queue kann man kantengewichte (unterschiedliches gelände) einbauen. 
//mit ner entfernungsabschätzung zum ziel ist man den berühmten A* ganz nahe. 
küste.push(start);
while(!küste.empty()){
   Pos p=küste.pop();
   for each n in p.nachbarn(){
      if(n==ziel) juhu();
      küste.push(n);
   }
}