Filed under:
Aquila タグ:
Aquila,
RCJ,
プレゼンシート,
京滋奈ブロック
プレゼンシートでは載せきれなかったアルゴリズムについて少しだけ説明したいと思います。
（おそらくわかりずらいので、どしどしお聞きください。
以下相方(アルゴリズム担当)のそのままです。
実機での探索アルゴリズムにはDFSにほんのりと評価関数を加えたアルゴリズムを使用しています。
また、DFSにおける頂点間の移動時に、単一始点最短経路問題(SSSP)を解いているのですが、
後述の通り重み無しのグラフなのでダイクストラ法ではなくあえて幅優先探索(O(E))を用いる事で高速化しています。
マッピングについては、30*30のマス一つを頂点とした重み無し無向グラフを構造体をつなげることで表現しています。
また、頂点の重複がないか確認する為に既存の頂点をすべて保存していて、
保存の為にAVL-tree(検索、挿入、削除共にO(log V))を用いる事で検索、構築を高速化しています。
以下補足。
※ダイクストラ法について
幅優先探索の特殊版のようなものです。(最良優先探索の一つ)
辺の重み(>0)に関する優先度付きキューを用いて辺集合を成長させる事で最短路を求める方法です。
(優先度付きキューの種類によって計算量は変化します。)
※AVL-treeについて
|左の部分木の高さー右の部分木の高さ|<=1を満たす木の事です。
これによって木の高さを平衡に近く保つ事で探索性能をO(log(V))に抑える事が出来ます。
(挿入、削除時に木を回転させています)
※DFS(深さ優先探索)とは一旦進めるまで進み、行き止まりに到着すると一つ前の分岐点にもどり、未探索の方へ進むという方法です。
らしいです。
自分でもわかりません(;’∀’)
こちらの資料(相方作)をご覧になると少しだけわかるかもしれないです・・・
ちゃんと動いてくれよ俺たちのロボット・・・
以上正月にプレゼンの原稿作ってるAquilaでした。
