ドローンの配送アルゴリズム

まだ画面だけ。WindowsのWPFで開発している。WPFの素のコントロールはあまりクールではないので、デザインライブラリを導入することを検討中。（良さげなデザインライブラリ知ってたら教えてください）

このアプリの肝は、巡回セールスマン問題（※）の最適解をアルゴリズム毎に表示できることだ。
※巡回セールスマン問題（Travelling Salesman Problem）とは、地図上の都市とそれぞれの都市の間の移動時間が与えられた時、全ての都市をちょうど一度ずつ巡って出発点に戻る最短経路を見つける問題のこと。
総当たりで最適解を算出するので、O(n!)の複雑度が生じる。nの数が増えると、最新のコンピュータを用いても最適解を求めるのは不可能になるという特徴がある。

アルファベットA～Pを一度ずつ巡って出発点（左下のGoogleのロゴがある辺り）に戻る最短経路を総当たり法で求める場合、N = 16: (N-1)! = 1307674368000（1兆3076億）パターンをごり押しで計算することになる。今はこの処理を実装している。

現状、このアプリは道路を認識することはできない。つまりマーカー上を直線でつなげることしかできない。技術的に実現の目途が立ったら、道路を認識して最適な道筋を求めるアプリを開発したい。

ちなみに、地図画像は「google static maps api」 経由で取得したものを使っている
Overview  |  Maps Static API  |  Google Developers

今後はアプリを開発する過程も公開していきたい。（備忘録的な意味で）