Ich versuche ein Problem zu lösen, wo ich Paare wie:
habe %Vor%und ich muss sie in Dreiergruppen gruppieren, wo ich ein Dreieck aus dieser Liste haben muss. Grundsätzlich brauche ich ein Ergebnis, wenn es möglich ist oder nicht, eine Sammlung zu gruppieren.
Die möglichen Gruppen sind also ( ACD und BFE ) oder ( ABC und DEF ) und diese Sammlung ist gruppierbar, da alle Buchstaben in Gruppen von 3 gruppiert werden können und niemand ausgelassen wird.
Ich habe ein Skript erstellt, mit dem ich dies für kleine Mengen an Input erreichen kann, aber für große Mengen wird es zu langsam.
Meine Logik ist:
%Vor%und ich mache das, bis ich keine Briefe mehr habe. Da es verschiedene Kombinationen geben kann, führe ich diese mehrfach mit verschiedenen Buchstaben aus, bis ich eine Übereinstimmung finde.
Ich kann verstehen, dass dies Schleifen in der Reihenfolge mindestens N^N gibt und zu langsam werden kann. Gibt es eine bessere Logik für solche Probleme? Kann hier ein Binärbaum verwendet werden?
Dieses Problem kann als Graph Clique-Cover-Problem modelliert werden. Jeder Buchstabe ist ein Knoten und jedes Paar ist eine Kante und Sie möchten den Graphen in vertex-disjoint Cliquen der Größe 3 (Dreiecke) aufteilen. Wenn Sie möchten, dass die Partitionierung von minimaler Kardinalität ist, dann wollen Sie eine minimale Cliquenabdeckung .
Eigentlich wäre das ein k-Clique-Cover-Problem, denn beim Clique-Cover-Problem kann man Cliquen beliebiger / unterschiedlicher Größe haben.
Wie Alberto Rivelli bereits gesagt hat, ist dieses Problem auf das Clique-Cover-Problem reduzierbar, das NP-schwer ist. Es ist auch reduzierbar auf das Problem, eine Clique bestimmter / maximaler Größe zu finden. Vielleicht gibt es andere, nicht NP-schwere Probleme, auf die sich Ihr bestimmter Fall reduzieren lässt, aber ich habe an keine gedacht.
Allerdings gibt es do Algorithmen, die die Lösung in polynomieller Zeit finden können, allerdings nicht immer für die schlimmsten Fälle. Einer davon ist der Bron-Kerbosch-Algorithmus , der bei weitem als der effizienteste Algorithmus bekannt ist zum Finden der maximalen Clique und kann im schlimmsten Fall von O eine Clique finden (3 ^ (n / 3)). Ich kenne die Größe Ihrer Eingaben nicht, aber ich hoffe, dass es für Ihr Problem ausreicht.
Hier ist der Code in Python, bereit zu gehen:
%Vor%Wenn diese Lösung immer noch zu langsam ist, kann es effizienter sein, stattdessen das Clique-Cover-Problem zu lösen. Wenn das der Fall ist, kann ich versuchen, einen geeigneten Algorithmus dafür zu finden.
Hoffe das hilft!
Nun, ich habe den Job in JS implementiert, wo ich mich am zuversichtlichsten fühle. Ich habe es auch mit 100000 Kanten versucht, die zufällig aus 26 Buchstaben ausgewählt wurden. Vorausgesetzt, dass sie alle einzigartig sind und kein Punkt wie ["A",A"] ist, wird sie in etwa 90 ~ 500 ms aufgelöst. Der gewundenste Teil bestand darin, die nicht identischen Gruppen zu erhalten, die sich nicht nur in der Reihenfolge der Dreiecke änderten. Für die gegebenen Kanten Daten löst es innerhalb von 1 ms.
Als Zusammenfassung findet die erste Reduzierungsstufe die Dreiecke und die zweite Reduzierstufengruppe die getrennten Reduzierungen.
Sie können zufällige Kanten in verschiedenen Längen erzeugen und mit dem Code hier
spielenTags und Links algorithm combinatorics