DATE: --/--/--(--)   CATEGORY: スポンサー広告
スポンサーサイト
上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。
page top
DATE: 2015/11/24(火)   CATEGORY: 未分類
うむ夫。探索編(1) ~アルゴリズム編~


今回はうむ夫。に実装している探索アルゴリズムについて紹介したいと思います.

足立法
…一般的に知られている探索アルゴリズムです.特に工夫もありません.足立法についての説明は省略します.

未知区間優先アルゴリズム
…部内ではF川法として有名です.部内の先輩に薦められ導入したアルゴリズムです.このアルゴリズムの利点としては,名前の通り未知区間を優先して探索を行うため迷路の概形が掴みやすいです.また,足立法に比べ迷路の多くを探索するためより良い経路を見つけやすいです.今シーズンはとてもお世話になりました.来シーズンも大変お世話になる予定です.現在は2マス以上の袋小路だとわかった場合,未知区間でも探索しないように工夫をして運用しています.この方法も後々紹介したいと思います.今後の改良案としては,2マス以上の袋小路だけでなく一周して戻ってくるような形状も探索しないようにしていきたいです.賢い探索は見ていて気持ちがいいです.

最短経路導出特化型アルゴリズム
…単純に言うと,探索が成功すれば最短経路が確実に見つけられるアルゴリズムです.学生大会のときにアルゴリズムの不手際や壁の読み間違いにより最短経路の導出ができなかったことを反省し考案しました.主に帰りの探索の時に用いています.全日本大会のときもこのアルゴリズムで帰りの探索で用いました.概要としては以下の通りです.

① 現在の迷路情報を参照し,推定最短経路を導出.
② 最短経路導出中に未知区間が現れた場合,その未知区間を仮のゴールとして探索を行う.
③ 仮のゴールに向かう時に,未知区間を探索する場合,①~②を繰り返す.
⓸ ①~③を繰り返し,未知区間が存在しなくなった場合その経路が最短経路である.

この方法の長所は,推定最短経路の求め方にあった経路が必ず求まることです.通常の足立法を用いている人なら経験したことがあると思いますが,足立法による探索ではきちんとした経路が求まらないことが多々あります.この方法ではそれがありません.

一方,短所としては迷路の概形がわっかっていなと探索の時間がかかることです.自分が帰りの探索でしか用いない理由はここにあります.迷路の概形がわからない場合,例えば北に向かおうとするとします.その後北の壁がわかってきた場合,南の壁が無い状態なので,南からの経路を目指そうとします.あとはこのループです.迷路の情報がわかっていない場合,一方向を見て,他方向を見に行くような探索を行ってしまうのです.ですのでこのアルゴリズムは,迷路の概形がわかった上で,残りの可能性のある未知区間をつぶしていくように行うことがいいと考えています.


うむ夫。には以上の探索アルゴリズムが実装されています.今シーズンは迷路探索について力を入れて開発してきました.
次回は,探索中に行っている小技や補正を紹介します.



スポンサーサイト

コメントの投稿

 管理者にだけ表示を許可する
Copyright © うむ夫の歩み. all rights reserved.
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。