Реализация итеративного углубления поиска в глубину

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

Вот мой код:

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

1

artificial-intelligence c++iterative-deepening

Решение

Другие решения

Других решений пока нет …

Источник

Accepted Answer

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 звонки, или есть проблема с тем, как он их называет.

У вас утечка памяти. List создано nodeSon никогда не освобождается

Оптимизирован для удаления ненужных сравнений строк:

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выполняет прыжки в длину или делает что-то странное.

2