Visual C++でWPFっぽく その2

昨日の続きです。
本当にVisual C++とSilverlightなんか組み合わせられるのか！？
という検証のために、簡単なVisual C++/Silverlightのアプリケーションを作ってみました。

巡回セールスマン問題を解くサンプルアプリ

巡回セールスマン問題？

巡回セールスマン問題とは、すべての都市を最短経路で巡回するために、
どういった順番で都市を回ればよいかを考える問題です。
都市がn個あるならば、その組み合わせは(n-1)!通りになります。
都市が10個程度ならば、数秒程度で計算が終わりますが、
都市が21個になると、組み合わせが20!=2432902008176640000通りになり、
現代最速のコンピュータを使ったとしても、私たちが死ぬ前に計算が終わることはありません。
そのため、巡回セールスマン問題は通常、総当りで解くようなことはせず、
分割統治法や遺伝的アルゴリズム(GA)、シミュレーテッド・アニーリング(SA)などのアルゴリズムを利用します。
ただし、こうしたアルゴリズムを利用した場合、真の最適解はまず得られません。
「最高ではないが、ある程度良い」結果（つまり局所最適）となります。

アプリの構成

今回、この巡回セールスマン問題を解くアプリケーションをサンプルとして作ってみました。
とりあえず、一番単純な総当り方式です。
下の絵はアプリのスクショです。


「都市を配置」ボタンを押すと、訪問すべき都市を指定された個数だけランダムに配置します。
スクリーンショットは、このボタンを押した後の様子を示しています。
（星が都市を表しています）


「巡回」ボタンを押すと、最適解を探索して、巡回ラインを引きます。
下のスクショは、最適解探索の進捗を示すプログレスバーを表示しています。
なお、画面ではわからないですが、プログレスバーはカラーアニメーションをしています。



下のスクリーンショットは、最適解を表示したものです。
なんとなく星座みたいに見えますね。



このアプリケーションは、HTML, Silverlight(JavaScript + XAML), Visual C++で動作しています。
それぞれの役割は、以下のとおりです。

• HTML……ボタンやキャンバスの配置
• XAML……画面表示
• JavaScript……XAMLの制御
• Visual C++……ボタンイベント、最適解計算、都市情報管理

「都市を配置」ボタンを押した場合の処理例だけ説明しておきます。
ボタンが押されると、Visual C++側のボタンイベントに対応付けられたメソッドがコールされます。
「都市を配置」ボタンの場合には、
Visual C++側の「都市を配置」するためのメソッドが呼ばれ、
都市のx,y座標を指定個数だけ作成します。
その後、Visual C++からJavaScriptの「XAMLに都市を配置する」関数を呼びます。
JavaScriptでは、指定座標にXAMLオブジェクトを追加していきます。
……とまあ、このような形で、Visual C++とJavaScriptが連携しながら処理を行っていきます。


表示(View)を全てHTMLとXAMLに任せていますので、C++部分はViewにノータッチです。
そのため、星をアニメーションさせたり、都市を星から家にしたり、
背景に壁紙を用意したりすることも、C++を弄らないでも可能です。
Visual C++では、何しろpngやjpegを読み込むだけでも一苦労ですから、
XAMLだけで表示を変更できるのは、意外と便利かと思います。


アプリケーションのバイナリも置いておきます。
興味があったら使ってみてください。
（あんまり気合を入れて作ってはいないので、色々と手抜き部分がありますが）
なお、実行には、MFC9.0とmsvcr90.dllが必要ですので、適宜ダウンロードしてください。
ダウンロードページへ