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

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

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

状態(state)と行動(action)

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

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

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

探索木

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

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

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

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

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

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

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

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

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

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

などが挙げられます。

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

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

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

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

などが挙げられます。

反復深化法|Iterative deepening(ID)

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

関連記事

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

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

記事を読む

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

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

記事を読む

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

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

記事を読む

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

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

記事を読む

【機械学習】 scikit-learn で不正解データを抽出する方法【Python】

Python の scikit-learn ライブラリを使って機械学習でテストデータを識別(2クラス

記事を読む

【Weka】アソシエーション・ルール(association rule)【機械学習】

フリーの機械学習ツール Weka でアソシエーション・ルール(association rule)を使

記事を読む

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

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

記事を読む

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

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

記事を読む

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

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

記事を読む

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

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

記事を読む

Message

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

初心者でも分かるビットコインの仕組みについてまとめてみた。

ビットコインは,時価総額が1位で最も有名な仮想通貨です. 仮

【LaTeX】 見出し付き箇条書きを右にずらす方法【数式の変数説明】

今回は、LaTeX で見出し付き箇条書きの全体の位置を右にずらす方法に

【LaTeX】 余白部分を設定しレイアウトを確認する方法。

今回は、LaTeX の余白部分のレイアウトの変更方法とレイアウトの確認

【LaTeX】 レポートや論文の表紙のテンプレート。

LaTex を使ってレポートや論文を書くときに、表紙をつけると思います

【DTM】 Cubase AI でギターやベースを録音する方法。

今回は、DTM のための DAWソフト Cubase AI でギター(

→もっと見る

PAGE TOP ↑