差分
このページの2つのバージョン間の差分を表示します。
| 次のリビジョン | 前のリビジョン | ||
| 全面探索 [2015/03/09 18:46] – 作成 member | 全面探索 [2015/03/09 21:24] (現在) – member | ||
|---|---|---|---|
| 行 1: | 行 1: | ||
| + | =========全面探索========= | ||
| + | |||
| まずは全面探索についてのアプローチを書いていきます。 | まずは全面探索についてのアプローチを書いていきます。 | ||
| 行 4: | 行 6: | ||
| よく行われる手法としては、 | よく行われる手法としては、 | ||
| - | ・全ての区画をゴール座標にして、足立法などの到達可能なアルゴリズムにより目的地の情報を収集する。これを全部の区画で実行する。 | + | * 全ての区画をゴール座標にして、足立法などの到達可能なアルゴリズムにより目的地の情報を収集する。これを全部の区画で実行する。 |
| キーワードは「ゴール座標にする」という言葉です。 | キーワードは「ゴール座標にする」という言葉です。 | ||
| 勘違いされる人もいるため、確認として明示します。 | 勘違いされる人もいるため、確認として明示します。 | ||
| + | =========アプローチ========= | ||
| + | 『全ての区画をゴール座標にする』ということは、まだ行っていない未探索な区画を見つければ良いということです。 | ||
| + | |||
| + | 極論を言えば、全区画をスキャンして、到達していない区画を見つけて、目的地に設定して足立法などの到達可能なアルゴリズムを実行するだけでも可能です。 | ||
| + | |||
| + | =========効率をよくするためには========= | ||
| + | 目的地にする区画を的確に見つけることが、効率の良い全面探索への近道と言えます。 | ||
| + | |||
| + | * 現在位置から一番近い未探索の区画をゴール座標にする | ||
| + | というような条件を追加していくと、より効率よく全面探索ができます。 | ||
