Den minimalen Satz von Eigenschaften finden, die einen Referenten in einer Gruppe von Entitäten beschreiben

Question

Ich habe mich gefragt, ob jemand mir helfen könnte, Hinweise zu bekommen, um dieses Problem zu lösen. Ein Link zu Algorithmen wäre großartig, aber auch Hinweise auf Papers/Info sind gut.

Das Problem ist wie folgt. Angenommen, ich habe eine Menge E von Einheiten E={car1, car2, bicycle} und eine Menge von Eigenschaften P ={red, blue, small}. Ich habe auch eine Wissensdatenbank wie red(bicycle), blue(car1), blue(car2), small(car2). Angenommen, ich habe auch einen Referenten r, der zu E gehört.

Das Problem besteht darin, den minimalen Satz von Eigenschaften P' \subseteq P so zu finden, dass es r von E eindeutig herauspickt. Wenn also rcar2 ist, dann P'={small}.

Irgendwelche Ideen? Ich denke, etwas wie das Set-Covering-Problem oder funktionale Abhängigkeiten (wie in der DB-Theorie) könnte einen Einblick geben, aber ich dachte, ich würde fragen, bevor ich in diese Literatur gehe. Eine weitere Möglichkeit ist das Erstellen von Graphen und das Finden von Algorithmen für Subgraph-Isomorphismen ... vielleicht.

Danke.

Answer 1

Zuerst finden Sie die Menge aller Eigenschaften, die r hat. Nennen Sie es S. Für jede Eigenschaft p in S finden Sie e (p), alle Entitäten, die die Eigenschaft p haben. Für jedes p in S ist klar, dass e (p) r enthält. Nimm nun die Schnittpunkte von e (p) für jedes p in S. Wenn die Kreuzung mehr als eine Entität enthält, gibt es keine Lösung, und wir beenden den Algorithmus.

Also haben wir eine Menge S von Eigenschaften, die die Entität r eindeutig bestimmen. Jetzt müssen wir eine minimale Teilmenge von S finden, die r eindeutig bestimmt. Wir können jede Eigenschaft p aus S entfernen, für die in S eine Eigenschaft q existiert, so dass e (p) eine Obermenge von e (q) ist. Wenn Sie das erschöpfend tun, werden Sie schließlich mit einem reduzierten Satz von Eigenschaften T enden, so dass der Schnittpunkt von e (p) für alle p in T immer noch {r} ist, aber keine weitere Eigenschaft in T kann entfernt werden. Diese Menge T ist dann minimal.

Ich habe nicht an etwas gedacht, um eine Eigenschaft zu finden, die Sie effizienter entfernen können als nur alle Kombinationen zu versuchen, aber es scheint mir, dass es einen Weg geben sollte.

Answer 2

Sie suchen nach einem minimum set cover der Menge E \ {r} mit Negationen (Komplementen) derjenigen Eigenschaften, zu denen r gehört (Eigenschaften können als Untermengen von E behandelt werden).

Da diese Sätze beliebige Sätze sein können, ist dies NP-schwer.

Genauer gesagt:

mit einem Satz Cover-Instanz (U, S), wo U ist die Menge, die Sie benötigen zu decken und S = {s1, s2, ..., sn} ist die Familie der Deckung

E = U \ union {r}, wobei r ist der referent und: Sets können Sie eine Instanz des Problems, so dass seine Lösung gibt eine Reihe Abdeckung in dem ursprünglichen Problem konstruierengehört nicht zu U. Die Menge der Eigenschaften P = {p1, p2, ..., pn} wird aus S so dass für jede e in U und jeder i so dass 1 < = konstruiert i < = n haben wir pi (e) iff e ist nicht in si. Darüber hinaus gilt jede Eigenschaft für r. Mit anderen Worten, Eigenschaften sind Ergänzungen der ursprünglichen Sätze, wenn sie auf U beschränkt sind, und r hat alle Eigenschaften.

Nun ist es klar, daß jeder Satz von Eigenschaften, die r ist ein Satz Abdeckung in dem ursprünglichen Problem wählt - wenn r von einem Satz ausgewählt ist S* von Eigenschaften, dann alle andere Elemente (das bedeutet, alle in U) versagt bei mindestens eine Eigenschaft in S*, so gehört jedes Element von U zu mindestens einer ursprünglichen Menge (aus der Konstruktion von Eigenschaften als Komplementen der Mengen). Das bedeutet, dass U eine Vereinigung jener Mengen ist, aus denen Eigenschaften in S* konstruiert wurden.

Die Umkehrung ist auch wahr - ein Set-Cover in U übersetzt in r-Select Set in E.

Die obige Reduktion ist offensichtlich polynomial, also ist das Problem NP-schwer.