Laufzeit eines Algorithmus zum Cliquenproblem |
| 19.06.2020, 19:32 | WilhelmV | Auf diesen Beitrag antworten » |
| Laufzeit eines Algorithmus zum Cliquenproblem Ich habe angefangen, wenn mir langweilig ist ein wenig an NP-vollständigen Problemen zu knobeln, in der Hoffnung, dass mir irgendein schnellerer Algorithmus einfällt. (Keine Sorge, mir ist bewusst dass das naiv ist und dass die Wahrscheinlichkeit, etwas innovatives zu finden quasi Null ist, aber ich finde es relativ entspannend weil ich gerne Rätsel löse) Im Anhang habe ich jetzt mal meine Idee dafür hochgeladen, die darauf basiert die Cliquen Knoten für Knoten aufzubauen und früher zu eliminieren, anstatt alle (n über k) Kombinationen zu testen. Ich kann allerdings nicht ganz ableiten, wie sich die Laufzeit bei großen n und k entwickelt, da einerseits k und n die Anzahl der Schleifen stark begrenzen, andererseits viele Schleifen aufgemacht werden. Ich habe unter dem folgenden Link einmal meine Ideen aufgeschrieben, vielleicht kann jemand mit mehr Ahnung von Komplexitätstheorie mir dabei helfen, entweder indem er erkennt wie die Laufzeit sich entwickelt oder vielleicht auch bemerkt dass es einen ähnlichen Algorithmus schon lange gibt (Ich habe zum Beispiel den Bron?Kerbosch-Algorithmus gefunden, bin aber nicht sicher ob er quasi gleich abläuft). Danke euch! Meine Ideen: https://www.dropbox.com/s/39fh1r7a047el6z/Cliquenproblem per Matrixeliminierung.pdf?dl=0 |
||
|
|
Verwandte Themen
| Die Beliebtesten » |
|
| Die Größten » |
|
| Die Neuesten » |
|
