Итеративный углубленный поиск в переполнении стека

Question

Итеративный углубленный поиск в переполнении стека

Хорошо, во-первых, я понятия не имею, что я делаю с повторным углублением. Я работал над тем, чтобы заставить этот кусок кода работать, но я не могу. Я посмотрел онлайн и не смог найти никакой ссылки для этого поиска в C ++.

void Graph::IDS(int x, int required, int depth = 1)
{
if(x == required) return;

cout << "Iterated Deepening Search for " << required << ", starting from vertex " << x << " : " << endl;

IDS_util(x, required, depth);

cout << endl;
}

void Graph::IDS_util(int x, int required, int depth)
{
stack s;
bool *visited = new bool[n+1];
int i, j, k;

for(i = 0; i <= n; i++)
visited[i] = false;

cout << "Depth = " << depth << ":  ";

visited[x] = true;

for (int c = 1; c <= n; c++){
s.push(x);

if(isConnected(x, c) && !visited[c])
{
for (j = 0; j < depth; j++){
k = s.pop();

if(k == required) return;

cout << "[" << k <<"] ";

for (i = n; i >= 0 ; --i)
if (isConnected(k, i) && !visited[i]) {
s.push(i);
visited[i] = true;
}
}
}
}

if(depth == n)  return;

cout << endl;

IDS_util(x, required, depth+1);
}

Выход из матрицы смежности:

0,1,1,1,0,0,0,0,0
0,0,0,0,1,0,0,0,0
0,0,0,0,0,1,1,0,0
0,0,0,0,0,0,0,1,0
0,0,0,0,0,0,0,0,1
0,0,0,0,0,0,0,0,0
0,0,0,0,0,0,0,0,0
0,0,0,0,0,0,0,0,0
0,0,0,0,0,0,0,0,0

который является направленной версией этого графика:

         [1]
/  |  \
[2]  [3]  [4]
/    / \     \
[5]  [6] [7]   [8]
/
[9]

является:

Iterated Deepening Search for 7, starting from vertex 1 :
Depth = 0:
Depth = 1:  [1]
Depth = 2:  [1] [2]
Depth = 3:  [1] [2] [5]
Depth = 4:  [1] [2] [5] [9]
Depth = 5:  [1] [2] [5] [9] [3]
Depth = 6:  [1] [2] [5] [9] [3] [6]
Depth = 7:  [1] [2] [5] [9] [3] [6]

Я теоретически знаю, что должен делать поиск, я могу кое-что сказать, чем занимается мой поиск, но я не могу понять, как это исправить. Любая помощь, которую кто-либо может оказать, будет высоко оценена.

1

c++graph iterative-deepening search tree

Решение

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

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

Источник

Accepted Answer

Я почти уверен, что это не самый эффективный способ, но я нашел способ, который работает.

void Graph::IDS(int x, int required)
{
if(x == required) return;

cout << "Iterated Deepening Search for " << required << ", starting from vertex " << x << " : " << endl;

for (int d = 0  ; d <= n ; d++)
if (IDS_util(x, required, d))
return;

cout << required << " was unable to be located via " << x << endl;
}bool Graph::IDS_util(int x, int required, int depth){

if(x == required) return true;

stack s, x_child;
bool *visited = new bool[n+1];
int i,k, d, sub_k;

for(i = 0; i <= n; i++) visited[i] = false;

visited[x] = true;

for (i = n; i >= 0 ; --i)
if (isConnected(x, i))
x_child.push(i);

cout << '[' << x << "] ";

while(!x_child.isEmpty()){
k = x_child.pop();
s.push(k);

for(d = 0; d < depth; d++){
sub_k = s.pop();
if(sub_k == required)  return true;

cout << '[' << sub_k << "] ";

for (i = 0; i <= n; i++){
if (isConnected(sub_k, i) && !visited[i]) {
if (i == required){
cout << "\n\n" << required << " is a child of " << sub_k << endl;
return true;
}

s.push(i);
visited[i] = true;
}
}
}
}
cout<<endl;
delete [] visited;

return false;
}

0