問題 No.5022
グラフや木の探索アルゴリズムの一つである深さ優先探索（DFS）に関する記述として不適切なものはどれか。
【正解の解説】
探索の過程で未訪問の隣接ノードが複数ある場合、常に最短経路を確実に見つけるためにすべての分岐先を同時に並行して展開しながら探索を進める。
迷路で例えると、一本の道を行き止まりになるか宝物を見つけるまでひたすら奥へ進み続けるのが深さ優先探索です。すべての道を同時に並行して進むわけではないため、最初に見つかったゴールが必ずしも最短経路とは限らないという特徴があります。最短経路を探したい場合は、別のアルゴリズムである幅優先探索を利用する必要があります。
スポンサーリンク
【その他の選択肢の解説】
探索の過程で未訪問の隣接ノードが複数ある場合、最後に追加されたノードを優先して訪問するLIFOの原則に基づいてスタック構造を利用して実装される。
積み上がった書類の山の一番上から順に処理していくイメージです。分岐に来たときに直前に入れた未訪問ノードを優先して掘り進めるため、コンピュータ内部では自動的にスタックというデータ構造が使われます。この仕組みによって、行き止まりになった際に一つ前の分岐までスムーズに戻ることができるようになっています。
探索の過程で未訪問の隣接ノードが複数ある場合、最初に追加されたノードを優先して訪問するFIFOの原則に基づいてキュー構造を利用して実装される。
窓口の順番待ちの列に並んだ人が先に対応されるFIFOの仕組みです。これを探索に使うと、現在地から近い場所を順番に広く浅く探していく幅優先探索になります。深さ優先探索のスタック構造とはデータの出し入れの順序が真逆になるため、初学者は混同しやすいポイントとしてよく試験に出題されます。
探索の過程で未訪問の隣接ノードが複数ある場合、各ノードに設定されたヒューリスティック関数の評価値が最も低いものを優先して選択する。
ゴールまでの近さを予測する評価値を使って次に進む場所を決めるのは、A*アルゴリズムなどの別の高度な探索手法です。深さ優先探索はゴールの方角を計算するような頭の良さは持っておらず、目の前にある分岐をルール通りにひたすら突き進むだけのシンプルなアルゴリズムなので、この記述は完全に誤りとなります。