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

最大クリーク問題


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

狭く探索
広く探索
500頂点×5辺 500頂点×10辺 500頂点×20辺 500頂点×40辺
1000頂点×5辺 1000頂点×10辺 1000頂点×20辺 1000頂点×40辺


 このデモは、最大クリーク問題に対する Tabu Search の実行状況をリアルタイムに示したものです。 最大クリーク問題とは、グラフが与えられたときに最も位数の大きい(点数の多い)、 クリーク(完全部分グラフ)を求める問題です。

 ●がグラフの点、白い線が枝を示しています。 この中で青い点集合は、現在までに得られている最大のクリークを示しています。 また、赤い点集合は現在、探索の対象となっている点集合を示しています。 赤い点集合がいったん広がって、その後小さくなっていくまでを1反復と考えます。 このとき一度に探索する範囲を広げると、 つまり一度に多くの点を赤い点集合に組み入れると1反復の時間はかかりますが、 局所最適解からは脱出しやすくなります。

このデモは 藤澤克樹先生(京都大学)久保幹雄先生(東京商船大学)のプログラムを利用しています。


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