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

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

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