21

BFS だけで加重なしのグラフで最短経路を見つけることができることは知っていますが、BFS または DFS のいずれかがこれを行うことができると人々が主張しているいくつかのサイトも読みました。これらはおそらく間違いであり、BFSだけがこれを行うことができることを確認したかっただけです（簡単なGoogle検索を行った後でも完全に自信がありませんでした）. 私が間違っている場合は、DFS が最短パスを提供する方法を説明してください。

4

6 に答える 6

32

DFSは、無向グラフで必ずしも最短経路を生成するとは限りません。ここではBFSが正しい選択です。

例として、三角形の角を取り、それらを接続することによって形成されたグラフを考えてみましょう。DFSを使用して、あるノードから別のノードへの最短パスを見つけようとすると、開始ノードと宛先ノードを直接接続するエッジをたどらない限り、間違った答えが得られます。

@nhahtdhが以下に示すように、反復深化と呼ばれるDFSの変形があり、ターゲットが見つかるまで最大深さ1、2、3などでDFSを実行します。これにより、常に最短パスが検出され、BFSよりも少ないメモリを使用して検出されます。

お役に立てれば！

于 2013-02-09T03:57:02.520 に答える
8

反復深化検索 (IDS) は、深さ制限検索 (基本的には DFS ですが、深さ制限 d に達した場合は検索を停止します) の多くのラウンドで構成され、深さを 1 から徐々に増やして、重み付けされていないグラフで最短経路を見つけます。 .

// Iterative deepening search
// isGoal is a function that checks whether the current node is the goal
function ids(graph, start, isGoal) { 
    maxDepth = 1
    do {
        found = dls(graph, start, isGoal, maxDepth, 0)
        // Clear the status whether a node has been visited
        graph.clearVisitedMarker();
        // Increase maximum depth
        depth = depth + 1

    // You can slightly modify the dls() function to return whether there is a
    // node beyond max depth, in case the graph doesn't have goal node.
    } while (found == null)

    return found
}

// Depth-limited search
// isGoal is a function that checks whether the current node is the goal
function dls(graph, currentNode, isGoal, maxDepth, currentDepth) {
    if (graph.visited(currentNode)) {
        return null
    }
    graph.setVisited(currentNode)

    if (isGoal(currentNode)) {
        return currentNode
    }

    // Stop searching when exceed max depth
    // This is the only difference from DFS
    if (currentDepth >= maxDepth) {
        return null
    }

    for (adjNode in graph.getAdjacent(currentNode)) {
        found = dls(graph, adjNode, goal, maxDepth, currentDepth + 1)
        if (found != null) {
            return found
        }
    }

    return null
}

開始ノードから許可される距離を徐々に増やすため、これは機能します。距離 a + 1 を持つノードは、深さの制限により、距離 a を持つノードの前に探索されません。

共通の懸念事項の 1 つは、距離 a のノードが (d - a + 1) 回再訪問されることです。ここで、d はゴールへの最短パスの深さです。パフォーマンスについて話したい場合は、グラフまたは検索ツリーに依存します。分岐因子の大きい探索木では、深さ d で生成された節点が支配的な項となるため、再訪の問題はあまりありません。このような場合、BFS は指数空間が必要なため使用できませんが、IDS は多項式空間のみを使用します。

于 2013-02-09T05:37:57.837 に答える
2

ここでのパーティーには遅れていることはわかっていますが。DFS と BFS にはいくつかの違いがあります (簡単な答え: どちらも重み付けされていないグラフで最短経路を見つけることができます)。

  1. BFS: 通常、キューによって実装されます (first in the first out データ構造) 宛先ノードに到達するまでレイヤーごとにすべての隣接頂点を使い果たし、そのノードで停止する場合、例: レイヤー 1 からすべてのノードに到達しない場合そのすべてのノードレイヤーをキューに見つけ、レイヤー2などについて続けます。ターゲットノードがこれまでに見つかった最短レイヤーであることを保証します（ターゲットノードが見つかった後に停止するため、グラフ内のすべてのノードをトラバースしません（速度の点でDFSよりも高速です））

  2. DFS: 通常、スタック (先入れ後出しのデータ構造) によって実装されます。DSF は、それ以上探索できなくなるまで、特定のポイントからすべてのノードを使い果たします。しかし、ターゲットノードが見つかった場合、パスが最短パスであるという保証はないため、パスが最短であることを確認するためにグラフ内のすべてのノードをトラバースする必要があります。ところで

@alandongの答えは間違っています

于 2021-03-19T10:18:29.547 に答える