アルゴリズム工学データベース
---

アルゴリズムの可視化について

〜 Webブラウザ上で動くデモの作り方 〜

---



アルゴリズムを実装したプログラムを公開するにあたって、ダウンロードせずとも、 Webブラウザ(Netscape Navigater や Internet Explorer) で手軽に表示することのできるデモを準備することが、課題の一つとなっております。 そこで、その方法を考えてみました。 ブラウザとのインターフェイスについて4種類、時間軸の使い方について2種類あります。


ブラウザとのインターフェイス

Webブラウザにどのようにしてデモプログラムを送るか、 単純で自由度の低いものから、複雑で自由度の高いものまで、 大まかにこの4つの方法に分類できると思います。

HTML+Java server
browser
HTMLJava
→ → →
あらかじめ用意しておいたデータをHTML文書に埋め込んでおき、 Javaプログラムでそれを表示させる。

CGI+Java server 送信ボタン
← ← ←
browser
HTMLJava
→ → →
ユーザが入力した問題をサーバーで解き、結果をブラウザに送ってJavaプログラムで表示させる。 検索エンジン等の「キーワードに対するURLを返すサービス」の表示にJavaを用いたようなもの。

Java+通信 server 自動
← ← ←
browser
Java
→ → →
送信ボタンをユーザが押したときではなく、 Javaプログラムによっていつでもサーバーに問題を送り、結果表示を行える。

Javaのみ
browser
Java
単純にすべてのプログラムをJavaで開発する。 Javaプログラム実行中には、サーバーは必要ない。

単純 <<-- -->> 複雑

HTML
+Java
CGI
+Java
Java
+通信
Java
のみ
(参考)
down load
ブラウザで見られる ×
ユーザの入力する問題を解く 文字入力 ×
座標入力 × ×
アルゴリズムの進行に
ユーザが介入する
× ×
ネットワークなしに動く ×
大量のデータ転送
(100Kbyte以上)
× × ×
公開に必要なもの プログラムの出力結果のみ サーバーで動くプログラム サーバーで動くプログラム Javaで記述したプログラム プログラムのソースまたはバイナリ
ブラウザで見せるための作業工数 2日〜 4日〜 3日〜 4日〜 ---
実例 量子計算 ジョブショップ問題 LEDA in the Web 最小カット 多数
問題点 画像が動くだけで、面白みに欠ける。 マウスによる座標入力ができない。 実行にはインターネット接続が必要。 複雑なアルゴリズムは製作できない。大規模問題は解けない。 ユーザの手間が大きい。実行環境が限定される。
特徴 プログラムを公開せずにすむ。量産可能。 量産可能。 マウスによる座標入力が可能。 実行環境を選ばない。自由度が高い。 大規模問題が解ける。

HTML
+Java
CGI
+Java
Java
+通信
Java
のみ
(参考)
down load


時間軸の使い方

コンピュータ画面の2次元空間に、時間軸を加えた3次元 の世界での表現について考えてみました。 時間軸の使い方により、アルゴリズムの表現方法が大きく異なります。

時間軸をアルゴリズムの進行に対応させる

アルゴリズムにおける1局面を2次元で表示が行える場合、 アルゴリズムの進行に応じて表示を変化させる。 例:量子計算

以下の条件を満たすサンプルデータを用意していただけると、 デモを作りやすいです。

2次元空間で表現しにくいものを3次元で表現する

3次元以上のものを表示するのに、 (見る人の操作により)動かしながら2次元に射影する。 例:無向グラフの表示

★3次元以上のものを、 アルゴリズムの進行に応じて表示を変化させるのは困難と思います。 何か良い方法があれば、ご教授下さい。


プログラムの記述言語

使用していただける記述言語は、以下のようになります。

HTML+Java
問題を解いた結果を保存しておくだけなので、 どのような言語/アプリケーション/パッケージでも使えます。 手計算の結果を用いることすら可能です。
CGI+Java Java+通信
サーバーでプログラムが動きさえすれば、問題ありません。 (サーバーは、現在は HP-UX ですが、Solaris 7 に移行します。)
C/C++/FORTRAN77/Pascal/Perlなどの言語でしたら十分利用できます。 (以前 FORTRAN は問題があるとお伝えしましたが、 その後の調査で FORTRAN77 はまったく問題ないことが判明しました。 FORTRAN90/95 は有料コンパイラを購入する必要がありそうです。)
Visual Basic などの MS-Windows 専用言語は利用不可能です。
利用するアプリケーションやパッケージについては、 LEDA は可能、Mathematica は購入する必要?があります。
Javaのみ
すべてをJavaで開発する必要があります。
(参考)down load
開発したままを公開すれば良いと思います。 プログラムパッケージ製作について もご覧下さい。

デモを作る際の作業手順

デモにしたいプログラムをお持ちの場合、次のような手順でデモを作ります。
  1. 時間軸の使い方を決めて下さい。
  2. HTML+Java CGI+Java Java+通信 Javaのみ の どのモデルを選択するか決めて下さい。 (初めに HTML+Java を作り、 完成してから CGI+Java に移行していただくのが楽だと思います。 また、グラフアルゴリズムでは、無条件に Java+通信 を 選ぶことになるかもしれません。)
  3. アルゴリズムに関する打ち合せ。e-mailで、または直接ご説明下さい。
  4. 次のものをご用意下さい。
    HTML+Java
    出力データ
    CGI+Java Java+通信
    プログラムとサンプル問題 (この場合、若干プログラムの修正をお願いするかもしれません。 プログラムは文字による入出力、 できれば標準入出力を使っていただくと助かります。 また、こちらで用意したファイルをパッケージに取り込んでいただくのも 良いと思います。)
    Javaのみ
    Javaプログラム :-p
  5. アルゴリズムの簡単な説明文、背景の解説なども、必要に応じてご用意下さい。 なお、数式等は LaTeX 形式で書いていただくと、こちらで画像に変換します。

CGI+JavaJava+通信 を作る上でのお願い

CGI+JavaJava+通信 では、ユーザーの操作によって問題を解き直し、 結果を表示しますが、正常に動作するためにはいくつか条件があります。

これらの条件を満たすように、 プログラム製作と、解くべき問題の制約を考えて頂けると助かります。


データベース [ 離散最適化 | グラフ | 幾何 | 並列/分散 ]
[ キーワード検索 ] [ リンク集 ] [ 動作確認環境 ]
参加メンバー [ 可視化 | パッケージ製作 | デバッグ術 | 標準入出力 | Makefile | 雛型 ]

土村 展之(tutimura@logopt.com)
<最終更新日 2000年1月11日 0時35分>