|
===================================== 〔語彙分解〕的な部分一致の検索結果は以下の通りです。 ・ 幅 ： [はば] 【名詞】 1. width 2. breadth ・ 優 ： [ゆう] 1. (adj-na,n) actor 2. superiority 3. gentleness ・ 優先 ： [ゆうせん] 1. (n,vs) preference 2. priority ・ 先 ： [せん] 1. (n,adj-no) the future 2. priority 3. precedence 4. former 5. previous 6. old 7. late ・ 探索 ： [たんさく] 1. (n,vs) search 2. hunt 3. (item of) research 4. exploration 5. investigation ・ 索 ： [さく] 【名詞】 1. rope 2. cord
幅優先探索（はばゆうせんたんさく、）はグラフ理論(Graph theory)において木構造(tree structure)やグラフ(graph)の探索に用いられるアルゴリズム。アルゴリズムは根ノードで始まり隣接した全てのノードを探索する。それからこれらの最も近いノードのそれぞれに対して同様のことを繰り返して探索対象ノードをみつける。「横型探索」とも言われる。 幅優先探索は解を探すために、グラフの全てのノードを網羅的に展開・検査する。最良優先探索とは異なり、ノード探索にヒューリスティクスを使わずに、グラフ全体を目的のノードがみつかるまで、目的のノードに接近しているかどうかなどは考慮せず探索する。 == アルゴリズム == # 根ノードを空のキューに加える。 # ノードをキューの先頭から取り出し、以下の処理を行う。 # * ノードが探索対象であれば、探索をやめ結果を返す。 # * そうでない場合、ノードの子で未探索のものを全てキューに追加する。 # もしキューが空ならば、グラフ内の全てのノードに対して処理が行われたので、探索をやめ"not found"と結果を返す。 # 2に戻る。 ノードの展開により得られる子ノードはキューに追加される。訪問済みの管理は配列やセットなどでも行える。 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「幅優先探索」の詳細全文を読む スポンサード リンク
|