2019.5.14
・スタートアップゼミの課題に取り組む
経路選択モデルを様々なアルゴリズム、言語で実装して比較する。
アルゴリズムはDijkstra法、Bellman-Ford法、A*法、言語はCとPython。
3つのアルゴリズムについて理解した後、実装。結果をGISで可視化。GISがなかなかうまくいかず、意外と時間を食ってしまった。
Bellman-Ford法は、リンクコストが負の場合も計算できるので、災害時に配給がある、というようなリンクコストが負になりうるネットワークを想定して、Dijkstra法ではうまくいかないが、Bellman-Ford法だとちゃんと最短経路出せることを示す。
CとPythonの比較は前やったが、200倍くらい違う。
なぜか、A*の方がDijkstra法より遅くなったので、原因を考える。
A*はヒューリスティック関数をいじれる。マンハッタン距離と直線距離で計算時間比較する。
理論談話会の反省も踏まえて、スライド作りながらやる。
・ArcGisエラーあるある
- 南東、北西方向に、400mくらいズレる
- 地図の真ん中に点が表示される
→ 座標がNULLの点をプロットしている