Komplexe viele zu viele Beziehung?

Question

Ich arbeite an einem Projekt mit einer komplexen Datenstruktur, von der ich nicht weiß, wie sie analysiert werden soll. Ich habe versucht, eine Lösung zu entwickeln, aber jede Idee, die ich mir ausgedacht habe, hat das Gefühl, dass sie keine hundertprozentige Genauigkeit haben wird. Wenn es eine bereits bekannte und erprobte Methode gibt, kann ich mich darauf verlassen.

So, hier ist ein Beispiel:

ein Geschäft Stellen Sie sich eine Liste der Aktionen, hat jede Aktion eine eigene Liste, ob es mit anderen Aktionen verbinden kann. Ich muss Stacks von Promotions erstellen, die sich miteinander verbinden können und keine Promotions überhaupt lassen.

können also sagen, ich habe Promotions, A, B, C, D. Ich werde eine Liste erhalten mir zu sagen, welche Aktionen stapeln, mit denen Aktionen:

A -> B = S (stapelbar)

A -> C = N (nicht stapelbar)

A -> D = S

B wird auch seine Liste haben und D wird seine Liste haben. Ich kann nicht davon ausgehen, dass ein N nicht bedeutet, dass es stapelbar ist, aber ich kann davon ausgehen, dass kein S bedeutet, dass es nicht stapelbar ist. Es kann zwischen 1 und unendlich viele Promotions geben.

Ich muss sicherstellen, dass ich jede mögliche Kombination von Aktionen zur Verfügung habe. Am Ende brauche ich ein Array aller Kombinationen (vorzugsweise einzigartige Kombinationen), aber auch nicht-eindeutige ist in Ordnung, wenn jede Kombination aufgeführt ist. Wenn Sie den Namen für ein solches Problem kennen, können Sie nur mit dem Namen antworten, Sie müssen meine Frage nicht bearbeiten, nur ein Name genügt mir, um mich selbst mehr auf Google zu suchen.

Answer 1

Ich denke, das kann als clique problem formuliert werden.

Sie müssen ein Diagramm erstellen, in dem die Werbeaktionen Scheitelpunkte sind und zwischen zwei Scheitelpunkten eine Kante vorhanden ist, wenn die Werbeaktionen gestapelt werden können. Eine mögliche Heraufstufung ist jetzt ein vollständiger Untergraph oder eine Clique, bei der es sich um einen Untergraphen handelt, bei dem jeder Scheitelpunkt im Untergraphen mit jedem anderen Scheitelpunkt verbunden ist.

Dies ist ein NP-vollständiges Problem, aber wenn Ihr System nicht zu groß ist, sollte es möglich sein, zu lösen.

Ein Brute-Force-Algorithmus ist ziemlich geradlinig. Es gibt zwei spezielle Fälle.

1. Zuerst werden alle Eckpunkte sind Cliquen (jeweils Förderung allein)
2. die Kanten Alle verbindet zwei Ecken Cliquen (Liste von zwei Aktionen) sind

Dann für Ruhe

k = 2 .. (number of vertices) 
    v in vertices 
    if (v.neighbors.size >= k) 
     s in distinct combination of k neighbors of v and v 
     if each vertex in s has a link to other vertices in s add s to the list 

Wie kann aus dem Algorithmus gesehen werden, es wird langsamer, wenn es viele Links gibt, wie die Anzahl der Kombination exponentiell wächst.