Hi,
gibt es einen effizienten Algorithmus, um einen vollständigen Graphen Km in einem anderen (unvollständigen) Graphen Kn zu finden (n>m)?
Oder ist das Problem NP-äquivalent? (Was natürlich auch nicht ausschließt, dass es eine Lösung gibt.)
Ein Monte-Carlo-Algorithmus würde mir evtl. auch schon weiterhelfen.
Wie natürlich jeder Denkanstoß oder Ansatz auch!
Vielen Dank,
Klaus
gibt es einen effizienten Algorithmus, um einen
vollständigen Graphen Km in einem anderen (unvollständigen)
Graphen Kn zu finden (n>m)?Oder ist das Problem NP-äquivalent? (Was natürlich auch nicht
ausschließt, dass es eine Lösung gibt.)
Hallo Klaus,
das Problem ist als das „maximum clique problem“ bekannt
und ist NP-hart und kann zudem nicht approximiert werden,
ist als ziemlich schwierig.
Der Ausweg ist, Suchheuristiken zu verwenden, die gute Lösungen
finden, aber keine Garantie für die Güte geben.
Googlen bei scholar.google.de nach
„maximum clique problem“ (evolutionary OR search OR genetic)
liefert viele Paper, allerdings kann ich Dir da keine Empfehlung geben,
welches gut ist.
Viele Grüße
Thorsten
Moien
gibt es einen effizienten Algorithmus, um einen
vollständigen Graphen Km in einem anderen (unvollständigen)
Graphen Kn zu finden (n>m)?
Hast du nicht wenigstens noch eine Zusatzinformation ? Z.B. welcher Punkt sicher im v. Graphen drin ist ?
Ein Monte-Carlo-Algorithmus würde mir evtl. auch schon
weiterhelfen.
Muss es die beste Lösung finden oder nur irgendeine?
cu
Ich kann mittlerweile noch etwas mehr dazu sagen:
Jeder Knoten in Kn hat zwei Attribute Typ und Version, die gemeinsam den Knoten Unique machen.
Beispiel: Typ=Farbe, dann kann gibt es evtl. 5 grüne Knoten, drei gelbe und 4 blaue. Keine Knoten des selben Typs können untereinander über Kanten verbunden sein!
Jetzt suche ich alle vollständige Graphen K3 (K3, da 3 Farben). Diese vollständigen Graphen enthalten nun zwingend immer einen Knoten von jedem Typ.
Vielleicht lassen sich die Graphen über Muster in der Adjazentmatritzen von Kn finden?
Das sollte die Sache jetzt doch stark vereinfachen, und wir haben wohl kein hartes NP-Problem mehr.
Danke auf jeden Fall schon mal für die Antworten!
Moien
Beispiel: Typ=Farbe, dann kann gibt es evtl. 5 grüne Knoten,
drei gelbe und 4 blaue. Keine Knoten des selben Typs können
untereinander über Kanten verbunden sein!
Dann kann ein vollständiger Graph maximal #-der-Farben Knoten. Das vereinfacht die Sache enorm.
Für alle Knoten
hat der Knoten #-der-Farben -1 Nachbarn ?
Ja: Knoten und seine Nachbarn sind ein vollständiger Graph
Nein: Konten wegschmeissen
Er hat mehr Nachbarn: Fehler im Graphen.
cu
Dann kann ein vollständiger Graph maximal #-der-Farben Knoten.
Das vereinfacht die Sache enorm.
Das ist zwar richtig, doch der folgende Ansatz funktioniert nicht, da
ein Knoten der Farbe grün, kann ja k blaue i gelbe Nachbarn haben mit k+i>#-der-Farben!
Für alle Knoten
hat der Knoten #-der-Farben -1 Nachbarn ?
Ja: Knoten und seine Nachbarn sind ein vollständiger Graph
Nein: Konten wegschmeissen
Er hat mehr Nachbarn: Fehler im Graphen.
Moien
Dann kann ein vollständiger Graph maximal #-der-Farben Knoten.
Das vereinfacht die Sache enorm.Das ist zwar richtig, doch der folgende Ansatz funktioniert
nicht, da
ein Knoten der Farbe grün, kann ja k blaue i gelbe Nachbarn
haben mit k+i>#-der-Farben!
Sorry, ich sollte solche Sachen nicht auf die schnelle schreiben.
Ermittel die Anzahl der unterschiedlichen Farben der Nachbarn pro Punkt. Alles unter X fliegt. Das reduziert den Graphen hoffentlich ein bisschen (Egal wie effizent der Algo ist, jeder eingesparte Knoten ist ein guter Knoten).
Jeder Knoten kann an vielen vollständigen Graphen beteiligt sein. Das macht die Sache so komplex. Man kann also nicht drum rum jeden Knoten zu testen und als Startknoten zu nehmen.
An sich ist es ein Problem aus der Kombinatorik: man hat für jeden Startknoten X Urnen mit Inhalt (Nachbarn nach Farben geordnet) und muss aus jeder Urne ein Element ziehen. Die Kunst ist es nun die Anzahl der Tests zu reduizeren ohne einen Fall zu übersehen. Als naiver Ansatz:
Erweiterung (Farbe i){
Wähle Nachbarn aus Farbe i aus
{
Teste ob bisheriger Graphen noch vollständig ist, return falls nicht.
falls noch Farben über:
Erweiterung (Farbe i+1)
falls nicht: Graph gefunden
}
}
Die Reihenfolge der Farben sollte eine grosse Rolle spielen. Kann man früh eine Kombination ausschliessen so reduizert sich die Anzahl der Tests stark. Gefühlsmässig würde ich die Farben nach aufstiegender Anzahl der Elemente sortieren und bei der kleinsten anfangen.
Der Test muss auch nur kucken ob das neue Elemente Kanten zu allen bisherigen hat, Startknoten ausgeschlossen (Der Startknoten muss eine Verbindung haben, sonst wäre das Teil gar nicht in den Urnen mit drin).
Wenn man einen Startknoten vollständig durchgeackert hat kann man ihn löschen. Angenommen der Knoten war rot. Falls einer seiner Nachbarn nur einen roten Nachbarn hatte kann man den ebenfalls löschen (Reduzierung der Anzahl der Knoten, kann man sehr schnell implementieren).
… es gibt bestimmt noch weitere Ansätze. Aber im Moment komm ich nur auf diesen …
viel Glück.
… es gibt bestimmt noch weitere Ansätze. Aber im Moment komm
ich nur auf diesen …viel Glück.
Vielen Dank!
Diese Methode beruht jetzt auf der Idee die Komplexität des Problems durch „ausfiltern“, etc. zu reduzieren. hat man allerdings 1500 Knoten (wie in meinem Fall), so lässt sich das nicht mehr so schnell machen (worst case 1500! = sehr groß 
)
Mal schauen, was sich so alles noch optimieren lässt und wie schnell ich werde…
Die Idee das Problem über die Adjazensmatritzen zu lösen beschäftigt mich noch. Vielleicht kommt auch dabei was raus.
Moien
Diese Methode beruht jetzt auf der Idee die Komplexität des
Problems durch „ausfiltern“, etc. zu reduzieren.
Jopp. Und sie findet alle maximalen v. Graphen.
hat man
allerdings 1500 Knoten (wie in meinem Fall), so lässt sich das
nicht mehr so schnell machen (worst case 1500! = sehr groß
)
Willst du Speed oder brauchst du immer und in jedem Fall alle ?
Das reizt mich jetzt: hast du 2-3 Beispielgraphen …?
Die Idee das Problem über die Adjazensmatritzen zu lösen
beschäftigt mich noch. Vielleicht kommt auch dabei was raus.
Wenn du solche Matrixen benutzt sind das wahrscheinlich ziemlich dichte Graphen. Da könnte es helfen die nicht möglichen Kombinationen vorzufiltern.
cu
Jetzt suche ich alle vollständige Graphen K3 (K3, da 3
Farben).
Hallo,
wenn Du nur Dreiecke finden möchtest, hilft dieses Paper weiter:
http://i11www.iti.uni-karlsruhe.de/people/schank/pub…
Oder suchst Du auch größere Cliquen?
Was ist eigentlich die konkrete Anwendung? (Nur so interesse-halber)
Grüße
Thorsten
Willst du Speed oder brauchst du immer und in jedem Fall alle
Beides. Ich brauch alle, da ich anschließend die gefundenen Graphen priorisiere. Dies kann ich allerdings erst wenn ich alle gefunden habe, da die Kriterien von den gefundenen Graphen abhängig sind.
Die Anwendung, die die Graphen nachher sucht, sollte auch nicht länger als ein paar Minuten benötigen.
Das reizt mich jetzt: hast du 2-3 Beispielgraphen …?
leider habe ich selbst keine realistischen Beispieldaten. 1500 Knoten können als Worst-Case angesehen werden. Immer ca 100 bilden einen vollständigen Graphen (z.b. K0-101, K102-202, K203-303). Die weiteren Kanten sind vollständig unbekannt! Es können ein paar Dutzend, aber auch ein paar Tausend sein.
Die Idee das Problem über die Adjazensmatritzen zu lösen
beschäftigt mich noch. Vielleicht kommt auch dabei was raus.Wenn du solche Matrixen benutzt sind das wahrscheinlich
ziemlich dichte Graphen. Da könnte es helfen die nicht
möglichen Kombinationen vorzufiltern.
Lässt sich leider so nicht sagen - eben abhängig davon wieviele Kanten existieren…
Vielleicht muss ich mir doch nochmal die Monte-Carlo-Algorithmen genauer anschauen…
Grüße,
Klaus
Moien
Die Anwendung, die die Graphen nachher sucht, sollte auch
nicht länger als ein paar Minuten benötigen.
Das ist bei 1500 Knoten auch ohne Voodoo drin. Kuck dir mal das an: http://www.nlsde.buaa.edu.cn/~kexu/benchmarks/graph-… und teste die Standardalgos an denen.
Das reizt mich jetzt: hast du 2-3 Beispielgraphen …?
leider habe ich selbst keine realistischen Beispieldaten. 1500
Knoten können als Worst-Case angesehen werden. Immer ca 100
bilden einen vollständigen Graphen (z.b. K0-101, K102-202,
K203-303).
Also ~100 Farben ? Das sollte die Sache (im Vergleich zum allgemeinen Fall) deutlich vereinfachen. Wenn mir nächstes WE langweilig ist teste ich den Ansatz von vor 3 Antworten mal in java.
Die weiteren Kanten sind vollständig unbekannt! Es
können ein paar Dutzend, aber auch ein paar Tausend sein.
Das ist Pech. Das kann dir die Laufzeit ganz schön verhageln.
Vielleicht muss ich mir doch nochmal die
Monte-Carlo-Algorithmen genauer anschauen…
MCs finden viele, aber nicht alle Lösungen. MC arbeitet immer mit Zufall. Es geht darum schnell eine Vorstellung von der realen Lösung zu bekommen, allerdings ohne diese wirklich zu bestimmen. Wenn du alle brauchst ist MC der falsche Weg.
cu
Morgen pumpkin!
Die Anwendung, die die Graphen nachher sucht, sollte auch
nicht länger als ein paar Minuten benötigen.Das ist bei 1500 Knoten auch ohne Voodoo drin. Kuck dir mal
das an:
http://www.nlsde.buaa.edu.cn/~kexu/benchmarks/graph-…
und teste die Standardalgos an denen.
Was meinst du mit „Standard“?
Ich nicht ganz, was du mit der Seite sagen willst. Dort werden doch nur einige Probleme im DIMACS Format aufgeführt.?!?
Das reizt mich jetzt: hast du 2-3 Beispielgraphen …?
leider habe ich selbst keine realistischen Beispieldaten. 1500
Knoten können als Worst-Case angesehen werden. Immer ca 100
bilden einen vollständigen Graphen (z.b. K0-101, K102-202,
K203-303).Also ~100 Farben ? Das sollte die Sache (im Vergleich zum
allgemeinen Fall) deutlich vereinfachen. Wenn mir nächstes WE
langweilig ist teste ich den Ansatz von vor 3 Antworten mal in
java.
Gerne doch! Würde mich freuen!
MCs finden viele, aber nicht alle Lösungen. MC arbeitet immer
mit Zufall. Es geht darum schnell eine Vorstellung von der
realen Lösung zu bekommen, allerdings ohne diese wirklich zu
bestimmen. Wenn du alle brauchst ist MC der falsche Weg.
Richtig, ich könnte allerdings damit leben, wenn das Ergebnis z.B. mit einer Wahrscheinlichkeit von 99,9% richtig wäre. Ich denke, dass es auch mit einem Randomisierten Algo. mögliche sein sollte, alle Lösungen zu finden. Vielleicht lässt sich ja aber auch ein las-Vegas-Algo. finden… Diese Woche komm ich wohl leider aber noch nicht dazu, das Problem per Randomisierung anzugehen.
Unter http://lion.dit.unitn.it/intelligent-optimization/cl… hab ich einen Solver für das Maximum Clique Problem gefunden, allerdings funktioniert der nicht und die Links sind auch tot. Mal schauen, ob eine Email an den Webmaster etwas erreicht.
Weiter muss ich mir die Kriterien, mit denen die Lösungen ausgewählt werden soll nochmal anschauen. Vielleicht kann ich, nachdem ich eine Lösung geraten habe auch schon während dem Ermitteln der weiteren Lösungen abschätzen, ob dieses relevant sind oder nicht, in dem ich sie mit der geratenen Lösung (bzw. der besten bisher gefundenen Lösung) vergleiche.
Viele Grüße,
Klaus