アルゴリズムの可視化について
〜 Webブラウザ上で動くデモの作り方 〜
アルゴリズムを実装したプログラムを公開するにあたって、ダウンロードせずとも、 Webブラウザ（Netscape Navigater や Internet Explorer） で手軽に表示することのできるデモを準備することが、課題の一つとなっております。 そこで、その方法を考えてみました。 ブラウザとのインターフェイスについて４種類、時間軸の使い方について２種類あります。
ブラウザとのインターフェイス
Webブラウザにどのようにしてデモプログラムを送るか、 単純で自由度の低いものから、複雑で自由度の高いものまで、 大まかにこの４つの方法に分類できると思います。
あらかじめ用意しておいたデータをHTML文書に埋め込んでおき、 Javaプログラムでそれを表示させる。
browser →
→ → →
ユーザが入力した問題をサーバーで解き、結果をブラウザに送ってJavaプログラムで表示させる。 検索エンジン等の「キーワードに対するURLを返すサービス」の表示にJavaを用いたようなもの。
送信ボタン
← ← ←
browser → → →
送信ボタンをユーザが押したときではなく、 Javaプログラムによっていつでもサーバーに問題を送り、結果表示を行える。
自動
← ← ←
browser → → →
単純にすべてのプログラムをJavaで開発する。 Javaプログラム実行中には、サーバーは必要ない。
browser
|
||||||||
| HTML +Java |
CGI +Java |
Java +通信 |
Java のみ |
(参考) down load |
||||
|---|---|---|---|---|---|---|---|---|
| ブラウザで見られる | ○ | ○ | ○ | ○ | × | |||
| ユーザの入力する問題を解く | 文字入力 | × | ○ | ○ | ○ | ○ | ||
| 座標入力 | × | × | ○ | ○ | ○ | |||
| アルゴリズムの進行に ユーザが介入する |
× | × | △ | ○ | ○ | |||
| ネットワークなしに動く | ○ | △ | × | ○ | ○ | |||
| 大量のデータ転送 (100Kbyte以上) |
× | × | × | ○ | ○ | |||
| 公開に必要なもの | プログラムの出力結果のみ | サーバーで動くプログラム | サーバーで動くプログラム | Javaで記述したプログラム | プログラムのソースまたはバイナリ | |||
| ブラウザで見せるための作業工数 | ２日〜 | ４日〜 | ３日〜 | ４日〜 | --- | |||
| 実例 | 量子計算 | ジョブショップ問題 | LEDA in the Web | 最小カット | 多数 | |||
| 問題点 | 画像が動くだけで、面白みに欠ける。 | マウスによる座標入力ができない。 | 実行にはインターネット接続が必要。 | 複雑なアルゴリズムは製作できない。大規模問題は解けない。 | ユーザの手間が大きい。実行環境が限定される。 | |||
| 特徴 | プログラムを公開せずにすむ。量産可能。 | 量産可能。 | マウスによる座標入力が可能。 | 実行環境を選ばない。自由度が高い。 | 大規模問題が解ける。 | |||
| HTML +Java |
CGI +Java |
Java +通信 |
Java のみ |
(参考) down load |
||||
時間軸の使い方
コンピュータ画面の２次元空間に、時間軸を加えた３次元 の世界での表現について考えてみました。 時間軸の使い方により、アルゴリズムの表現方法が大きく異なります。
時間軸をアルゴリズムの進行に対応させる アルゴリズムにおける１局面を２次元で表示が行える場合、 アルゴリズムの進行に応じて表示を変化させる。 例：量子計算
以下の条件を満たすサンプルデータを用意していただけると、 デモを作りやすいです。
- １つの局面にアイティム（動くもの）が５〜３０個程度ある
- 表示する局面が５〜３０局面ある
- ２つの局面を滑らかに補間できる
- 情報を「１局面１行」のテキスト形式に書き出せる
２次元空間で表現しにくいものを３次元で表現する ３次元以上のものを表示するのに、 （見る人の操作により）動かしながら２次元に射影する。 例：無向グラフの表示
★３次元以上のものを、 アルゴリズムの進行に応じて表示を変化させるのは困難と思います。 何か良い方法があれば、ご教授下さい。
プログラムの記述言語
使用していただける記述言語は、以下のようになります。
- 問題を解いた結果を保存しておくだけなので、 どのような言語/アプリケーション/パッケージでも使えます。 手計算の結果を用いることすら可能です。
- サーバーでプログラムが動きさえすれば、問題ありません。 （サーバーは、現在は HP-UX ですが、Solaris 7 に移行します。）
C/C++/FORTRAN77/Pascal/Perlなどの言語でしたら十分利用できます。 （以前 FORTRAN は問題があるとお伝えしましたが、 その後の調査で FORTRAN77 はまったく問題ないことが判明しました。 FORTRAN90/95 は有料コンパイラを購入する必要がありそうです。）
Visual Basic などの MS-Windows 専用言語は利用不可能です。
利用するアプリケーションやパッケージについては、 LEDA は可能、Mathematica は購入する必要？があります。- すべてをJavaで開発する必要があります。
- 開発したままを公開すれば良いと思います。 プログラムパッケージ製作について もご覧下さい。
デモを作る際の作業手順
デモにしたいプログラムをお持ちの場合、次のような手順でデモを作ります。
- 時間軸の使い方を決めて下さい。
の どのモデルを選択するか決めて下さい。 （初めに
- アルゴリズムに関する打ち合せ。e-mailで、または直接ご説明下さい。
- 次のものをご用意下さい。
- 出力データ
- プログラムとサンプル問題 （この場合、若干プログラムの修正をお願いするかもしれません。 プログラムは文字による入出力、 できれば標準入出力を使っていただくと助かります。 また、こちらで用意したファイルをパッケージに取り込んでいただくのも 良いと思います。）
- Javaプログラム :-p
- アルゴリズムの簡単な説明文、背景の解説なども、必要に応じてご用意下さい。 なお、数式等は LaTeX 形式で書いていただくと、こちらで画像に変換します。
- ユーザーが行える操作に「あらかじめ結果が準備されている」とは感じさせない程度の自由度がある。
- 表示プログラムの製作が楽（≒可能）になるような制約をつける。
- プログラムが一定時間以内（１秒程度）に、確実に終了する。
- 結果表示に必要なデータ量が、極端に大きくならない。
- 情報のやりとりには標準入力・標準出力を用いる。
これらの条件を満たすように、 プログラム製作と、解くべき問題の制約を考えて頂けると助かります。
