Problem mit "Breitensuche"

[finix]

Bashar schrieb:

Naja, und dass Breitensuche hier nicht wirklich ein geeigneter Algorithmus ist, aber das wirst du schon noch merken.

Vielleicht für Kurzstrecken-Teleporter

[Bashar]

finix schrieb:

Du benutzt den falschen Algorithmus. http://de.wikipedia.org/wiki/Algorithmus_von_Dijkstra

Auch falsch
http://de.wikipedia.org/wiki/A*

[Turing]

Du benutzt den falschen Algorithmus. http://de.wikipedia.org/wiki/Algorithmus_von_Dijkstra

Nimm lieber A* - Suche. Als Heuristik verwendest Du die "Manhattan-Norm" / "Spaltensummennorm".

[finix]

Dijkstras Algorithmus funktioniert, und ist einem offensichtlichem Anfänger wohl erst einmal zugänglicher.

[Konrad Rudolph]

finix schrieb:

Dijkstras Algorithmus funktioniert, und ist einem offensichtlichem Anfänger wohl erst einmal zugänglicher.

Breitensuche funktioniert auch und ist ja wohl vor Dijkstra der erste Schritt.

[finix]

Konrad Rudolph schrieb:

finix schrieb:

Dijkstras Algorithmus funktioniert, und ist einem offensichtlichem Anfänger wohl erst einmal zugänglicher.

Breitensuche funktioniert auch und ist ja wohl vor Dijkstra der erste Schritt.

Das möchte ich sehen.

[Konrad Rudolph]

finix schrieb:

Konrad Rudolph schrieb:

finix schrieb:

Dijkstras Algorithmus funktioniert, und ist einem offensichtlichem Anfänger wohl erst einmal zugänglicher.

Breitensuche funktioniert auch und ist ja wohl vor Dijkstra der erste Schritt.

Das möchte ich sehen.

Hmm, ich habe wohl das Wörtchen "kürzesten" überlesen. Dann funktioniert Breitensuche natürlich nur noch in Spezialfällen (alle Kanten haben dieselbe Länge). Im einfachen Fall, in dem man durch ein Pixel-Array sucht, funktioniert sie natürlich aber trotzdem, das sollte offensichtlich sein, oder?

[finix]

Das ist für mich ehrlich gesagt nicht offensichtlich. Mir ist nicht ganz klar wie da ein Pfad herauskommen soll (außer natürlich in einem speziellen Fall ), daher wäre ich dir für eine kurze Erläuterung sehr dankbar.

[life]

finix schrieb:

Das ist für mich ehrlich gesagt nicht offensichtlich. Mir ist nicht ganz klar wie da ein Pfad herauskommen soll (außer natürlich in einem speziellen Fall ), daher wäre ich dir für eine kurze Erläuterung sehr dankbar.

http://de.wikipedia.org/wiki/Breitensuche

--> Breitensuche liefert kürzeste Weg von einem Knoten s zu allen anderen Knoten, sofern man keine Kantengewichte hat (bzw. alle gleich sind). Legt man hier also ein entsprechendes Grid rein, würd auch Breitensuche ohne weiteres funktionieren.

Der "Fehler" sieht eher so aus als wären im Graphen die Hindernisse garnicht berücksichtigt worden..

[Konrad Rudolph]

finix schrieb:

Das ist für mich ehrlich gesagt nicht offensichtlich. Mir ist nicht ganz klar wie da ein Pfad herauskommen soll (außer natürlich in einem speziellen Fall ), daher wäre ich dir für eine kurze Erläuterung sehr dankbar.

Na die Breitensuche liefert Dir doch auf Wunsch einen GAG und einen Endknoten. Dann musst Du Dich an den Kanten vom Endknoten aus einfach zur Wurzel hochhangeln und schon hast Du Deinen Pfad vom Ziel zum Start (welcher der kürzeste ist).

Pseudocode für die Breitensuche mit Endknoten und GAG:

Funktion Breitensuche(start, ende)
  W: leere Warteschlange
  B: leerer Baum
  Füge start W hinzu
  Füge start B hinzu
  Wiederhole
    Entnimm v aus W
    markiere v
    Wenn v = ende dann gib B zurück
    Für alle unmarkierten u in Adjazenzknoten(v)
      Füge u W hinzu
      Füge (v, u) B hinzu
    Wenn W leer, dann gib nix zurück

Sollte so klappen.

[Shakesbier]

life schrieb:

--> Breitensuche liefert kürzeste Weg von einem Knoten s zu allen anderen Knoten, sofern man keine Kantengewichte hat (bzw. alle gleich sind). Legt man hier also ein entsprechendes Grid rein, würd auch Breitensuche ohne weiteres funktionieren.

Der "Fehler" sieht eher so aus als wären im Graphen die Hindernisse garnicht berücksichtigt worden..

Hätte ich vielleicht am Anfang dazu sagen sollen. Genauso ist es nämlich, dass ich mich durch einen Raum mit einer bestimmten Rastergröße bewege, also in Grid ist vorhanden!

An einen anderen Algorithmus wie ja hier auch schon empfohlen wurde, hatte ich auch schon gedacht, aber da ich jetzt mit der Breitensuche angefangen habe, würde ich es auch gerne ersteinmal zum laufen bringen... Danach mache ich mir definitiv mal ein paar Gedanken zur Optimierung!

Nur warum die Hindernisse allen Anschein nach bei mir noch nicht berücksichtigt werden, konnte ich immer noch nicht raus finden...

@ Konrad Rudolph: Genauso habe ich es ja auch versucht (siehe meinen Pseudocode im ersten Beitrag). Und ich denke zumindest, dass ich das in meinem Code auch umgesetzt habe...

[Bashar]

Shakesbier schrieb:

Nur warum die Hindernisse allen Anschein nach bei mir noch nicht berücksichtigt werden, konnte ich immer noch nicht raus finden...

Bist du der Sache mit der Reihenfolge der Indizes mal nachgegangen?

[Shakesbier]

Nach stundenlangem debuggen habe ich den Fehler endlich gefunden...

// In dieser Tabelle steht die Reihenfolge in der die Umliegenden Felder abgearbeitet werden sollen

const int DirTable[8][2] = { 
{  0, -1},      // oben
{  1,  0},      // rechts
{  0,  1},      // unten
{ -1, -1},      // links         FEHLER: Hier muss natürlich {-1, 0} hin!!
{  1, -1},      // rechts-oben
{  1,  1},      // rechts-unten
{ -1,  1},      // links-unten
{ -1, -1} };    // links-oben

An der Stelle habe ich natürlich erst am Schluss gesucht.

Danke nochmal für die Hinweise zu effizienteren Algorithmen. Werde ich mir die nächsten Tage mal ansehn!