無向グラフですべての k-clique を見つけたい。したがって、グラフ内のすべての k クリークを見つけるために、アリのコロニーに基づいた正確なアルゴリズムが必要です。たとえば、次の隣接行列を考えてみましょう。
0 1 1 0 0
1 0 1 1 0
1 1 0 1 1
0 1 1 0 1
0 0 1 1 0
この隣接行列には、(1,2,3)、(2,3,4)、(3,4,5) の 3 つの 3 クリークがあります。
すべてのグラフでこのkクリークを見つけたいです。note=K は K-clique アルゴリズムの入力です。
ant-colony タグを含めるように再タグ付けされましたが、Andrei は正しいです。ant-colony 最適化は NP 完全バリアを破ることはなく、特に k クリーク問題には近似アルゴリズムさえありません。(私の記憶が正しければ、P=NP でない限り、近似アルゴリズムは存在しません。)
ACO と特にクリークの問題について話していることについて私がたまたま知っている最新の調査は、約 6 年前のもので、以下にリンクされています。これは非常に優れた研究であり、4 つの個別の手法の徹底的なシミュレーション/ベンチマークが含まれており、2006 年には最先端の ACO アプローチでさえ、ベンチマーク問題で実際の最大クリークを得ることが保証されていなかったという 1 つの即時の結論があります。