Das Finden der minimalen Menge von Eigenschaften, die eine referent in einer Menge von Entitäten beschreiben

Question

Ich frage mich, wenn jemand mir Zeiger erhalten helfen könnte, dieses Problem zu lösen. Ein Link zu Algorithmen wäre großartig, aber Zeiger auf Papiere / info ist auch gut.

Das Problem ist wie folgt. Angenommen, ich habe eine Menge E von Entitäten E={car1, car2, bicycle} und eine Reihe von Eigenschaften P ={red, blue, small}. Ich habe auch eine Wissensbasis, so dass red(bicycle), blue(car1), blue(car2), small(car2). Angenommen, ich habe auch einen referenten r, die E gehört.

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

Irgendwelche Ideen? Ich denke, so etwas wie das Set abdeckt Problem oder funktionale Abhängigkeiten (wie in DB Theorie) könnte einen Einblick bieten, aber ich dachte, ich würde fragen, bevor sie in dieser Literatur geht. Noch eine weitere Möglichkeit Graphen ist zu bauen und finden Algorithmen für Subgraphen Isomorphien ... vielleicht.

Danke.

Answer 1

Zuerst die Menge aller Eigenschaften finden, hat r. Nennen Sie es S. Für jede Eigenschaft p in S, finden e (p), alle Einheiten, die die Eigenschaft p. Es ist klar, für jeden p S in der e (p) enthält, r. Nun nehmen Sie die Schnittstellen von e (p) für jedes p in S. Wenn der Schnittpunkt mehr als eine Einheit enthält, gibt es keine Lösung gibt, und wir am Ende des Algorithmus.

So haben wir eine Menge S von Eigenschaften, die die Entität eindeutig r bestimmen. Jetzt brauchen wir eine minimale Teilmenge von S zu finden, die eindeutig r bestimmt. Wir können jede Eigenschaft p von S entfernen, für die es eine Eigenschaft q in S existiert, so dass e (p) ist eine Obermenge von e (q). Wenn Sie, dass erschöpfend tun, werden Sie schließlich mit einem reduzierten Satz von Eigenschaften T am Ende, so dass der Schnittpunkt der e (p) für alle p in T noch sein wird {r}, aber keine weitere Eigenschaft in T kann entfernt werden. Dieses Set T ist dann minimal.

Ich habe an nichts gedacht, um eine Immobilie zu finden, machen Sie eine effizientere entfernen können als nur alle Kombinationen versucht, aber es scheint mir, dass es einen Weg geben.

Answer 2

Sie suchen einen Mindestabdeckung der Menge E \ {r} mit Negationen (Ergänzungen) jene Eigenschaften, die gehören r (Eigenschaften können als Teilmengen von E behandelt werden).

Da diese Sätze keine Sets sein kann, das ist NP-schwer.

Genauer gesagt:

Mit einem Satz Abdeckung Instanz (U, S), wo U ist die Menge, die Sie benötigen decken und S = {s1, s2, ..., sn} ist die Familie der Abdeckung Sets können Sie eine Instanz Ihrer konstruieren Problem so, dass seine Lösung eine Reihe Abdeckung in dem ursprünglichen Problem gibt:

E = U \ union {r}, wobei r der referent und r gehört nicht U. Der Satz von Eigenschaften P = {p1, p2, ..., pn} von S so aufgebaut ist, dass für jeden in e U und jeden i, so dass 1 <= i <= n wir pi (e) iff e haben, ist nicht in si. Außerdem jede Eigenschaft gilt für r. Mit anderen Worten Eigenschaften sind Ergänzungen der ursprünglichen Sätze, wenn sie U beschränkt und r hat alle Eigenschaften.

Jetzt ist es klar, daß jeder Satz von Eigenschaften, die r auswählt, ist ein Satz Abdeckung in das ursprüngliche Problem - wenn r durch einen Satz S* von Eigenschaften ausgewählt ist, dann sind alle anderen Elemente (das bedeutet, alle in U) versagen mindestens eine Eigenschaft in S* gehört so jedes Element von U zu mindestens einen ursprünglichen Satz (von Bau von Eigenschaften als Komplemente der Sets). Das bedeutet, dass U ist die Vereinigung jener Sätze, aus denen Eigenschaften in S* gebaut wurden.

Das Gegenteil ist auch wahr -. Ein Satz Abdeckung in U zu einem r-Auswahl Satz in E übersetzt

Die obige Reduktion ist offensichtlich Polynom, so ist das Problem NP-hart.