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

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

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

状態(state)と行動(action)

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

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

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

探索木

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

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

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

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

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

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

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

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

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

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

などが挙げられます。

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

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

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

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

などが挙げられます。

反復深化法|Iterative deepening(ID)

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

関連記事

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

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

記事を読む

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

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

記事を読む

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

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

記事を読む

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

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

記事を読む

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

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

記事を読む

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

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

記事を読む

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

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

記事を読む

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

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

記事を読む

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

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

記事を読む

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

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

記事を読む

Message

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

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

TensorFlow で GPU を認識させようとしたときにハマってし

【耳コピ】音楽ファイルを楽器ごとに分離する方法【Spleeter:フリー】

今回は、mp3 などの音楽ファイルをボーカル、ベース、ドラムなどの楽器

【Chainer】手書き数字認識をしてみた【Deep Learning】

Chainerを用いて、ニューラルネットワークを構築し、手書き数字認識

【Spyder】引数のあるスクリプトを実行する方法。

Python の統合開発環境(IDE)である Spyder では、簡単

【Anaconda】Prompt 上で Git コマンドを実行する方法。

Anaconda のコマンドプロンプト(Anaconda Prompt

→もっと見る

PAGE TOP ↑