Iterative Tiefensuche

Question

Implementierung ich folgenden Pseudo-Code aus dem wikipedia page bin mit iterativer Vertiefung zuerst in der Tiefe für Graphen Suche zu implementieren

function IDDFS(root) 
    for depth from 0 to ∞ 
     found ← DLS(root, depth) 
     if found ≠ null 
      return found 

function DLS(node, depth) 
    if depth = 0 and node is a goal 
     return node 
    if depth > 0 
     foreach child of node 
      found ← DLS(child, depth−1) 
      if found ≠ null 
       return found 
    return null 

mein Code hier:

bool DLS(GrapheMat* graphe, Node* source, NomSom but, int limit) { 
    bool found = false; 
    printf("%s\n", (char*)source->etat); 
    if (strcmp((char*)source->etat, (char*)but) == 0) { 
     return true; 
    } 
    if (limit > 0) { 
     List* listSon = nodeSon(graphe, source); 
     while(!listEpmty(listSon)) { 
      Node* son = (Node*)popList(listSon); 
      if (DLS(graphe, son, but, limit-1)) { 
       return true; 
      } 
     } 
    } 
    return false; 
} 

bool IDDLS (GrapheMat* graphe, NomSom goal, int limit) { 
    bool found = false; 
    node* source = createNode(graphe, graphe->nomS[0]); 
    for (int i = 0; i <= limit; i++) { 
     printf("/nLimit : %d\n", i); 
     DLS(graphe, source, goal, i); 
    } 
    return false; 
} 

I verwende die folgende Grafik zum Testen:

Es ist aus der folgenden Datei erstellt:

A B C D E F G H I J ; 
A : B (140) C (118) D (75) ; 
B : A (140) E (99) F (151) G (80); 
C : A (118) ; 
D : A (75) F (71) ; 
E : B (99) H (211) ; 
F : D (71) B (151) ; 
G : B (80) I (146) J (97) ; 
H : E (211) J (101) ; 
I : G (146) J (138) ; 
J : G (97) H (101) I (138) ; 

Aufruf IDDLS(graphe, "J", 4) gibt der folgende:

/nLimit : 0 
A 

Das ist alles.

DLS(graphe, "A", "J", 4) Aufruf gibt die folgende (Zeilenumbrüche entfernt):

ABABAEFGCADAFEBAEFGHEJ 

Von dem, was ich verstehe, sollte die DLS-Funktion den folgenden Pfad tatsächlich folgen:

ABEGHCDEFGHIJ 

Answer 1

DLS(graphe, "A", "J", 4) ist den richtigen Weg nehmen. ABABAEFGCADAFEBAEFGHEJ ist korrekt.

4 3 2 1 0 

A     A 
├─ B    B 
│ ├─ A   A 
│ │ ├─ B   B 
│ │ │ ├─ A  A 
│ │ │ ├─ E  E 
│ │ │ ├─ F  F 
│ │ │ └─ G  G 
│ │ ├─ C   C 
│ │ │ └─ A  A 
│ │ └─ D   D 
│ │  ├─ A  A 
│ │  └─ F  F 
│ ├─ E   E 
│ │ ├─ B   B 
│ │ │ ├─ A  A 
│ │ │ ├─ E  E 
│ │ │ ├─ F  F 
│ │ │ └─ G  G 
│ │ └─ H   H 
│ │  ├─ E  E 
│ │  └─ J  J 
C F 
D G 

---

In IDDLS ersetzen

DLS(graphe, source, goal, i); 

mit

if (DLS(graphe, source, goal, i)) { 
    return true; 
} 

Es gibt keine Notwendigkeit zu halten suchen tiefer, wenn Sie den Knoten gefunden haben.

---

Der einzige Weg, IDDLS(graphe, "J", 4) konnte Ausgang, was sagen Sie es tut, ist, wenn das Programm durch ein Signal getötet wurde (beispielsweise von SIGSEGV) ^[1]. Überprüfen Sie dies (indem Sie den Beendigungscode des Prozesses überprüfen). Wenn das der Fall ist, gibt es ein Problem mit den Funktionen DLS Anrufe, oder es gibt ein Problem damit, wie sie sie aufruft.

---

Sie haben ein Speicherleck. Die List erstellt von nodeSon wird nie freigegeben.

---

Optimierte unnötige String-Vergleiche zu entfernen:

bool DLS(GrapheMat* graphe, Node* source, NomSom but, int limit) { 
    printf("%s\n", (char*)source->etat); 

    if (limit) { 
     List* listSon = nodeSon(graphe, source); 
     while (!listEpmty(listSon)) { 
      Node* son = (Node*)popList(listSon); 
      if (DLS(graphe, son, but, limit-1)) { 
       return true; 
      } 
     } 

     return false; 
    } else { 
     return strcmp((char*)source->etat, (char*)but) == 0; 
    } 
} 

bool IDDLS(GrapheMat* graphe, NomSom goal, int limit) { 
    node* source = createNode(graphe, graphe->nomS[0]); 
    for (int i = 0; i <= limit; ++i) { 
     printf("/nLimit : %d\n", i); 
     if (DLS(graphe, source, goal, i)) { 
      return true; 
     } 
    } 

    return false; 
} 

---

1. Nun, es ist auch möglich, eine der Funktionen, die Sie Anrufe rufen exit, einen Weitsprung führt, oder tut etwas ähnlich seltsam .