キノコの自省録

テクノロジーとコンテンツの融合を目指して

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++では、何しろpngjpegを読み込むだけでも一苦労ですから、
XAMLだけで表示を変更できるのは、意外と便利かと思います。


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