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

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

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

Contents

状態(state)と行動(action)

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

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

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

探索木

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

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

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

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

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

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

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

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

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

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

などが挙げられます。

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

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

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

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

などが挙げられます。

反復深化法|Iterative deepening(ID)

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

関連記事

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

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

記事を読む

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

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

記事を読む

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

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

記事を読む

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

今回は、PyTorch を使って、学習済みのモデル VGG16 を用いて転移学習をしてみました。

記事を読む

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

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

記事を読む

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

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

記事を読む

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

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

記事を読む

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

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

記事を読む

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

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

記事を読む

【機械学習】 scikit-learn で精度・再現率・F値を算出する方法【Python】

今回は、2クラス分類で Python の scikit-learn を使った評価指標である、精度(P

記事を読む

Message

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

無料動画編集ソフト AviUtl で mp4 形式の動画を読み込み・出力する方法【Windows】

今回は、無料動画編集ソフト AviUtl で mp4 形式の動画を読み

【Cubase】イヤホンから音がでないときの対処方法。

Cubase でイヤホンから音がでなくなったときの対処方法のメモです。

【Cubase】特定のトラックを無効にする方法。

今回は、Cubaseで特定のトラックのみを無効にする方法について紹介し

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

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

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

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

→もっと見る

PAGE TOP ↑