Now Loading...

Now Loading...

幅優先探索

幅優先探索

コンピュータで迷路の問題を解く時、探索木の始点から場合分けを続けて終点にたどり着く経路が見つかれば、それが迷路の回答になります。このとき、探索にかかる時間は検索する方法によって変わり、主に2つの手法があります。
幅優先探索は、出発点に近いノード(探索木の各要素)から順に検索します。よって、最短距離でゴールにたどり着く解を必ず見つけることができます。しかし、探索の途中で立ち寄ったノードをすべて記憶しておかなければならないため、複雑な迷路になるとメモリ不足により処理を続行できなくなる可能性があります。

クイズ

迷路を場合分けの問題としてコンピュータに与えて解くときに適切なアルゴリズムがある.これは木のような構造をしており,条件の場合分けに対応して枝が分岐し,枝を辿ることで目的の条件に合致するものが見つかるという発想に基づいている.枝を探索する方法の一つに,ゴールへの最短経路を確実に見つけることができる代わりにメモリを大量に使うものがある.この方法の名前として最も適切な選択肢を1つ選べ.
  • 正解を見る
  • 解説を見る
    幅優先探索とは探索の途中のノードを全て記憶しておく必要がある為,大量のメモリが必要となります.一方深さ優先探索では一旦行き止まりのノードまで行き解が見つからない場合は分岐までもどる,という方法をとる為,メモリはそれほど必要としません. (参考: G検定公式テキスト 第2版 第2章 2-1 P38-39) (参考: G検定公式テキスト 第1版 P18-22 探索・推論)

幅優先探索を体験できる記事を紹介!

下記のリンク先にてPythonのコードを用いて実際に幅優先探索のアルゴリズムを実行できる記事を公開中。ぜひご覧ください。

人工知能基礎講座を提供中

人工知能の第一人者である東京大学の松尾豊教授が監修した人工知能基礎講座を受講してみませんか? 人工知能の歴史から自然言語処理、機械学習、深層学習といった最先端のトピックやAIに関わる法律問題まで網羅しているので全てのビジネスパーソン・AIの初学者におすすめです。

サンプル動画

人工知能基礎講座はこちら↓ zero to one G検定 人工知能基礎 jdla

AIエンジニアを目指すならE資格

日本ディープラーニング協会の実施するE資格の受験に必要となるE資格認定プログラムを割引価格で提供中です。最短合格を目指す方向けのスピードパッケージを70,000円で提供中。(一発合格で33,000円のキャッシュバックキャンペーンも実施中です) zero to one E資格 jdla

AI初学者・ビジネスパーソン向けのG検定対策講座

G検定受験前にトレーニングしたい方向けの問題集「G検定実践トレーニング」も提供中です。 zero to one E資格 jdla