【探索】縦型・横型・反復深化法の探索手法の比較。

公開日: : 最終更新日:2018/05/16 機械学習 , , , ,

探索とは、チェスや将棋や囲碁などのゲームをコンピュータがプレイするときに、どの手を指すかを決定するのに使われます。人間の「読み」にあたる部分です。

状態(state)と行動(action)

ゲームの盤面など意志決定に必要な情報を状態(state)、可能な全ての状態を状態空間と呼びます。また、状態を変化させる選択肢を行動(action、ゲームでは手、moveとも)と呼びます。

  • 盤だけが状態ではなく、自分がどっちなのか、先手後手どっちの番なのか、持ち駒なども状態に含まれる。
  • 名前、手数、持ち時間などは普通は状態に含めない。

状態空間は、状態を節点(node)、変換操作を枝(edge)とすると、グラフ(節点と枝の集まり)で表現できます。

探索木

探索空間を木状のグラフで表現したものを「探索木」といいます。節点が状態、枝が行動を表します。

探索木による探索とは、「与えられた問題において想定される多くの可能な状態の中から、特定の条件を満たすものに至る経路を見つけ出すための方法」とされます。

探索はおおむね以下の手順の繰り返しで行われます。

  • 分かっている情報を候補リストに保管する。
  • 候補リストから次に調べる状態・着手を選択する。
  • 新しいノードを展開し、リストを更新する。

基本的には、全てを調べ上げればゴールは見つかるため、重複や見落としなしに、しらみつぶしに探索します。

どのような順序で探索するかによって、いくつか探索手法があります。

縦型(深さ優先)探索|Depth-first search(DFS)

縦型探索は、子節点をどんどん深く(枝の先に)探索していく方法です。

縦型探索の特徴としては、

  • 深いゴールが早く見つけられる場合がある(長所)。
  • 浅いゴールがなかなか見つけられない(短所)。
  • 記憶領域(メモリ使用量)が少ない(むやみに手を広げないため)。
  • 得られた解が最善である保証がない。

などが挙げられます。

横型(幅優先)探索|Breadth-first search(BFS)

横型探索は、同じ深さの節点を全て調べ、ゴールが見つかるまで1つずつ深くしていく手法です。

横型探索の特徴としては、

  • 最短の方法でゴールを見つけることができる(最適解がみつかる)。
  • 記憶容量が大量に必要になる(致命的な欠点)。

などが挙げられます。

反復深化法|Iterative deepening(ID)

反復深化法は、縦型探索で閾値(最大探索深さ)を徐徐に上げ、繰り返し探索を行う方法で、縦型探索と横型探索の長所を兼ね備えています。

関連記事

【Weka】フリーの機械学習ソフトをインストールする方法。

Weka は、GUIで使えるフリーの機械学習ソフトです。 https://ja.wikiped

記事を読む

【深層学習】 TensorFlow と Keras をインストールする【Python】

今回は、Google Colaboratory 上で、深層学習(DeepLearning)フレームワ

記事を読む

【Weka】CSVファイルを読み込んで決定木を実行。

フリーの機械学習ソフト Weka を使って、CSVファイルを読み込んで決定木(Decision Tr

記事を読む

【機械学習】パーセプトロン(Perceptron)について。

パーセプトロンは、教師あり学習の中でも、入出力モデルベース(eager learning:働き者の学

記事を読む

【機械学習・手法比較】決定木とナイーブベイズを比較してみた。

同じデータを使って、教師有り機械学習手法の 決定木(Decision Tree)とナイーブベイズ(N

記事を読む

【機械学習】モンテカルロ法(Monte Carlo method)について。

モンテカルロ法(Monte Carlo method)とは、シュミレーションや数値計算を乱数を用いて

記事を読む

【Weka】欠損データを自動的に補完するフィルタを使ってみた。

機械学習で用いるデータについてです。データは完璧なことに越したことはないが、通常は、ある属性の値が入

記事を読む

【探索】ダイクストラ法・最良優先探索・Aアルゴリズムの比較。

縦型探索や横型探索では、機械的に順序を付け、最小ステップでゴールを目指します。 つまり、

記事を読む

【Weka】ARFF 形式から CSV 形式に簡単に変換する方法。

フリーのデータマイニングツールである WEKA では、ARFF 形式と CSV 形式のデータを読み込

記事を読む

【画像認識】 Google画像検索結果を取得する方法 【google image download】

今回は、深層学習(DeepLearning)で画像認識をするための画像データの収集を、Google画

記事を読む

Message

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です

【matplotlib】 Python でヒストグラムの横軸と棒(ビン)の数を調整する方法。

Python の matplotlib を使ってヒストグラムを描画し、

【デジカメ】 NEX-6 で撮った写真を Wi-Fi で PC に転送する方法【SONY】

今回は、SONY の NEX-6 のデジカメで撮った写真を 無線の W

【SONY NEX-6】オールドレンズをミラーレスカメラに付ける方法【マウントアダプター】

家でずっと眠っていたオールドレンズ(フィルムカメラに装着されて

【WordPress】 カテゴリごとに広告を簡単に切り替える方法【AdRotate】

今回は、WordPress のプラグインを使って、簡単にカテゴリごとに

【ビットコイン】 アドレス生成方法について調べてみた。

仮想通貨の1つであるビットコインを送金するときは、送付側と受け手側のそ

→もっと見る

PAGE TOP ↑