clique basierend auf Ameisenkolonie

Question

Ich möchte alle k-Clique in ungerichteten Graphen finden. Daher muss ich einen Algorithmus auf Basis der Ameisenkolonie entwickeln, um alle k-Cliquen im Graph zu finden. Betrachten wir zum Beispiel diese benachbarten Matrix:

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 

In diesem benachbarten Matrix haben wir drei 3-Clique: (1,2,3), (2,3,4), (3,4,5)

Ich möchte diese K-Clique in jedem Diagramm finden. Anmerkung = K wird in den K-Cliquenalgorithmus eingegeben.

Answer 1

Solange ist K willkürlicher Wert ist ein Problem eingegeben wird, die k-Clique Problem ist NP-complete, was bedeutet, dass es nichts ist wesentlich besser als nur ein Brute-Force-Algorithmus - jeden Subgraphen von K Knoten nehmen und prüfen, ob es sich um eine repräsentiert Clique. Implementierungsdetails dieser Idee über Backtracking finden Sie unter here.

Answer 2

Mit Tags versehen, um ein Anti-Kolonie-Tag einzuschließen, aber Andrei ist korrekt - die Kolonien-Optimierung wird die NP-vollständige Barriere nicht durchbrechen, und das k-Clique-Problem hat nicht einmal einen Approximationsalgorithmus. (Approximationsalgorithmus kann nicht existieren, wenn ich mich richtig erinnere, außer P = NP.)

Die neueste Umfrage, die ich zufällig über ACO und das Cliquenproblem insbesondere weiß, ist etwa sechs Jahre alt, unten verlinkt. Es ist eine sehr schöne Studie, einschließlich erschöpfender Simulationen/Benchmarks für vier separate Techniken, und eine unmittelbare Schlussfolgerung ist, dass 2006 selbst modernste ACO-Ansätze nicht garantiert waren, die tatsächliche maximale Clique in den Benchmark-Problemen zu bekommen.

http://liris.cnrs.fr/Documents/Liris-1847.pdf