3

StartNodeとEndNodeの間のパスが存在するかどうかを「テスト」する単純な DFS (非再帰的) を実装しました。期待どおりに動作します（双方向/方向グラフの処理）-しかし、後で使用するためにパスを保存する方法がわかりません。

現在、訪問したノードをデバッグ印刷していますが、保存すべきものではありません。

誰かが私を助けてくれます/少し光を当ててください-正確に何を保存し、どの時点で NodeStart から NodeEnd までのノードのリストを返す必要がありますか?

グラフの例を次に示します。

グラフ

DFS トラバース関数は次のとおりです。

bool DFS(CNavigationGraph *pNavGraph, CNavigationGraphNode* pFromNode, CNavigationGraphNode* pToNode)
{
    assert(pNavGraph);
    assert(pFromNode);
    assert(pToNode);

    std::vector<CNavigationGraphNode*> vpVisitedNodes;
    std::vector<CNavigationGraphNode*> stack;

    stack.push_back(pFromNode);

    while(!stack.empty())
    {
        CNavigationGraphNode     *pTop = stack.back();
        stack.pop_back();

        // Ok We've reached pToNode - means, path pFromNode to pToNode available
        if(pTop == pToNode)
        {
            for(int a = 0; a < vpVisitedNodes.size(); a++)
            {
                CLogger::Instance()->Write(XLOGEVENT_LOCATION, "{VISITED} %s",vpVisitedNodes[a]->GetNodeName().data());
            }
            return true;
        }

        // Add to visited list
        vpVisitedNodes.push_back(pTop);

        // Look for adjacent Nodes for pTop
        std::vector<CNavigationGraphNode*> vpAdjacentNodes;
        pNavGraph->GetAdjacentNodes(pTop->GetNodeName(), vpAdjacentNodes);
        for(int x = 0; x < vpAdjacentNodes.size(); x++)
        {
            // Add to stack if not visited
            if(IsVisited(vpVisitedNodes, vpAdjacentNodes[x]) == false)
                stack.push_back(vpAdjacentNodes[x]);
        }
    }

    // Path not found
    return false;
}

デバッグ出力は次のとおりです。

Node1 と Node3 の間のパスを検索

<main> [] DFS TRAVERSE TEST (DIRECTIONAL)
<DFS> [] {VISITED} Node1
<DFS> [] {VISITED} Node4
<DFS> [] {VISITED} Node5
<main> [] Path from Node1 to Node3 - YES

Node3 と Node1 の間のパスを検索

<main> [] DFS TRAVERSE TEST (DIRECTIONAL)
<main> [] Path from Node3 to Node1 - NO
4

2 に答える 2

4

私があなたのアルゴリズムを正しく理解していれば (そしてそれは DFS です)、
開始点から最初の未訪問ノードの方向に一歩進んでいます。そのノードからターゲットへのルートがない場合は、一歩下がって次の未訪問ノードに移動しようとします。その間、どのノードが訪問されたかを注意深く管理します。

追加する必要があるのは、ステップを実行しているノードを常にプッシュし、ステップを戻す必要がある場合はスタックからポップするスタックだけです。このスタックは、start_node からターゲットへのルートを格納します。また、後退する場所を決定するのにも役立ちます。

これがあなたのコードです。最終的には私が思っていたよりも少し長くなりましたが、ここにあります:

// I call fromNode: start_node, toNode: target_node.

std::stack<CNavigationGraphNode*> DFS(CNavigationGraph *pNavGraph, CNavigationGraphNode* start_node, CNavigationGraphNode* target_node)
{
    using namespace std;

    stack<CNavigationGraphNode*> route; // route to target
    unordered_set<CNavigationGraphNode*> visited_nodes;  // hash set on who is visited
    vector<CNavigationGraphNode*> adjacent_nodes;

    CNavigationGraphNode* current_node = start_node;
    while(current_node!=target_node)
    {
      pNavGraph->GetAdjacentNodes(current_node->GetNodeName(), adjacent_nodes); 

      // "for each"; you can use any form of looping through the neighbors of current_node.
      bool found_non_visited = false;
      for(auto node : adjacent_nodes) 
      {
        if(visited_nodes.find(node) == visited_nodes.end())
        {
          route.push(current_node);
          visited_nodes.insert(node);
          current_node = node;
          found_non_visited = true;
          break;
        }
      }
      if(found_non_visited) 
        continue;

      if(route.empty())
        return route; // empty route means no route found
      current_node = route.pop();
    }
    route.push(target);
    return route;
}

pop_backこれで、開始から目標へ、または目標から開始へと進むことができますpop。ルートが空の場合、それは元の関数から false を返すことに対応します。

unordered_setとstackの参照。どちらも STL です。バケツで実装されるため、通常は赤黒木で実装されるセットやマップよりもはるかに高速です。

注意:は C++11 の拡張機能です。C++03 を使用している場合std::unordered_setは、より遅いものに自由に置き換えてください。std::set

于 2012-12-09T13:52:32.363 に答える
3

visited セットを持つ代わりに、parent マップを持つことができます(map:Vertex->Vertex)。

vノードからノードを発見した場合はu、 を追加するように、グラフをトラバースしながらマップを変更しますparent[v] = u。初期化parent[source] = NULL。

あとは反復するだけです (疑似コード):

current <- dest
while current != NULL:
   print current
   current <- parent[current]

逆の順序でパスが表示されます。パスの元の順序を実現したい場合は、(print ステートメントの代わりに) スタックに格納し、スタックを反復することができます。

これは、スレッドで BFS について説明されているアイデアと非常によく似ています: How can I find the actual path found by BFS?

于 2012-12-09T13:50:47.277 に答える