読者です 読者をやめる 読者になる 読者になる

196の日記

完全に開発メモと雑談、その他忘れそうな計算式などを書き溜める場所になっています!

A(A*)アルゴリズムをC#で書く

勉強

 どうも!今日の目的は”git からソースコードを持ってきて貼る”です笑 しかし、ただ貼るだけではつまらないので、最近触った A*アルゴリズムをかるーーく後世の自分のために解説してみようかなと思います!笑 本当にかるーくです!


今回探索する図

今回探索する図はこちら。
f:id:thinline196:20161021224255j:plain
 
 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 の貼り方と、自分が後でなんとなくわかるようにメモれたので満足です笑