나는 이것이 일반적으로 너비가 넓은 것으로 끝난다는 것을 알고있다. 그러나 우리는 둘 다로해야만한다. 나는 이미 너비를 먼저 달성했다. ...깊이 최단 경로를 찾으려면 먼저 검색 하시겠습니까?
나는 깊이 첫 번째 검색을 사용하는 전형적인 예다. 그래서 나는 여기서 도움을 얻을 수 있기를 바랐다 ... 나는 깊이 우선 검색을 사용하여 미로를 통과하는 최단 경로를 찾으려고 시도하고있다. 그러나 지금 당장은 그것을 정확히 어떻게 수행 할 것인지에 대해 머리를 감쌀 수 없다. 지금
void maze::findPathRecursive(graph &g, int position, int goal) {
if (position == goal) {
isPath = true; //returns true if there is a path to the goal
correctPath.push_back(position); // the path to the goal
} else {
g.mark(position);
g.visit(position);
//gets all the neighbors of the current position
vector<int> neighbors = getNeighbors(position, g);
while (!neighbors.empty()) {
int n = neighbors.back();
neighbors.pop_back();
if (!g.isVisited(n)) {
findPathRecursive(g, n, goal);
}
if (isPath) {
correctPath.push_back(position);
break;
}
}
}
}
는, 어떤이가하는 일은 거기에서 목표 및 휴식 시간에 그것을 할 수있는 최초의 경로를 찾을 수 있습니다 : 이것은 지금까지 내 코드입니다. 내가 휴식을 제거해야 할거야 그리고 내가 가장 짧은 경로를 저장하고 이전과 가장 짧은 이전의 길이를 비교하는 다른 벡터를 만들려고했는데 어떤 점에서 노드를 비켜 필요가 있기 때문에 그것이 작동하지 않았다 여기 정확히 어떻게해야 하는지를 알 수는 없습니다.
도움을 주시면 대단히 감사하겠습니다 !!
g는 미로를 포함하는 방식으로 나타낸 그래프입니다.
그래프가 비순환인지 확인할 수 있습니까? – nobillygreen
@nobillygreen 잘 작동하는 방식은 큰 원을 만들었지 만 첫 번째 노드는 방문한 것으로 표시되어 다시 방문 할 수 없으므로 예 그렇습니다 – seanscal