Program Demos


MASU Java-Applets
■ リバーシゲーム
(2000年度卒研生武田朋航君による)

■ 整列アルゴリズムのアニメーション
(選択法，挿入法，バブル，シェル，クィック，マージ，ヒープ)
整列アルゴリズムはデータ構造とアルゴリズムに関する授業で習うはず． その内容を理解するのにこのアプレットが役立つ．
■巡回セールスマン問題のアルゴリズムのデモ：
  • 最小スパニング木法
    最小スパニング木を求めてからその上で深さ優先探索を行い，たどった頂点の列を shortcutするとセールスマンツアーを得る．三角不等式が成り立つ場合， 求めたセールスマンツアーのコストは最適なツアーのコストの2倍以内である．
  • Christofides法
    まず最小スパニング木Tを求めて，次にTにおいて奇の次数を持つ頂点間で最小重み 完全マッチングMを求める．MをTに加えるとEulerグラフ（一筆書きのできるグラフ） Hを得る．さらに，H上で一筆書きを行い，たどった頂点の列をshortcutすると セールスマンツアーを得る．三角不等式が成り立つ場合，求めたセールスマンツアー のコストは最適なツアーのコストの1.5倍以内である．
  • 3-opt法
    適当なセールスマンツアーから始め，それをどんどん改善していく方法．現在のツアー Tを改善するには，Tから隣接しない２辺を選んで削除してコストのより小さい新しい２辺で つなぎ直すか，または，Tから隣接しない３辺を選んで削除してコストのより小さい新しい３辺で つなぎ直す．求めたセールスマンツアーのコストについて理論的な保証がない．
■よく知られているグラフアルゴリズムおよび組み合わせ最適化問題のデモ：
  • 最大重み２-マッチング問題
    辺に重みが付いているグラフGから，お互いに交わらないパスまたはサイクルの集まりS を選ぶ問題．ただし，Sに属する辺の重みの総和をできるだけ大きくしたい． この問題はNP困難な最適化問題の近似アルゴリズムの設計に役立つ．
  • 最大重みマッチング問題
    辺に重みが付いているグラフGから，お互いに端点を共有しない辺の集まりM を選ぶ問題．ただし，Mに属する辺の重みの総和をできるだけ大きくしたい． この問題は最も重要な最適化問題の１つで，多くの応用を持つ．
  • 最小重み完全マッチング問題
    辺に非負の重みが付いているグラフGから，お互いに端点を共有しない辺の集まりM を選ぶ問題．ただし，Mに属する辺の本数を最大に，かつ，その重みの総和をできるだけ 小さくしたい．この問題は最も重要な最適化問題の１つで，多くの応用を持つ．
  • オイラーグラフの判定問題（別名：一筆書き可能性の判定問題）
    多重グラフGのどれかの頂点から出発して，Gの各辺をちょうど一度ずつ辿っていける か否かを判定する問題．
  • 幅優先探索
    グラフアルゴリズムの基礎となる問題．
  • 深さ優先探索
    グラフアルゴリズムの基礎となる問題． 特に，迷路の設計と解決によく使われる．また，その変形が人工知能で多用されている．
  • 最小スパニング木（Kruskal法）
    グラフアルゴリズムおよび組み合わせ最適化の基礎となる問題．
  • 最小スパニング木（Prim法 & Heap）
    グラフアルゴリズムおよび組み合わせ最適化の基礎となる問題．
  • 最小スパニング木（Prim法 & Fibonacci Heap）
    グラフアルゴリズムおよび組み合わせ最適化の基礎となる問題．
  • 単一始点最短路（Dijkstra法 & Heap）
    グラフアルゴリズムおよび組み合わせ最適化の基礎となる問題．
  • 単一始点最短路（Dijkstra法 & Fibonacci Heap）
    グラフアルゴリズムおよび組み合わせ最適化の基礎となる問題．
■ RSA暗号の実装
(2001年度卒研生及川正晃君・浅田恵美さんによる)
鍵の生成の所で時間がかかりすぎて（あなたのコンピュータの性能にもよるが）、 気長に待てる人は是非覗いてみてください。

■ 木におけるLCA質問に定数時間で答える(Answering on-line LCA queries in trees in O(1) time):
このアプレットで根付き木を描き、木の頂点の中から２頂点を指定すると、 その２頂点の最近共通祖先(lowest common ancestor)を定数時間内で知ることができる。 Schieber & Vishkinのアルゴリズムに基づいている。

■ 弦グラフのPerfect Elimination Ordering (PEO)を求める線形時間アルゴリズムの実装
(2003年度卒研生小山明大君による. )
このアプレットでグラフを描き，そのグラフが弦グラフであるか 否かを判定する．弦グラフの場合，そのグラフのPEOを1つ見つけて表示する． 弦グラフではない場合，そのグラフを弦グラフに変えるために追加する辺の集合を １つ見つけて表示する．Tarjanらのアルゴリズムに基づいている．