深度优先搜索以找到最短路径? [英] Depth First Search to find shortest path?

问题描述

我知道通常通常先用广度来做，但是我们都被要求同时做，我已经先完成了广度....

我觉得这是使用深度优先搜索的一个非常典型的示例，因此我希望可以在这里得到一些帮助...我试图使用深度优先搜索通过迷宫找到最短的路径，但是现在，我无法确定如何做到这一点.到目前为止，这是我的代码:

  void maze :: findPathRecursive(图表&g，int位置，int目标){如果(排名==目标){isPath = true;//如果有到达目标的路径，则返回trueCorrectPath.push_back(position);//目标的路径} 别的 {g.mark(位置);g.visit(position);//获取当前位置的所有邻居向量< int>邻居= getNeighbors(position，g);while(！neighbors.empty()){int n = neighbors.back();neighbors.pop_back();如果(！g.isVisited(n)){findPathRecursive(g，n，目标);}如果(isPath){CorrectPath.push_back(position);休息;}}}} 

现在，此操作是找到它可以到达目标的第一条路径，并从该处中断.我知道我需要摆脱中断，我尝试制作另一个向量来存储最短路径并将其与先前最短路径之间的长度进行比较，但是它没有用，因为我觉得我需要在某个时候取消访问节点但无法在这里弄清楚该怎么做.

任何帮助将不胜感激！

g是包含迷宫的图形.

解决方案

尽管您可以使用DFS查找路径(如果很幸运，可以找到一条最短的路径)，但通常不能保证最短的路径.BFS是您最好的选择.

但是，有一种方法称为迭代加深.来自维基百科:

迭代加深深度优先搜索 1 (IDDFS)是一个状态空间重复执行深度受限搜索的搜索策略，每次迭代增加深度限制，直到达到d，最浅目标状态的深度.IDDFS等效于广度优先搜索，但是使用更少的内存；在每次迭代中，以深度优先"的顺序访问搜索树中的节点搜索，但首先访问节点的累积顺序为有效地广度优先.

伪代码，同样来自维基百科:

 >IDDFS(根，目标){>深度= 0>for(i = 1，i <10，i ++){>DFS(限制= i)>}>} 

首先实现一个DFS(应该与BFS完全一样，但是使用堆栈而不是队列)，然后实现ID算法.希望这会有所帮助.

I know this is usually done with breadth first, but we are asked to do it with both, I already accomplished breadth first....

I feel like this is a pretty typical example of using a depth first search, so I was hoping I could get some help here... I am attempting to find the shortest path through a maze using depth first search, but as of right now I cannot wrap my head around how exactly to do it. This is my code so far:

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

Right now, what this does is find the first path it can to the goal and breaks from there. I know I'll need to get rid of the break and I tried making another vector to store the shortest path and compare the lengths between it and the previous shortest but it did not work because I feel like I need to unvisit nodes at some point but cannot figure out how exactly to do it here.

Any help is greatly appreciated!!

g is a graph by the way which contains the maze.

解决方案

While you can find a path (and if you're lucky a shortest path) using DFS, it does not guarantee a shortest path in general. BFS is your best bet.

There is however an approach called Iterative Deepening. From Wikipedia:

Iterative deepening depth-first search1 (IDDFS) is a state space search strategy in which a depth-limited search is run repeatedly, increasing the depth limit with each iteration until it reaches d, the depth of the shallowest goal state. IDDFS is equivalent to breadth-first search, but uses much less memory; on each iteration, it visits the nodes in the search tree in the same order as depth-first search, but the cumulative order in which nodes are first visited is effectively breadth-first.

Pseudocode, again from wikipedia:

> IDDFS(root, goal) {
>   depth = 0
>   for(i=1, i<10, i++)   {
>       DFS(limit=i)
>   }
> }

First implement a DFS (should be exactly like BFS, but use a stack instead of a queue), and then implement the ID algorithm. Hope this helps.

这篇关于深度优先搜索以找到最短路径?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！