迭代深化在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; 
}