Anzahl der Rekursionsaufrufe eines DFS Algorithmus

gamma21

Mitglied
Hallo,
ich habe wieder eine Aufgabe die mir Schwierigkeiten bereitet und hoffe, dass mir jemand einen Schubser in die richtige Richtung gibt.
Gegeben sei der Pseudocode mit G = Graph. G = (V,E) und s = Startknoten:
Code:
DFS(G,s):
Discovered[v]  <- false für alle Knoten v aus V
DFS1(G,s)

DFS1(G,u):
Discovered[u]  <- true
Führe Operation auf u aus (z.B. Ausgabe)
foreach Kante (u, v) inzident zu u
    if !Discovered[v]
    DFS1(G,v)

welcher nun modifiziert wird, indem in der letzten Zeile der Funktion DFS1
Code:
Discovered[u] <- false
eingefügt wird.
Wie oft tritt nun der Fall ein, dass DFS1 keinen weiteren Rekursionsaufruf tätigt, wenn dieser modifizierte Algorithmus (also DFS mit beliebigen Startknoten) auf den vollständigen ungerichteten Graphen (d.h. von jedem Knoten existiert eine Kante zu allen anderen Knoten) mit 15 Knoten ausgeführt wird?
Ich verstehe das für den unmodifizierten Code so:
Für einen ungerichteten Graphen A,B,C (im Dreieck gezeichnet) wird der Startwert A gewählt. A wird auf true gesetzt. Anschließend werden aller Nachbarn von A untersucht, in diesen Fall B. Wenn ein Nachbar auf false gesetzt ist, wird DFS1 nochmals aufgerufen und somit wird auch B true. Im nächsten Schritt wäre dann C dran.
So weit so gut. Für den modifizierten Code, ändert sich doch kaum was außer das im letzen Schritt C wieder auf false gesetzt wird, weil A ja schon besucht wurde. Stimmt das so weit?
Wenn ich das dann richtig verstehe, wird
Code:
Discovered[u] <- false
nur einmal aufgerufen und zwar dann, wenn alle Nachbarn besucht wurden.
 

mihe7

Top Contributor
Im unmodifizierten Fall, wird jeder Knoten nur einmal besucht, z. B. A -> B und B -> C. Dann sind alle Knoten markiert. Wenn Du dagegen im letzten Schritt die Markierung aufhebst, werden Knoten mehrfach besucht.

Code:
DFS1(G,A)
  A <- visited
  (A,B): B unvisited also
    DFS1(G,B)
      B <- visited
      (B,A): A visited -> NOP
      (B,C): C unvisited also
        DFS1(G,C)
          C <- visited
            (C,A): A visited -> NOP
            (C,B): B visited -> NOP
  (A,C): C visited -> NOP
vs

Code:
DFS1(G,A)
  A <- visited
  (A,B): B unvisited also
    DFS1(G,B)
      B <- visited
      (B,A): A visited -> NOP
      (B,C): C unvisited also
        DFS1(G,C):
          C <- visited
            (C,A): A visited -> NOP
            (C,B): B visited -> NOP
          C <- unvisited
      B <- unvisited
  (A,C): C unvisited also
    DFS1(G,C)
      C <- visited
      (C,A): A visited -> NOP
      (C,B): B unvisited also
        DFS1(G,B)
          B <- visited
            (B,A): A visited -> NOP
            (B,C): C visited -> NOP
          B <- unvisited
 

gamma21

Mitglied
Gut es ist keine Endlosschleife weil durch das foreach(u,v) die Anzahl der Aufrufe begrenzt ist. Gefragt ist ja jetzt, wie oft kein weiterer Rekursionsaufruf getätigt wird. Und die Rekursion wird ja jedesmal aufgerufen. Stimmt es dann, dass nie der Fall eintritt, dass kein weiterer Rekursionsaufruf getätigt wird.
 

gamma21

Mitglied
Aber nur dann wenn beide NOP sind also für
Code:
(B,A): A visited -> NOP
(B,C): C unvisited also
erfolgt ja ein Aufruf nämlich für C. Ich sehe hier nur nicht, wie ich eine allgemeine Aussage treffen kann.
 

mihe7

Top Contributor
Aber nur dann wenn beide NOP sind also für
Code:
(B,A): A visited -> NOP
(B,C): C unvisited also
erfolgt ja ein Aufruf nämlich für C. Ich sehe hier nur nicht, wie ich eine allgemeine Aussage treffen kann.
Die Frage war, wie oft kein rekursiver Aufruf erfolgt. Wurde ein Knoten bereits besucht, erfolgt kein weiterer rekursiver Aufruf. Du kannst diese Prüfung auch zu Beginn der Rekursion durchführen, dann wird es vielleicht deutlicher:
Code:
(B,A): also
  DFS1(G,A)
    A visited also NOP
D. h. für die Aufruf DFS1(G,B) würde zwar ein rekursiver Aufruf erfolgen, für diesen Aufruf DFS1(G,A) jedoch nicht mehr.
 

mihe7

Top Contributor
Nachtrag: es ist eine Interpretationsfrage.
Code:
foreach Kante (u, v) inzident zu u
    if !Discovered[v]
    DFS1(G,v)
    else
      anzahl++

vs.
Code:
called = false
foreach Kante (u, v) inzident zu u
    if !Discovered[v]
      DFS1(G,v); called = true
if !called
  anzahl++
 

gamma21

Mitglied
Hmm jetzt kenn ich mich gar nicht mehr aus.
Code:
DFS1(G,A)
  A <- visited
  (A,B): B unvisited also
DFS1(G,B)
Das ist mein 1. Rekursiver Aufruf.
Code:
 B <- visited
      (B,A): A visited -> NOP
      (B,C): C unvisited also
        DFS1(G,C):
Das mein 2.
Code:
C <- visited
            (C,A): A visited -> NOP
            (C,B): B visited -> NOP
          C <- unvisited
      B <- unvisited
  (A,C): C unvisited also
3.
Code:
DFS1(G,C)

      C <- visited

      (C,A): A visited -> NOP

      (C,B): B unvisited also
Hier mein 4.und jetzt mein
Code:
DFS1(G,B)
          B <- visited
            (B,A): A visited -> NOP
            (B,C): C visited -> NOP
          B <- unvisited
5.Rekursiver Aufruf.
Ich kann zwar aus dem zählen der Aufrufe feststellen, dass kein weiterer Aufruf erfolgt wenn der Knoten besucht wurde, aus dem Code sehe ich das aber nicht.
P.S: Für 5 Aufrufe bei 6 Möglichkeiten wird die Rekursion nur einmal nicht aufgerufen.
 

mihe7

Top Contributor
DFS1 wird doch jedesmal nicht aufgerufen, wenn der betreffende Knoten bereits als besucht markiert wurde.

aus dem Code sehe ich das aber nicht.
Selbstverständlich sieht man das:
Code:
    if !Discovered[v]
        DFS1(G,v)
DFS1(G,v) wird nur aufgerufen, wenn v noch nicht discovered ist. Umgekehrt wird DFS1(G,v) nicht aufgerufen, wenn v bereits discovered ist.
 

mihe7

Top Contributor
Vielleicht mal als Baum:
Code:
        A
       / \
      /   \
     /     \
    /       \
   B         C
  / \       / \
 /   \     /   \
A     C   A     B
=    / \  =    / \
    A   B     A   C
    =   =     =   =
Das = kennzeichnet die Stellen, an denen kein rekursiver Aufruf mehr erfolgt (sprich: die Blätter im Baum).
 

gamma21

Mitglied
Also 1.einmal danke für deine Geduld und die guten Erklärungsversuche.
Das heißt es findet hier 6 mal kein rekursiver Aufruf statt. Ich denke (hoffe) es ist kein Zufall, dass es genau 3 Faktorielle sind. Für 15 Knoten wären es dann 15!. Das wäre
1307674368000
mal KEINE Rekursion. Bin mir nicht ganz sicher ob das so stimmt.
 

mihe7

Top Contributor
Gegeben sei ein vollständig verbundener Graph G mit n Knoten. Für jeden dieser n Knoten existieren n-1 ausgehende Kanten, die traversiert werden können. Beispiel für zwei Knoten A und B: A <==> B, A hat Kante zu B und B hat Kante zu A, d. h. jeder Knoten besitzt eine ausgehende Kante.

Im Baum B (wie in #13 gezeigt) hat jeder Knoten, der kein Blattknoten ist, dem Graphen G entsprechend n-1 Nachfolger. Im Beispiel oben haben wir drei Knoten A, B und C. Dabei hat A hat die Knoten B und C als Nachfolger, B hat die Nachfolger A und C usw.

Besucht man nun einen Knoten, der kein Blattknoten ist, fallen für jeden seiner n-1 Nachfolger die rekursiven Aufrufe weg, die zu einem seiner Vorgänger führen. Mit jeder Ebene erhöht sich die Zahl der besuchten Knoten (= Vorgänger) um 1, womit sich gleichzeitig die Zahl der noch nicht besuchten Knoten um 1 verringert. Dies hat lediglich auf die Kanten der Wurzel keine Auswirkung.

Bei n Knoten hat die Wurzel n-1 Nachfolger. Für jeden dieser n-1 Knoten fällt 1 rekursiver Aufruf weg, so dass noch n-2 rekursive Aufrufe übrig bleiben. Für jeden dieser n-2 rekursive Aufrufe gäbe es wieder n-1 Nachfolger, wovon jetzt aber 2 rekursive Aufrufe wegfallen (es gibt jetzt zwei Vorgänger), so dass noch n-3 rekursive Aufrufe übrig bleiben usw. Der Spaß wird wiederholt, bis gar kein rekursive Aufruf mehr erfolgt.

D. h. wir sparen (n-1)*1 + (n-1)*(n-2)*2 + (n-1)*(n-2)*(n-3)*3 + ... = sum_{i=1}^{n-1} i * (n-1)! / (n-1-i)!

Für n=15: https://www.wolframalpha.com/input/?i=sum+i*(14!/(14-i)!),+i=1+to+14

Voraussetzung: ich habe mich nirgends vertan :)
 

gamma21

Mitglied
Nachdem das Beispiel in der Übung gestern aufgelöst wurde, möchte ich die Antwort nun auch noch bekannt geben. Richtig wäre (zumindest laut Lösung) 14 Faktorielle gewesen, was sich aus den Baum Ergibt.
 

mihe7

Top Contributor
Dann wurden vermutlich alle eingesparten Aufrufe (und nicht nur die nicht aufgerufenen) gezählt. Müsste ich jetzt nachrechnen, habe ich jetzt aber keine Zeit.
 
Ähnliche Java Themen
  Titel Forum Antworten Datum
O Minimale Anzahl an Operationen herausfinden Softwareentwicklung 7
Paule UML Anzahl der Instanzen einschränken Softwareentwicklung 19
N Dynamische Objekt anzahl erstellen Softwareentwicklung 4
X Programmieren eines Spieles Softwareentwicklung 25
J Programmierung eines MazeGames Softwareentwicklung 1
F Planung und Durchführung eines Projektes Softwareentwicklung 2
A Händische Programmierung eines 1:n-ORM Softwareentwicklung 3
? Fragen zur richtigen Umsetzung eines Projektes Softwareentwicklung 3
M Ada95 - Breite eines Baumes bestimmen Softwareentwicklung 3
B Konstruktion eines Epsilon Automaten & NFA Softwareentwicklung 2
B Signatur eines Abstrakten Datentyps Softwareentwicklung 10
S Länge eines char[][] Softwareentwicklung 12
F Aufwändes eines Software Projektes Softwareentwicklung 21
M Technische Abwicklung eines Onlinekaufs Softwareentwicklung 7
-horn- "Laufzeitberechnung" eines Programmes? Softwareentwicklung 5
U Komplexität eines Algorithmus Softwareentwicklung 1
Z Herangehensweise zum "entschlüsseln" eines Dateifo Softwareentwicklung 2
G Modellierung eines graphentheoretischen Problems Softwareentwicklung 5
V alle abgeleiten Klassen eines Interfaces finden? Softwareentwicklung 2
I Object mit Hilfe eines Class-Objectes instanzieren Softwareentwicklung 3
M Elemente eines Vektors zufällig anordnen Softwareentwicklung 2
M Software zur Erstellung eines Pflichtenhefts? Softwareentwicklung 15
F Zellen eines Excel-Sheets per VBA disablen (ausgrauen)? Softwareentwicklung 10
H Synchronisation eines Bitstreams Softwareentwicklung 4
B Programmierung eines 8051-Assemblers unter Java Softwareentwicklung 3
F Ist der Name eines Ojekts eine Eigenschaft Softwareentwicklung 7

Ähnliche Java Themen

Neue Themen


Oben