DATE: --/--/--(--)   CATEGORY: スポンサー広告
スポンサーサイト
上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。
page top
DATE: 2015/12/11(金)   CATEGORY: 未分類
うむ夫。探索編(2) ~アルゴリズム編Part2~
探索シミュレーターがある程度形になったため前回の記事の補足を行いたいと思います.
前回の記事では,文字だけで説明したので伝わりにくかったと思います.

例として,全日本大会2015エキスパート予選の迷路を参考に補足していきたいと思います.
うむ夫。に実装している最短経路導出アルゴリズムだとこの経路を走りたいです.
全日本大会2015エキスパート予選最短

上位陣の方々を見ていると南回りの方が速そうですね.
そこのところは次回作への課題です.

足立法


ゴールまでの探索時間が短いです.
帰りの探索をうまくやらないと未知区間が多く,いい経路がでない場合があるので注意が必要です.
とりあえずゴールしたいときには有効ですね.

未知区間優先アルゴリズム


例のF川法です.
足立法と比べ迷路の概形がかなりつかめていることがわかると思います.
全面探索を実装していないうむ夫。には大変ありがたいですね.

最短経路導出特化型アルゴリズム


ピンクの丸が仮のゴールです.
走りたい最短経路が見つけられていることがわかると思います.
また,前回の記事で述べた概形がわかっていないと非常に効率が悪いと言ったことも伝わったと思います笑.
最短経路導出の方法を変えれば下の経路もだせると考えています.
最短経路の導出の仕方を考えていくうちに改良したいです.

補足としては以上です.実際にうむ夫。では往路は未知区間優先アルゴリズムでの探索,復路では最短経路導出特化型アルゴリズムでの探索を行っています.
今回はここまでです.





スポンサーサイト

コメントの投稿

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