Ein bisschen Automatentheorie, oder doch nicht?
Ich stehe hier vor einem Problem für das ich einen Namen brauche. Ich möchte gerne wissen ob es schonmal gelöst wurde (nicht das Rad zweimal erfinden). Ich hoffe ihr könnt meinen Ausführungen folgen 😉.
Die Ausgangslage
Ich habe eine Reihe von Merkmalen die 1 oder 0 ausgeprägt sein können. Nennen wir die Merkmale mal M1 bis M4. Es könnte z.B. gelten:
Merkmal | Wert
--------------
M1 | 0
M2 | 1
M3 | 1
M4 | 1
Für die Merkmale soll jetzt eine Bewertungsmatrix angesetzt werden. Je nachdem welche Kombination eintritt gilt eine andere Gewichtung. Der Einfachheit nehme ich mal zwei Bewertungen vor.
Merkmal | B1 | B2 |
--------------------
M1 | 0.4 | 0.1 |
M2 | 0.6 | 0.8 |
M3 | 0.2 | 0.1 |
M4 | 0.3 | 0.1 |
Die Summe errechnet sich durch B1 * M1 + B1 * M2 ... = S1 und B2 * M1 ... = S2. Für das Beispiel würde sich S1 = 1.1 und S2 = 1.0 ergeben.
Die Regeln
Das Ziel der Konstruktion ist es eine Wahrscheinlichkeit festzustellen ob ein bestimmter Fall eintritt. Dafür legt man Fest, dass der Fall (nennen wir ihn mal F) true ist, wenn S1 < 1.5 und S2 < 1.0. Spiegelbildlich wird F = false.
Das Problem ist aber, dass F durch einen booleschen Ausdruck definiert werden soll, der nur die eingangs erwähnten Merkmale enthält.
D.h. in diesem Fall:
Bedingung 1 (S1 < 1.5):
(M1 AND M2 AND M3 AND NOT M4) OR (M1 AND M2 AND NOT M3 AND M4) ...
Bedinung 2 (S2 < 1.0):
(M1 AND M1 AND NOT M3 ...
Die beiden Ausdrücke werden dann per AND konjugiert. Letztendlich müsste der Ausdruck dann wieder vereinfacht werden. (zumindest hier habe ich Algorithmen/Ansätze gefunden)
**Die Frage **
In welchem Themenbereich bin ich hier?
Wie kann ich Softwarekomponenten finden, die sich mit der Problemstellung beschäftigen?
Muss ich doch auf "dem weißen Blatt" anfangen?
Vielen Dank, schonmal
Hallo Levion,
die Ausgangslage ist klar. Der erste Teil der Regeln auch. Unklar wird es bei mir ab:
Das Problem ist aber, dass F durch einen booleschen Ausdruck definiert werden soll, der nur die eingangs erwähnten Merkmale enthält.
Verstehe ich es richtig, dass F nicht wie im Satz davor als true oder false definiert wird, sondern als boolscher Ausdruck, der aus M1-M4 aufgebaut ist?
Und wenn ja, wo ist denn das Problem?
Da du die tatsächlichen Werte für M1-M4 kennst, musst du die doch nur einsetzen, kannst die Bedingung ausrechnen und bekommst am Ende wieder true oder false heraus.
herbivore
Und wenn ja, wo ist denn das Problem?
Also technisch gibt es gar kein Problem. Ich weiß nur nicht ob es bereits eine Implementierung für meine Idee gibt. Ich hab schon Spaß am Programmieren, aber auch an meiner Freizeit 😉
Hallo Levion,
eine Implementierung für welchen Teil genau?
Es gibt sicher fertige Parser für boolsche Formen, falls das das Problem ist. Wenn man die Formel als Objektbaum im Speicher hat, sollte das Ausrechnen des Wahrheitswerts kein Problem sein.
herbivore
Hallo witte,
ob es um das NP-vollständige Erfüllbarkeitsproblem der Aussagenlogik geht, hängt davon ab, ob der Merkmalsvektor (M1, ...M4) bekannt ist (nein, Lösung trivial) oder ob einer gefunden werden soll, der die boolsche Bedingung erfüllt (ja, Lösung NP schwierig). Ich lese eher die erstere Variante aus der Beschreibung, aber mir ist zugegeben leider immer noch nicht klar, worauf Levion eigentlich hinaus will.
herbivore