夏学期ゼミ #2 4/9 プログラミング課題1：経路探索問題(鈴木)

■Dijkstra法 スライドP.10
青字：リンクコスト
黒字：一時ラベル（そのノードまでの暫定の最小コスト）
黒字*：永久ラベル（そのノードまでの確定した最小コスト）

P.12練習問題 解答
ノード0の永久ラベル0
→ノード⓪に隣接するノード①② 一時ラベルはそれぞれ4,1
→ノード②の一時ラベルを永久ラベルに
→ノード②に隣接するノード⑤ 一時ラベルは4
→ノード①の一時ラベルを永久ラベルに ※⑤でもOK
→ノード①に隣接するノード③ 一時ラベルは6
→ノード⑤の一時ラベルを永久ラベルに
→ノード⑤に隣接するノード④⑧ 一時ラベルはそれぞれ6,11
→ノード③の一時ラベルを永久ラベルに ※④でもOK
→ノード③に隣接するノード④⑥ 一時ラベルは8(6より大きいので×),9
→ノード④の一時ラベルを永久ラベルに
→ノード④に隣接するノード⑦ 一時ラベルは7
→ノード⑦の一時ラベルを永久ラベルに
→ノード⑦に隣接するノード⑧ 一時ラベルは10
→ノード⑥の一時ラベルを永久ラベルに
→…

浦田さん：一時ラベルが同率の場合は？
＞どっちを確定してもいい
小林さん：リンクコストが負の場合は？
＞後で

Junji Urata から全員に: 12:51 PM
聞こえづらかったら，言ってください．
渡邉 葵 から全員に: 12:51 PM
最短経路の辿り方については、各ノードへの最小コストを求めていく段階で、直前にいたノード(どのノードからの移動でコストが最小になるか)を、リストで保持しておいて、ゴールから逆向きに辿っていく、と言う方法もよく使われると思います
Junji Urata から全員に: 01:10 PM
リストで保持？
Taiki Suzuki から全員に: 01:11 PM
リストのインデックスとノード番号を対応させて，リストの要素として直前にいたノード番号を格納しておく，ということだと思います
Junji Urata から全員に: 01:13 PM
どうもです．フォローはありがたいですが，ざっくりした説明だとわかった感じになるだけで，基礎編の効果がないので，その点，よろしくお願いします．
渡邉 葵 から全員に: 01:14 PM
はい、フォローありがとうございます


■A*法 スライドP.18
g(n):青字リンクコスト(Dijkstraと同じ)
h(n):ゴールからのマンハッタン距離
f(n):トータルコスト g(n)+h(n)

P.19練習問題 解答
f(0)=g(0)+h(0)=0+4=3
→ノード0に隣接するノード1,2 f(1)=4+5=9, f(2)=1+3=4
→ノード2を取り出す
→ノード2に隣接するノード5 f(5)=4+1=5
→ノード5を取り出す
→ノード5に隣接するノード4,8 f(4)=6+2=8, f(8)=11+0=11
→ノード4を取り出す
→ノード4に隣接するノード7 f(7)=7+1=8
→ノード7を取り出す
→ノード7に隣接するノード8 f(8)=10+0=10
→ノード8を取り出す
→ノード8はゴールなので終わり 0-2-5-4-7-8


■pythonの基本
・言語について 研究室ではR,pythonが主流
Cは鈴木が書ける．javaは月田が書ける(伝統的なマップマッチングのコード)

積＝product a*b
べき乗＝exponentiation a**b

・CSVとは？ データをカンマ形式で格納するファイル形式．
　number,digits
　12,2
　5469,4　...