A(A*)アルゴリズムをC#で書く
どうも!今日の目的は”git からソースコードを持ってきて貼る”です笑 しかし、ただ貼るだけではつまらないので、最近触った A*アルゴリズムをかるーーく後世の自分のために解説してみようかなと思います!笑 本当にかるーくです!
今回探索する図
今回探索する図はこちら。S がスタートノードで、ここからゴールノードである G を目指していきます。
A*アルゴリズムのC#ソースコード
簡単な解説
A* アルゴリズムは OPENリスト と CLOSEDリストを作成し、OPENリストには探索中のノードを、 CLOSEDリストには探索し終わったノードを挿入します。探索するノードはOPENリストの先頭から選ばれ、1つのノードについて探索が終わると OPENリストは重みの軽い順にソートされます。基本的にはこれを繰り返し、OPENリストがなくなったら、終了となります。
ソースコードではまずに、存在するノードと、そのノードからゴールへの見積もりの値hを入力しています。次にノード間の辺の重みを保存しています。それが終わったら、問題を作成し(button1_Click)、それを探索します(searchStart_Click)。
searchStart_Clickの解説
最初は OPENリストにはSが入った状態でスタートします。そしてノードを入れる変数 n と m を用意します。m にはOPENリストの先頭から取り出したノードが、m にはその n から移動できるノードが入ります。この先頭から取り出す処理を whlie の始まりのあたりで、m を順番に代入する処理を foreach 内で行っています。f_m_nの計算に必要なもの
m.g には、m にたどり着くまでの辺の合計の重みが入ります。例えば、n=A から m=F への移動を考えるとき、S-A 間の重みである1と、A-F 間の重みである6を足した、7という重みが入るといった感じです。m.hには、先ほど説明した通り、そのノード m のゴールまでの見積もりの値が入っています。
edge.Tagは、n から m の辺の重みが入っています。
f_m_n には、n から m へ移動した場合のゴールまでの予測の重みが入ると思います(多分)。。OPENリストでは、この値を元に毎回ソートしていると思われます。なので毎回 m を使用して、f_m_n = n.g + edge.Tag + m.h を計算しています。
if内の処理
さて、f_m_nを計算したら、次は n から m に移動した時に、今まで調べてきた予想重み (m.f) より、新たに計算した (f_m_n) 重みの方が軽くなっているか調べます。もし軽くなっていたら、今までの道のりよりも近道を通ってそのノード m に到着したことになりますからね!それが、if内に対応しています。まず、今回の m ノードがまだ一回も訪れたことのないノードだった場合!(つまり、OPEN にも CLOSED にもまだはいっていない。)この時は、m の値を設定してから、OPENリストに入れてあげましょう。
次に、m はもうOPENリストに入っているんだけど、今調べてきた道のりの重みの方が軽くて近道だと思われる場合。(つまり、OPEN.Contains(m) == true && f_m_n < m.f) これは、もうOPENリストには入っているので、m の値だけ設定しなおしてあげるだけでOK!
そして、m はもう探索終わって CLOSED に入っているんだけど、前回調べた時より近道でこれたって場合!(CLOSED.Contains(m) == true && f_m_n < m.f) m の値を設定しなおして、OPENリストに再び追加してあげましょう。そして、 CLOSEDリストからは消してしまいます!
こちらが一つのノード n とそこから移動できる全ノード n に対して行う処理です!基本的に、今まで調べた重みより軽い重みが見つかったら、そっちに書き直してあげているだけです!念のため書いておきますが、father は親ノードのことです。これを覚えてもらえば、あとでどの順路でゴールについたかが、簡単にわかります!
結果
OPEN : S(0) CLOSED: OPEN : B(7) A(8) CLOSED: S(0) OPEN : A(8) H(10) F(12) C(15) CLOSED: S(0) B(7) OPEN : B(6) H(10) F(10) C(15) CLOSED: S(0) A(8) OPEN : H(9) F(10) C(14) CLOSED: S(0) A(8) B(6) OPEN : I(8) F(10) G(12) C(14) CLOSED: S(0) A(8) B(6) H(9) OPEN : F(10) G(11) C(14) CLOSED: S(0) A(8) B(6) H(9) I(8) OPEN : G(11) C(14) E(16) CLOSED: S(0) A(8) B(6) H(9) I(8) F(10) 成功 ゴールへの道: G<-I<-H<-B<-A<-S
こんな感じです。とりあえず、git の貼り方と、自分が後でなんとなくわかるようにメモれたので満足です笑