首页 文章

深度优先搜索以找到最短路径？

提问于
浏览 次
0

我知道这通常先用广度来完成，但我们被要求用两者做，我已经先实现了广度....

我觉得这是使用深度优先搜索的一个非常典型的例子，所以我希望我能在这里得到一些帮助...我试图通过深度优先搜索找到通过迷宫的最短路径，但是现在截至目前我无法理解如何做到这一点 . 到目前为止这是我的代码：

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是包含迷宫的方式的图表 .

graph shortest-path depth-first-search maze

4 回答

  • 1

    我不确定我是否完全理解这个问题，但通常情况下，你不会使用广度优先搜索（至少在最简单的情况下）？在我看来，任何试图找到最短路径的DFS都必须转变为某种BFS，因为DFS可能会“错过”快捷方式 .

    也许这个https://cs.stackexchange.com/questions/4914/why-cant-dfs-be-used-to-find-shortest-paths-in-unweighted-graphs和这个http://en.wikipedia.org/wiki/Shortest_path_problem有帮助 .

    回复于
  • 0

    虽然你可以使用DFS找到一条路径（如果你是幸运的最短路径），它通常不能保证最短的路径 . BFS是你最好的选择 .

    然而，有一种叫做Iterative Deepening的方法 . 来自维基百科：

    迭代加深深度优先搜索1（IDDFS）是一种状态空间搜索策略，其中重复运行深度限制搜索，随着每次迭代增加深度限制，直到达到最浅目标状态的深度d . IDDFS相当于广度优先搜索，但使用的内存要少得多;在每次迭代中，它以与深度优先搜索相同的顺序访问搜索树中的节点，但是首次访问节点的累积顺序实际上是广度优先的 .

    Pseudocode，再次来自维基百科：

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

    首先实现DFS（应该与BFS完全相同，但使用堆栈而不是队列），然后实现ID算法 . 希望这可以帮助 .

    回复于
  • 0

    一般情况下，您不希望使用DFS来查找最短路径（除非您的图形明确是非循环的，也是无向的，在这种情况下，您的目标只有一条路径可以开始 . ）这是可能的，但它变得非常做作 . 在最简单的层面上，DFS更擅长确定是否有路径然后确定最佳路径是什么 .

    我建议看看不同的广度优先搜索（BFS）算法 . 如果你的迷宫在网格上，A *可能是你最好的选择 .

    回复于
  • 0

    我认为你不需要“取消访问”一个节点，而是需要为每个节点存储到达那里所需的边数 . 如果通过较短的路径再次到达那里，则更新该节点的边缘计数以及从该节点到目标的最佳路径上的所有节点 .

    回复于

相关问题