1

我正在使用维基百科页面中的以下伪代码来实现对图形的迭代加深深度优先搜索

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
4

1 回答 1

2

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)可以输出您所说的内容的方法是程序是否被信号（例如 from SIGSEGV）[1]杀死。验证这一点（通过检查进程的退出代码）。如果是这种情况，则函数DLS调用存在问题，或者调用方式存在问题。

你有内存泄漏。Listcreated bynodeSon永远不会被释放。

优化以删除不必要的字符串比较：

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，执行一个跳远，或者做一些类似的奇怪的事情。
于 2017-04-26T02:40:09.100 回答