は、反復深化深さ優先探索に

Question

の実装、私はグラフ

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 

のための反復深化深さ優先探索を実装するためにウィキペディアpageから次の擬似コードを使用しています。ここに私のコードです：

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; 
} 

私は次のグラフを使用してテストしています：

は、次のファイルから構築されています：すべてのです

/nLimit : 0 
A 

：

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) ; 

IDDLS(graphe, "J", 4)を呼び出すと、次のように出力します。 DLS(graphe, "A", "J", 4)を呼び出す

は、以下の（改行削除）を出力：

ABABAEFGCADAFEBAEFGHEJ 

私が理解から、DLS機能は、実際には次のパスに従ってください：

ABEGHCDEFGHIJ 

Answer 1

DLS(graphe, "A", "J", 4)は正しい道を取っています。 ABABAEFGCADAFEBAEFGHEJが正しいです。 IDDLSで

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 

---

、あなたはノードを見つけたら、より深い探して維持する必要はありません

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

と

DLS(graphe, source, goal, i); 

交換してください。

---

プログラムは（例えばSIGSEGVからの）信号によって殺された場合は、それがない言うことIDDLS(graphe, "J", 4)可能性が出力される唯一の方法^[1]。これを確認します（プロセスの終了コードを確認してください）。そのような場合は、関数DLSの呼び出しに問題があるか、呼び出す方法に問題があります。

---

メモリリークがあります。 nodeSonによって作成されたListは決して解放されません。

---

不要な文字列比較を削除するために最適化された

：あなたが呼び出しexit呼び出す機能の一つは、長いジャンプを実行し、または同様に奇妙な何かを

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. まあが、それも可能です。