c++ - 实现迭代加深深度优先搜索

Question

我正在使用来自维基百科的以下伪代码 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 

Answer 1

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

---

1. 嗯，您调用的函数之一也可能调用 exit、执行跳远或执行类似的奇怪操作。