Wie besucht die Tiefensuche einen Knoten?

Ein Algorithmus kann ein zweites Mal auf einen Knoten treffen, d. H. Es könnten zwei Pfade zu dem Knoten existieren. Der Algorithmus muss wissen, welcher Pfad kürzer war.Wie besucht die Tiefensuche einen Knoten?

Wenn die beste erste Suche einen Knoten erreicht, den sie zuvor besucht hat, ist es möglich, dass der vorherige Besuch einen längeren Pfad hatte. Wenn dies geschieht, müssen die offenen und geschlossenen Listen aktualisiert werden. Dies kann nicht mit einer A * Suche passieren.

Frage: Kann dies bei einem DFS passieren?

Die Antwort ist ja, aber ich dachte, es war nein. Warum ist es ja? Ich dachte, wenn ein Knoten einmal besucht wurde, wird er nicht mehr darauf zurückkommen.

Quelle

2017-12-15 blazing

'Dies kann nicht mit einer A * -Suche passieren.Wenn die Heuristik nicht optimal ist, aktualisiert A * diesen Knoten mit den kürzeren Kosten. Also wird A * auch die Dinge manipulieren, aber wenn die Heuristik optimal ist, wird es nicht funktionieren, weil wir wissen, dass es keinen anderen Knoten mit geringeren Kosten gibt. –

Die DFS-Strategie besucht einen Knoten so oft, wie er einen Pfad dazu findet. Es würde den Besuch von diesem Knoten nicht fortsetzen, aber es würde den Besuch selbst registrieren. Dies ist wichtig für DFS edge classification.

Betrachten wir zum Beispiel DFS läuft auf diesem Diagramm:

Wenn Sie Knoten C zum ersten Mal zu erreichen, ist der Weg A-B-C. Wenn Sie zum zweiten Mal C erreichen, ist der Pfad A-C, der kürzer ist.

Quelle

2017-12-15 19:07:46 dasblinkenlight

Wenn Sie ein Diagramm wie diese

A 
|\ 
B \ 
| E 
C/
|/ 
D

und durchqueren sie zuerst in der Tiefe, von links nach rechts, werden die folgenden pathes in dieser Reihenfolge besucht werden:

A 
AB 
ABC 
ABCD 
AE 
AED

Sie sehen, der erste Besuch von D ist auf einem längeren Weg (ABCD) als der zweite (AED).

Quelle

2017-12-15 19:08:11

Wie besucht die Tiefensuche einen Knoten?

Antwort

Verwandte Themen