幅優先探索

幅優先探索 †

このページは競技プログラミングに興味のある方向けに幅優先探索を簡単に説明するページです

幅優先探索って何？ †

木構造のデータを探索する手法なのですが、大雑把にいえば

1.とりあえず根の子ノードをすべて列挙する
2.列挙されたノードの子ノードをすべて列挙する
3.2において子ノードを持たないノードがあればそのノードの状態や経路が条件を満たしているかをチェックする
4.2に戻る

という形になります

ざっくりいえば、
1手目の候補を全列挙→2手目の候補を全列挙→3手目の候補を全列挙・・・
として行き、途中で「これ以上進行しない手」があった場合、その状態やそこまでの経路が条件を満たすかをチェックする
という手法です

具体的にどんな手法 †

一般に、ゲームの終了状態や組み合わせ問題は各々木構造における末端部分や末端部分への経路に対応付けることが出来ます。
つまり、ゲームの終了状態や組み合わせ問題において条件を満たす手順や組み合わせがあるかどうかを木構造における末端部分あるいはそこへ至る経路を探索することで確認することが出来ます
このとき以下の手法をとる探索手法が幅優先探索です

1.変数lenを一つ用意します。初期置は0とします
2.根からの距離がlenであるノードをすべて列挙します(つまり、根からスタートする)
3.2で列挙したノードの内、子を持たないノードについて、その状態あるいは遷移経路について条件を満たすかどうかを判定します
　 条件を満たしていれば探索を打ち切ります。 4.lenを1増やします

根からの距離をいちいち計算するのがめんどくさい †

キューを使えば簡単にできますよ

キューとはなんぞや？ †

知らなくても、幅優先探索を理解することは何とか可能です
(けど、知識レベル的には幅優先探索の方が上なので、できればスタックを勉強してくださいね)

キューを勉強しました †

それなら、以下の手法で容易に実装できます

1.根ノードをPUSHする
2.POPする
3.POPしたノードの子ノードをもつならそれらを全てPUSHする。
4.POPしたノードが子ノードを持たないならそのノードへ至る経路あるいはそのノードの状態が条件を満たすかどうかを判定します
　 条件を満たしていれば探索を打ち切ります。
5.2に戻る

キューが爆発しました †

深さが最大でN,各ノードにK個の子ノードがあると仮定しましょう
すると、幅優先探索においてキューに入るノードの数は最大で K^N 程度となってしまいます。
K=10,N=20でもうお手上げです
一方、深さ優先探索ではスタックに入るノードの数は最大で K×N 程度です。(もう少し上手にすれば K+N 程度)
K=100,N=100でも余裕です

幅優先探索が深さ優先探索に勝っているところはないの？ †

大きく上げると2つあります

1つ目
末端ノードと根との距離が一定でない木において解が比較的根に近い位置にある場合、幅優先探索であれば早い段階で解に到達できるが
深さ優先探索だと根からの距離が遠いノードから探索していた場合、解の発見に時間がかかります
例えば根ノードをAとし、Aは子ノードとしてB, Cを持つとします
またBはさらにその下に非常に大きな部分木を持つものとします
もしこの時解が(A-C)という経路である場合に幅優先探索では極めて迅速に解が発見されますが、
深さ優先探索では(A-B-・・・)の経路から探索した場合において非常に多くの時間がかかります
根からの距離が短い部分から探索するという手法にした場合は単純な構造の木であれば深さ優先探索でも早期に解(A-C)を発見できますが
木の構造が複雑になるとこの手法は使えなくなります
具体的には根ノードAが子ノードB, Cを持ち、B, Cは子ノードとして各々(B1,B2),(C1,C2)を持つとします
B1, C1は各々その下非常に大きな部分木を持ちB2, C2は子ノードを持たないとします
この時解が(A-C-C2)である場合はもはや「根からの距離が短い部分木を優先して深さ優先探索を行う」という手法では不可能になります。

2つ目
幅優先探索においては枝刈りが非常に効率的に働く場合があります
その典型例として「マス目状の平面(あるいは立体、多次元空間)に位置された2点間の最短経路」を求めるというものがあります
詳細は割愛しますが、このようなパターンの場合において幅優先探索は非常に効果的です