實現迭代深入深度優先搜索

我用下面的僞代碼從維基百科page實現了圖形反覆深入深度優先搜索實現迭代深入深度優先搜索

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

這裏是我的代碼：

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

我我使用下面的圖表來測試：

它從以下文件內置：

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)輸出以下：

/nLimit : 0 
A

這就是全部。

調用DLS(graphe, "A", "J", 4)輸出以下（換行刪除）：

ABABAEFGCADAFEBAEFGHEJ

從我的理解中，DLS功能實際上應該遵循以下路徑：

ABEGHCDEFGHIJ

來源

2017-04-26 Meryem

@ikegami我剛纔編輯與輸出後，孩子們都按字母順序排列 – Meryem

@ikegami對不起，我再次編輯後，希望這是足夠的信息 – Meryem

重新「*我的輸出是： /nLimit：0 A 這就是所有*「，除非進程被信號殺死，否則這是不可能的。那是怎麼回事？如果是這樣，什麼信號？ – ikegami

DLS(graphe, "A", "J", 4)走的是正確的道路。 ABABAEFGCADAFEBAEFGHEJ是正確的。

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

在IDDLS，更換

DLS(graphe, source, goal, i);

與

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

有沒有必要繼續尋找更深層次的，一旦你發現的節點。

的唯一途徑IDDLS(graphe, "J", 4)可以輸出你說做什麼是如果程序是由信號（例如，來自SIGSEGV）殺死^[1]。驗證這一點（通過檢查進程的退出代碼）。如果是這樣的話，功能DLS調用有問題，或者它如何調用它們有問題。

您有內存泄漏。由nodeSon創建的List永遠不會被釋放。

的最佳去除不必要的字符串比較：

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

那麼，它也有可能你撥打電話exit的功能之一，執行跳遠，或做一些類似的怪異。

來源

2017-04-26 02:40:09 ikegami

實現迭代深入深度優先搜索

回答

相關問題