アルゴリズム工学データベース離散最適化

グラフ分割問題


Java を有効にするとデモが表示されます。
Please enable Java.

500頂点×5辺 500頂点×10辺 500頂点×20辺 500頂点×40辺
1000頂点×5辺 1000頂点×10辺 1000頂点×20辺 1000頂点×40辺


 このデモは、グラフ分割問題に対する Tabu Search の実行状況を リアルタイムに示したものです。 グラフ分割問題とは、グラフが与えられたときにカットの重みの和を最小に するような点の分割を求める問題です。 この場合では全ての枝の重みを1と仮定しているので、カットの重みの和と カットに含まれる枝の本数は同じになります。

 上記の Current Solution や Best Solution の図では、白い線が枝、赤と水色の円 が点を示しています。赤の点集合と水色の点集合に分割していますが、この場合、 点数が偶数で赤と水色の点集合に含まれる点の数は等しいものと仮定します。 両端点の色が異なる枝はカットに含まれますので、 このような枝の本数を最小にするのが問題の目的になります。

 Current Solution の図は現在の Tabu Search が探索している解、 Best Solution の図は、これまでの探索で最も優れた解を表しています。また、 下の黄緑色の波形は目的関数(カットに含まれる枝の本数)の推移を示しています。 下の方が目的関数の値が小さく、 黄色の線は現在までの最良解の目的関数の位置を表しています。

 目的関数値が悪化する解も探索するのが Tabu Search の大きな特徴の一つであって、 目的関数値が上下しながらより優れた解に到達していく様子がこの波形から読み取る ことができます。

藤澤 克樹

このデモは 京都大学 藤澤克樹 先生 のプログラムを利用しています。


土村 展之(tutimura@logopt.com)
<最終更新日 2000年4月21日>