实现迭代深入深度优先搜索

我用下面的伪代码从维基百科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

实现迭代深入深度优先搜索

回答

相关问题