WRM007 Aquila アルゴリズム解説

目次

※ここからは、頂点の数はV,辺の数はEとする.(頂点=Vertex,辺=edge)
また大会の終了後にソースコードを公開する予定にしている.

マッピング

30cm*30cmのマスを1つの頂点として重み無し無向グラフ(unweighted graph)を構築し、
それを地図としている.(※グラフの構築方式は構造体を連結する連結リスト方式.)
しかし、ナイーブなグラフの実装では頂点の存在判定の時間計算量はO(E)となってしまうので、
別にAVLtree(平衡2分探索木)を構築し、計算量をO(log V)程度まで改善した.
これらの2つの構造と現在のロボットの向き、その他内部での探索に必要なパラメータを
1つのクラスに集約して管理することで、単純さを保っている.
また、
地図となるグラフ上での最短距離をBFSを用いて算出し、後述の頂点間移動を最適な物にしている.
具体的に言うと、単一始点最短経路問題(Single Source Shortest Path problem)を解いている.
(※BFSは、グラフの任意の辺の重みが等しいと見なせることから、ダイクストラ法を適用しているのと同じと見なせる.
(∵全ての重みが同じ集合の要素をpriority queueから取り出すのは、
queueからその集合の要素を取り出すのと同じ.)　
実は、ダイクストラ法は最良優先探索(Best-First-Search)と呼ばれる、BFSを拡張した問題のクラスに所属している. )

・AVLtree(Adelson-Velskii and Landis'tree)とは
任意のノードについて、
そのノードの左右の部分木の高さの差が1以下という条件を満たす2分探索木の事である.
探索に費やす時間計算量はO(log |V|)である.
多くの場合、1.挿入　2.削除　3.探索　の3つのクエリに答えるように実装するが、
このロボットのプログラム中では削除クエリは実装していない.
また挿入クエリにおいて、挿入されたノードについて、
左右の部分木の高さの差が1よりも大きくなると木を回転させることで
上記の条件を満たすようにしている.
詳しい説明はこのロボットの本質ではないので省略する.(木の回転が非常に可愛いので必見である!)
またAVLtreeを選択したのは,
挿入クエリよりも探索クエリの方がはるかに高頻度であり、挿入された順だと,ソート済みの列を挿入するのに近い動作をすることになり、
B木では平衡構造が崩れやすく、逐次的に探索する事が予想されることから、
SplayTreeも適切ではないと考えられたからである. (∵ノード移動時に毎回探索している)

(改良)深さ優先探索(DFS)

深さ優先探索(Depth-First-Search)とは
　訪問したい頂点をstack(Last In First Out)に積み、それを順に訪れる探索手法である.
　一般にグラフをDFSする事で、そのグラフの持つ性質を明らかにできる事がある.
(ex.有向グラフ中での強連結成分分解,木判定 等)
また、時間計算量はO(E)である.
実装は再帰を用いるのが最も簡単であろう.(∵マイコン上での再帰は関数の処理"stack"に搭載される)

※幅優先探索(Breadth-First-Search)とは
　DFSと違って、こちらは訪問したい頂点をqueue(First In Fast Out)に積むという点が違う.
　こちらも時間計算量はO(E)である.
　だが、DFSと最も大きな違いとなるのはBFSは解の発見時の、
(探索の起点となる頂点からの)解の深さが最短になるということである.
　このロボットではこの性質を用いて,頂点間の移動を最適化している.

訪問したい頂点を単一のstackに管理し、順に訪問している.
ほとんどナイーブなDFSであるが、stack内の頂点の順を工夫(☆)している.
左手法よりもmappingの実現という点を除けば単純であり、全探索が保証されるので、
DFSを選択した.

☆stack内の頂点の最適化について------------------------------------------------
最短ハミルトン路問題と呼ばれる問題を解いている.
これは、頂点集合に含まれる全ての頂点を通るような最短の道を求める組み合わせ最適化の問題である.
実際の実装では、始点を現在地に、終点をスタート地点におき、
動的計画法(Dynamic Programming)により、
・dp[S+{u}][u] = min(dp[S][t] + dist[t][u]) ....(※)
　　という漸化式を解くことで実現している.(細かく詰めると,bitDPの配るDPである)
※dp[S][t]は頂点集合Sに含まれる頂点をすべて通り、かつ頂点tで終わるような最短の道の長さを表す.

動的計画法が使用できるのは、
・部分構造最適性(部分問題も同じ最適化問題であり,その問題同士が独立している事.
これによって解を結合していく事で解が作られる.)
・部分問題重複性(同じ部分問題が何度も出現する事.解を保存しておくことで計算を高速化する(メモ化という).)
の2つをこの問題が満たすからである。

また、頂点集合は元のstack内の配列をコピーし、"添え字集合"のようにして、2進数で表現している.
(ex. 0100:={2} , 0001:={0})

細かい工夫と苦労した事

①細かい工夫
アルゴリズム関連の実装部分については、移動に関連する手続きは、
全て頂点間の移動によって表現した.
そうすることで抽象性が上がり、より一般的で強力な概念の導入が容易になるからである.
(勿論抽象性が高い方がバグも少なく、多くの人間にとって分かり易いという利点もある.)
その実装をC++風のコードにより以下に示す.

struct node{
int x,y,z;
node* next[4];//その頂点の4近傍を配列に管理.
int dist;//bfsにより算出された頂点間距離は全て頂点中に保存し、管理.
int flag;//現在の探索において、訪問済みか否か.
/*実際のコードは一連の大会の終了後に公開する事を計画している.実際のコードを単純化している.*/
}

move_four_n(node* s){//s∈{現在地のnodeの4近傍}
/*現在地のnodeの4近傍への移動を表現.*/
/*全ての方向について逐次判定し、移動するとループから抜ける.*/
/*現在地のnodeのアドレスもここで変更される.*/
}

move_vertex(node* t,node* s){/*頂点tから頂点sへの移動*/
bfs(s,t);/*sをrootとして、tを幅優先探索する.*/
node* now = /*現在地のノード*/;
while(now != s){
for(int i=0;i<4;i++){
if(now->next[i]->dist < now->dist){
move_four_n(now->next[i]);
break;
}//これは、現在のnodeより1node分近い頂点が存在すれば、それが最短に確定するからである.(背理法で示される.・・・☆)
}
}
}
///////////////////////////

(☆の証明)
bfsの探索の起点となるnodeをsとし、現在のnodeをnowと表現する.(now≠s,s:=const.)
また、頂点s、頂点u間の距離をsからuへの最短経路に含まれる辺の数とし、
これをdist(u)と表す事にする.(dist(u)∈ℤ)

dist(u) < dist(now) - 1 となるuの存在を仮定し、それをrと置く.(ただし,頂点rは頂点nowの4近傍に含まれる)
この時、rはnowの4近傍に含まれるから、rはnowに隣接する.

つまり、dist(now) = min(dist(r)+1) (r∈nowの4近傍)をふまえて、
dist(r)が最小となるr=r1(r∈nowの4近傍)と置くと、
dist(r1) + 1 = dist(now) であるから、
dist(r1) <= dist(r) (r∈nowの4近傍)と合わせて、
dist(now) <= dist(r) + 1 (r∈nowの4近傍)を満たす.
これは仮定に反する.

ゆえに、示された. //

②苦労した事
・C++のnew,deleteが使えなかったので、
配列を用意してそこから取り出していかなくてはならなかった事.
・(PC上で動かすプログラムと違って)非常に副作用が多い事.
・AVLtreeの実装.
・アルゴリズムの動作確認.
・バグの発生時にメモリを読まなくてはならない事.

アルゴリズムに触れる方法

このパネルを読む人の多くは相当にアルゴリズムの知識を持っていると思われるが、
弊校の後輩や、来年度以降にこの競技に参加したいと考える方のために記しておく.
(1)本(又は記事)を読む.(場合によっては証明をなぞる)
(2)具体例を出して、その手法の動作を自分の手で確かめる.(イメージを掴む)
(3)実装する.
の順にやると理解しやすい傾向にあると私は考える.(人によって良い方法は変わると思う)
「アルゴリズムクイックリファレンス」、「アルゴリズムイントロダクション(1巻,2巻)」等の書籍が分かりやすいかもしれない.

〇実現できなかったアイデアについて.)

・経路修正
紙面上の実験では、周囲3*3ブロック分の地形が一致すれば,
uniqueに頂点が定まる気がするが,状況によるので何とも言えない.
・A*のようなゲーム木の探索
迷路の探索状況をゲームの盤面とみなして、盤面評価関数を作成する.
そして、ゲーム木を探索する.これがうまくいけば、非常に効率の良い結果が得られるであろうが、
1.盤面のサイズ
2.評価関数の調整
が非常に難しいし、平均的にみて性能が良い手法と断言する事は非常に難しい.
・被災者が存在するブロック,又は,開始地点のブロックのみを頂点とし、
他は全て辺とする重み付きグラフを構築する.
これは組み込みの側との兼ね合いが非常に難しい上に、実装にも困難が伴うが、
思考的な面では、より簡潔に考える事ができると思われる.

ここまで読んでくださってありがとうございました.
そして、関係者、運営の皆様、今までと今のチームメイトの友人達、6年間ありがとうございました.