　どうも！今日の目的は”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 間の重みである１と、A-F 間の重みである６を足した、７という重みが入るといった感じです。
　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 の値だけ設定しなおしてあげるだけでＯＫ！

　そして、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 の貼り方と、自分が後でなんとなくわかるようにメモれたので満足です笑