c++ - C++ 中的迭代加深搜索

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] 

理论上我知道搜索应该做什么，我可以稍微说出我的搜索在做什么，但我不知道如何修复它。任何人都可以提供任何帮助，我们将不胜感激。

Answer 1

我几乎可以肯定这不是最有效的方法，但我找到了一种可行的方法。

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