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