SamWN SamWN - 1 month ago 10
C++ Question

Iterative Deepening Search in C++

OK, so, first off, I have no real idea what I'm doing with iterated deepening. I've been working on trying to get this piece of code to work, but I can't. I looked online and couldn't find any reference for this search in 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);
}


The output from adjacency matrix:

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


which is a directional version of this graph:

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


is:

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]


I know theoretically what the search should be doing, I can somewhat tell what my search is doing instead, but I can't figure out how to fix it. Any help that anyone could provide would be deeply appreciated.

Answer

I'm almost certain that it's not the most efficient way to go about it, but I found a way that works.

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