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

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

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

状態(state)と行動(action)

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

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

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

探索木

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

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

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

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

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

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

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

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

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

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

などが挙げられます。

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

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

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

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

などが挙げられます。

反復深化法|Iterative deepening(ID)

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

関連記事

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

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

記事を読む

【TensorFlow】GPUを認識しない時の対処方法【Python】

TensorFlow で GPU を認識させようとしたときにハマってしまったので、その対処方法のメモ

記事を読む

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

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

記事を読む

機械学習の手法のまとめ。

機械学習は、「与えられた入出力事例をモデル化する行為」のことで、ディープラーニングなどで注目を集めて

記事を読む

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

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

記事を読む

【PyTorch】畳込みニューラルネットワークを構築する方法【CNN】

今回は、PyTorch を使って畳込みニューラルネットワーク(CNN)を構築する方法について紹介しま

記事を読む

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

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

記事を読む

【Fashion-MNIST】ファッションアイテムのデータセットを使ってみた【TensorFlow】

今回は、機械学習用に公開されているデータセットの1つである「Fashion-MNIST」について紹介

記事を読む

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

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

記事を読む

【機械学習】決定木(decision tree)について。

教師あり学習の一つである決定木(desicion tree)について勉強したことを書いていきます。

記事を読む

Message

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

【転移学習】学習済みVGG16 による転移学習を行う方法【PyTorch】

今回は、PyTorch を使って、学習済みのモデル VGG16 を用い

【PyTorch】畳込みニューラルネットワークを構築する方法【CNN】

今回は、PyTorch を使って畳込みニューラルネットワーク(CNN)

【PyTorch】ニューラルネットワークを構築する方法【NN】

今回は、PyTorch を使って、ニューラルネットワーク(NN)を構築

【OpenCV】検出した顔画像部分を切り出す方法【Python】

OpenCV を使って、Python で画像の中から顔部分を切り出した

【Fashion-MNIST】ファッションアイテムのデータセットを使ってみた【TensorFlow】

今回は、機械学習用に公開されているデータセットの1つである「Fashi

→もっと見る

PAGE TOP ↑