全面探索 [Mice Wiki]

現在位置: IndexPage » 全面探索

技術資料

このWikiについて

この文書は読取専用です。文書のソースを閲覧することは可能ですが、変更はできません。もし変更したい場合は管理者に連絡してください。

=========全面探索=========

まずは全面探索についてのアプローチを書いていきます。

全面探索とは名前の通り、全ての区画に対し探索を行うことを意味ます。

よく行われる手法としては、
  * 全ての区画をゴール座標にして、足立法などの到達可能なアルゴリズムにより目的地の情報を収集する。これを全部の区画で実行する。

キーワードは「ゴール座標にする」という言葉です。
勘違いされる人もいるため、確認として明示します。

=========アプローチ=========
『全ての区画をゴール座標にする』ということは、まだ行っていない未探索な区画を見つければ良いということです。

極論を言えば、全区画をスキャンして、到達していない区画を見つけて、目的地に設定して足立法などの到達可能なアルゴリズムを実行するだけでも可能です。

=========効率をよくするためには=========
目的地にする区画を的確に見つけることが、効率の良い全面探索への近道と言えます。

  * 現在位置から一番近い未探索の区画をゴール座標にする

というような条件を追加していくと、より効率よく全面探索ができます。

/home/users/2/deca.jp-mice/web/cgi/dokuwiki/data/pages/全面探索.txt · 最終更新: 2015/03/09 21:24 by member

文書の表示以前のリビジョン

[unknown link type]文書の先頭へ

Menu

このWikiについて