Путь записи графика DFS (Pathfinding)
я реализовал простой DFS (не рекурсивный), который «проверяет», если путь между StartNode а также EndNode существует. Это работает как ожидалось (обработка двунаправленных / направленных графиков) — но я просто не могу понять, как хранить путь для последующего использования.
В настоящее время я отлаживаю печать посещенных узлов, но это не то, что следует хранить.
Может ли кто-нибудь помочь мне / пролить немного света на то, что именно я должен хранить и в какой момент вернуть список узлов из 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;
}
Вот результат отладки:
Найти путь между узлом 1 и узлом 3
<main> [] DFS TRAVERSE TEST (DIRECTIONAL)
<DFS> [] {VISITED} Node1
<DFS> [] {VISITED} Node4
<DFS> [] {VISITED} Node5
<main> [] Path from Node1 to Node3 - YES
Найти путь между узлом 3 и узлом 1
<main> [] DFS TRAVERSE TEST (DIRECTIONAL)
<main> [] Path from Node3 to Node1 - NO
Решение
Если я правильно понимаю ваш алгоритм (и это DFS),
от начальной точки вы делаете шаг в направлении первого не посещаемого узла. Если нет маршрута к вашей цели от этого узла, вы отступаете назад и пытаетесь перейти к следующему не посещенному узлу, в то же время тщательно администрируя, какие узлы были посещены.
Все, что вам нужно добавить, это стек к которому вы всегда подталкиваете узел, к которому вы делаете шаг,
и вытолкни его из стека, если тебе пришлось отступить. Этот стек будет хранить ваш маршрут от начального узла до цели. Это также поможет вам определить, где сделать шаг назад.
Вот ваш код, наконец он стал немного длиннее, чем я думал, но вот он:
// 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 а также стек, оба в STL. Он реализован с использованием корзины, поэтому он намного быстрее, чем набор или отображение, которые обычно реализуются с красно-черными деревьями.
Примечание: std::unordered_set расширение C ++ 11, не стесняйтесь заменить его на более медленное std::set если вы используете C ++ 03.
Другие решения
Ну, вместо того, чтобы иметь visited задавать — Вы можете иметь parent карта (Карта: вершинно> Vertex).
Измените карту, пока вы пересекаете график, так что если вы обнаружили узел v от узла u, добавлять parent[v] = u, В этом parent[source] = NULL,
Теперь все, что вам нужно сделать, это итерация (псевдокод):
current <- dest
while current != NULL:
print current
current <- parent[current]
Это даст вам путь в обратном порядке. Вы можете сохранить в стеке (вместо оператора print) и выполнить итерацию стека, если хотите достичь первоначального порядка пути.
Это очень похоже на идею, объясненную для BFS в теме: Как я могу найти фактический путь, найденный BFS?