Rekursion abbrechen

...und selbst goto helfen dir dabei

Na dann doch lieber rekursion

Eigentlich ist doch der zweite vorschlag von dir nicht so schlecht, vielleicht resultFound als return wert zurückgeben. Und wenn Du das sauber machst, dann brauchst du das erste

if (resultFound)
    return;

auch nicht.

Nidhogger

Untitled schrieb:

Dazu muss ich für jeden Knoten jeden Weg ausprobieren(Breitensuche).

Breitensuche sucht ja normalerweise nach dem kürzesten Weg und nicht - wie die Tiefensuche - nach e i n e m Weg. Breitensuche prüft erst alle Wege der Länge 1, dann alle der Länge 2, etc. und wird normalerweise mit ner Queue implementiert.

Nid

Apollon

Breitensuche sucht nicht nach Wegen und Threadsteller auch nicht.

Nidhogger

Apollon schrieb:

Breitensuche sucht nicht nach Wegen und Threadsteller auch nicht.

Breitensuche wird zur Suche des kürzesten Wegs/Pfads benutzt. Auch wenn hier keine Wege gesucht werden, ist die übliche Implementierung einer Breitensuche mit Queue und nicht Rekursion.

Nid

Ersteinmal vielen Dank an alle!

@Nidhogger: Ich wollte zuerst auch die Breitensuche mit Hilfe einer Queue implementieren, hatte dabei aber keine Möglichkeit gefunden wie ich alle Knoten von Start bis Ziel der Reihenfolge nach speichern kann, ohne dafür extra eine weitere Liste zu benutzen oder die Konten zu verändern. Welche Möglichkeiten übersehe ich?

Mein Pseudocode würde dafür so aussehen:

füge Startknoten in Queue
while (Queue ist nicht leer)
  hole Element aus Queue
  for (alle Kanten von aktl. Knoten)
    if (Kante noch nicht besucht)
       Füge Kante in Queue ein
    end if
  end for
end while

imhotep

Was noch wichtig ist, dass dein Query nach FIFO funktioniert, weil sonst es keine Breitensuche wird, sondern einen Tiefensuche oder irgendein Mischmasch.

mantiz

classMember = 0;

bool someFooBarFunc(){ 

	for (...) {
		if (foo == SOME_VALUE) {
			classMember = ...; 
			return true;
		}
		if (someFooBarFunc()) {
			return true;
		}
	}

	return false;
}

Ist vielleicht nicht so besonders chic, aber so müsste es doch gehen, oder?

Nidhogger

Untitled schrieb:

@Nidhogger: Ich wollte zuerst auch die Breitensuche mit Hilfe einer Queue implementieren, hatte dabei aber keine Möglichkeit gefunden wie ich alle Knoten von Start bis Ziel der Reihenfolge nach speichern kann, ohne dafür extra eine weitere Liste zu benutzen oder die Konten zu verändern. Welche Möglichkeiten übersehe ich?

Du müsstest ja in jeden Knoten sowieso ein Attribut haben, mit dem du festhalten kannst, ob du einen Knoten bereits besucht hast. Wenn du dieses Attribut so verwendest, dass du dort abspeicherst, wie weit der Knoten vom Ursprungsknoten entfernt sind, dann brauchst du dich, nachdem du den gesuchten Knoten gefunden hast, einfach nur rückwärts an diesen Zahlen zurückzuhangeln.

Nid.

groovemaster

123456789 schrieb:

Na dann doch lieber rekursion

Wieso?

Na weils übersichtlicher ist als dieses goto gespringe.

CStoll

Brauchst du für dein Problem wirklich diese Graphen-Struktur? (besonders sind Graphen nicht gerade die ideale Grundstruktur für eine Suche)

groovemaster

123456789 schrieb:

Na weils übersichtlicher ist als dieses goto gespringe.

Uninteressant. Rekursion mag zwar übersichtlicher erscheinen, ist aber von der Logik her oftmals viel schwerer zu verstehen. Ausserdem sagt niemmand, dass du etliche goto's verwenden sollst, idR gibt es bessere Möglichkeiten. Wer aber glaubt, es führt kein Weg an goto in seinem Code vorbei, dann soll er's auch nutzen. Besser als irgendwelche Dummys einzuführen ist es allemal. Dabei zu beachten ist nur, niemals nach oben springen, denn sonst kann man tatsächlich schnell den Überblick verlieren.

CStoll

groovemaster schrieb:

CStoll schrieb:

Na weils übersichtlicher ist als dieses goto gespringe.

Wenn du schon zitierst, dann achte bitte darauf, wen (ich störe mich zwar nicht daran, daß mein Name genannt wird - aber bitte im richtigen Zusammenhang)

CStoll schrieb:

groovemaster schrieb:

CStoll schrieb:

Na weils übersichtlicher ist als dieses goto gespringe.

Wenn du schon zitierst, dann achte bitte darauf, wen (ich störe mich zwar nicht daran, daß mein Name genannt wird - aber bitte im richtigen Zusammenhang)

groovemaster schrieb:

Uninteressant. Rekursion mag zwar übersichtlicher erscheinen, ist aber von der Logik her oftmals viel schwerer zu verstehen. Ausserdem sagt niemmand, dass du etliche goto's verwenden sollst, idR gibt es bessere Möglichkeiten. Wer aber glaubt, es führt kein Weg an goto in seinem Code vorbei, dann soll er's auch nutzen. Besser als irgendwelche Dummys einzuführen ist es allemal. Dabei zu beachten ist nur, niemals nach oben springen, denn sonst kann man tatsächlich schnell den Überblick verlieren.

Also ich hab noch keinen Code (außer Assembler) gesehen, bei dem man ein goto nicht vermeiden hätte können. Man kann natürlich jede Rekursion mit hilfe eines Stacks in ein iteratives prog. umwandeln, aber obs dann übersichtilcher ist? Man sollte natürlich nur da Rekursion verwenden wo es wirklich besser ist oder sein muss.

imhotep

groovemaster schrieb:

Wer aber glaubt, es führt kein Weg an goto in seinem Code vorbei, dann soll er's auch nutzen.

Oder er soll sich wohl strukturierten Code ausdenken.

groovemaster

CStoll schrieb:

Wenn du schon zitierst, dann achte bitte darauf, wen

Solltest vielleicht nicht soviel posten.
Lass mich mal kurz nachrechnen, 12 Tage dabei, fast 400 Beiträge, dh 33 Beiträge pro Tag. Respekt!

1234567789 schrieb:

Also ich hab noch keinen Code (außer Assembler) gesehen, bei dem man ein goto nicht vermeiden hätte können.

Natürlich kannst du immer goto vermeiden, die Frage ist nur, zu welchen Kosten. Versteh mich nicht falsch, ich bin kein Verfechter von goto. Nur ist es unsinnig sich stur gegen die Verwendung von goto zu stellen, auch wenn der aussergewöhnliche Fall eintreten sollte, dass es mal die einfachste Lösung darstellt. Es geht auch nicht darum, seinen Code möglichst so aufzubauen, dass man goto erst gar nicht braucht. Das versteht sich eigentlich von selbst.

1234567789 schrieb:

Also ich hab noch keinen Code (außer Assembler) gesehen, bei dem man ein goto nicht vermeiden hätte können.

Was allerdings nicht für die Allgemeinheit zutreffen muss.

1234567789 schrieb:

Man kann natürlich jede Rekursion mit hilfe eines Stacks in ein iteratives prog. umwandeln

Kann sein, dafür ist ein Stack aber gar nicht notwendig.

1234567789 schrieb:

aber obs dann übersichtilcher ist?

Wie bereits gesagt, bei solchen Sachen geht es in erster Linie aber nicht um Übersichtlichkeit, sondern um Codeverständnis.

Apollon

So wie ich das sehe, sucht dein Algorithmus sehr lange nach etwas, was es nicht gibt, bzw. findet es sehr sehr oft.

In etwa so koennte eine Loesung aussehen.

void findNode(Node* start, Node* found, int id)
{
    if (start->id == id) {
        found = start;
        return;
    }

    start->visit();

    for (int i = 0; i < successors.size(); ++i) {
        if (!successor[i]->visited())
            findNode(successor[i], found, id);
    }
}

Dabei ist die erste Abbruchbedingung recht "weak". Es kann passieren (wird ganz sicher), dass er trotzdem alle Knoten besucht.

CStoll

groovemaster schrieb:

CStoll schrieb:

Wenn du schon zitierst, dann achte bitte darauf, wen

Solltest vielleicht nicht soviel posten.
Lass mich mal kurz nachrechnen, 12 Tage dabei, fast 400 Beiträge, dh 33 Beiträge pro Tag. Respekt!

Danke (*grml* warum gibt's hier keinen errötenden Smilie?)